第5章 跳跃表

为什么从“跳跃表路径与跨度台”开始

第5章 跳跃表的核心任务是用zskiplist层级、前进指针、跨度和后退指针解释有序集合的范围与排名操作。命令返回值只暴露外层合同；实现解释还必须连接内存结构、写入与读取路径、事件顺序以及失败后的旧状态回收。跳跃表路径与跨度台把这些关系放进同一条可复位轨迹。

先写预测：当目标位置由“中位区间”进入“表尾附近”时，哪个可观察状态最先变化？再规定什么结果会推翻当前解释。交互中的分数只表达透明因果方向，不冒充真实Redis测量。

来源、版次与独立重写边界

黄健宏作者读者服务页确认正式出版新版以Redis 3.0为源码基线，列出4部分、24章及完整小节，并链接Redis 3.0中文注释源码。本课程据此映射24个正式单元、145个目录节点，另设学习地图和总复习；未取得出版正文授权，目录只界定范围，不宣称复现原书正文。

本章字段与控制流由Redis官方3.0源码：t_zset.c和作者注释源码交叉核对；Redis当前持久化文档只用于辨认版本差异。中文解释、图示、交互、实验与答案均为独立教学重写，不把目录页或代码仓库许可证误报为原书许可证。

本章术语与源码合同

第5章 跳跃表必须守住“分值顺序与成员字典序稳定，跨度可恢复排名，层级和前后链在更新后保持一致”。观察同时记录跳跃表路径与跨度台一致率与操作分叉风险；只有结构快照、函数入口、运行结果和故障反例互相一致，才接受实现结论。

作者目录逐项深读

跳跃表的实现

四级证据 1/3。 zskiplistNode按随机层保存forward与span，另有backward；头节点不保存成员，tail支持反向访问。本节点用“跳跃表的实现”作观察点，执行rg 'zslInsert|zslDelete|zslGetRank' src/t_zset.c或等价源码探针，保存版本、输入、前后状态和能推翻解释的反例。

验证跳跃表的实现时，先预测目标位置从“中位区间”切到“表尾附近”会改变哪个字段、偏移、文件或消息；再固定操作做一次对照。若故障注入没有破坏“分值顺序与成员字典序稳定，跨度可恢复排名，层级和前后链在更新后保持一致”，就撤回当前解释而不是补写故事。

跳跃表API

四级证据 2/3。 插入先记录每层update与rank，再同时修正前进指针和跨度；排名由沿途span累加得到。本节点用“跳跃表API”作观察点，执行rg 'zslInsert|zslDelete|zslGetRank' src/t_zset.c或等价源码探针，保存版本、输入、前后状态和能推翻解释的反例。

验证跳跃表API时，先预测目标位置从“中位区间”切到“表尾附近”会改变哪个字段、偏移、文件或消息；再固定操作做一次对照。若故障注入没有破坏“分值顺序与成员字典序稳定，跨度可恢复排名，层级和前后链在更新后保持一致”，就撤回当前解释而不是补写故事。

重点回顾

四级证据 3/3。 第5章 跳跃表的回顾要重新证明“分值顺序与成员字典序稳定，跨度可恢复排名，层级和前后链在更新后保持一致”，并用同一输入比较结构前态、变更轨迹、故障首错与恢复后态

验证重点回顾时，先预测目标位置从“中位区间”切到“表尾附近”会改变哪个字段、偏移、文件或消息；再固定操作做一次对照。若故障注入没有破坏“分值顺序与成员字典序稳定，跨度可恢复排名，层级和前后链在更新后保持一致”，就撤回当前解释而不是补写故事。

最小源码与运行切片

+git clone --branch 3.0 --depth 1 https://github.com/redis/redis.git redis-3.0
+cd redis-3.0
+rg 'zslInsert|zslDelete|zslGetRank' src/t_zset.c

该切片固定Redis 3.0分支、编译器、配置、数据集和命令序列；先保存结构或函数位置，再运行隔离实例。任何持久化损坏、断线、故障转移、大键或高流量实验都必须使用临时数据并规定CPU、内存、磁盘、延迟和停止上限。

unit: rdi-05-skiplist
source_file: t_zset.c
axis_a: "目标位置"
axis_b: "操作"
fault: "只维护forward指针而漏改span或backward，范围结果正确但排名错误"
invariant: "分值顺序与成员字典序稳定，跨度可恢复排名，层级和前后链在更新后保持一致"
replay: same_version_same_input

三个必须主动触发的误区

误区 1

现象 → 对跳表做频繁中间删除 原因 → 链表指针维护成本累积 修法 → 批量删除或定期重建

误区 2

现象 → 范围查询不限制数量 原因 → 全量遍历大 zset 修法 → ZRANGE 必带 LIMIT 分批

误区 3

现象 → 期望层数越高越好 原因 → 层数过多浪费内存 修法 → 理解期望 1.33 层的概率设计

小结

• 跳表用随机层数实现有序索引
• 平均 O(logN) 支持范围查询
• 实现比平衡树简单且局部性好
• zset 大数据量时选跳表
• 每层都是有序链表

练习、答案与节点验证

术语复核与本章回顾

完成第5章 跳跃表意味着能从t_zset.c解释用zskiplist层级、前进指针、跨度和后退指针解释有序集合的范围与排名操作，能运行章专属状态实验，能制造反例并在复位后证明旧状态没有残留。