目录
1. 1.1、zskiplistNode：带导航标记的 "商品"（跳跃表节点）
1.1.1.4、obj：商品的 "名称牌"（衔接 SDS！）
1.1.2、zskiplist：商场的 "总服务台"（跳跃表管理结构）
3.2、为什么不用平衡树？——"导航系统比复杂树状图更实用"
如果说 SDS 是 "智能价签"、链表是 "货架"、字典是 "储物柜"，那么跳跃表就是 Redis 为 "有序商品展示" 设计的商场多层导航系统。当你需要按价格排序展示商品（如电商 APP 的 "价格从低到高"），或者记录游戏排名这类需要快速定位和范围查询的场景时，跳跃表就会像商场的多层导视图一样，让你不用逐个浏览就能快速找到目标。
一 、从 "超市货架" 的痛点看跳跃表的价值
假设你在超市的 "零食区" 货架上按价格排序摆放着商品：
薯片(5元) → 巧克力(10元) → 牛肉干(15元) → 坚果(20元) → ... → 进口礼盒(100元)
这本质上是一个有序链表（类似我们之前讲的 list 结构），但有个明显问题：如果想找 "30 元左右的商品"，你必须从第一个商品开始逐个查看 —— 就像顾客在货架前从头走到尾，效率很低（时间复杂度 O (N)）。
超市为了解决这个问题，会在货架上方加多层导航牌：
- 地面层（对应货架本身）：每个商品都能看到
- 中层导航（2 米高）：每隔 5 个商品标一个价格区间（如 "5-15 元区→15-30 元区→..."）
- 高层导航（5 米高）：标注大区间（如 "0-50 元区→50-100 元区"）
这种设计让顾客先看高层导航定位大致区域，再通过中层导航缩小范围，最后在地面层精确查找 —— 这就是跳跃表的核心思路：用多层索引实现 "跳着找"，把复杂度从 O (N) 降到平均 O (logN)。
1.1、跳跃表与商场导航系统的结构对应
Redis 的跳跃表结构与商场导航系统的对应关系非常直观，我们结合之前学过的结构知识逐层拆解：
1. 1.1、zskiplistNode：带导航标记的 "商品"（跳跃表节点）
每个商品就像一个跳跃表节点，不仅有自身信息，还带着多层导航标记：
typedef struct zskiplistNode {
// 层（多层导航标记）
struct zskiplistLevel {
struct zskiplistNode *forward; // 前进指针（指向远处的商品）
unsigned int span; // 跨度（中间隔了多少个商品）
} level[];
// 后退指针（只能回到前一个商品）
struct zskiplistNode *backward;
// 分值（商品价格，排序依据）
double score;
// 成员对象（商品名称，用SDS存储）
robj *obj;
} zskiplistNode;
1.1.1.1、level []：商品上的多层导航标记
- 这是跳跃表的核心，每个
level元素对应一层导航。比如level[0]是 "地面层导航"（必有的基础层），level[1]是 "中层导航"，level[2]是 "高层导航"（最多 32 层）。 - forward 指针：就像商品上贴的 "前方 50 米有 30 元区" 标签，直接指向远处的目标节点。比如在 "15 元牛肉干" 的中层导航（level [1]）上，forward 可能直接指向 "30 元饼干"，跳过中间的 20 元、25 元商品。
- span（跨度）：记录两个节点之间的 "间隔数"。比如从 15 元牛肉干到 30 元饼干中间有 3 个商品，span 就等于 3—— 这就像导航标签上写着 "中间有 3 个商品"，能快速计算排名（比如知道 15 元是第 3 名，span=3，30 元就是第 6 名）。
1.1.1.2、backward：商品的 "后退箭头"
- 每个节点只有一个 backward 指针，只能指向 "前一个节点"，就像货架上的 "返回上一个商品" 箭头，顾客看完当前商品想回头，只能一步一步往回走（不能跳）。这和链表的 prev 指针功能类似，但跳跃表的 forward 指针能跳，backward 不能 —— 因为后退场景少，没必要浪费空间做多层后退索引。
1.1.1.3、score：商品的 "价格标签"
score是排序的依据（必须有序），就像商品按价格从小到大排列。在 Redis 的有序集合中，比如ZADD goods 5 "chip" 10 "chocolate"，这里的 5 和 10 就是 score。
1.1.1.4、obj：商品的 "名称牌"（衔接 SDS！）
obj存储的是成员名称（如 "chip"），底层用SDS实现（呼应我们讲过的 SDS 结构）：- 比如 "chocolate" 这个名称，实际存储为 SDS：
len=9（9 个字符）、free=9（预分配空间）、buf=['c','h','o','c','o','l','a','t','e','\0']。 - 为什么用 SDS？因为商品名称可能很长（比如 "2024 限量版进口巧克力"），SDS 的动态扩展和二进制安全特性，能高效存储这些字符串（和我们之前讲的字典键存储逻辑一致）。
- 比如 "chocolate" 这个名称，实际存储为 SDS：
1.1.2、zskiplist：商场的 "总服务台"（跳跃表管理结构）
如果说zskiplistNode是单个商品，zskiplist就是商场服务台的 "总导视图"，记录全局信息：
typedef struct zskiplist {
struct zskiplistNode *header, *tail; // 首/尾商品位置
unsigned long length; // 商品总数
int level; // 最高导航层数
} zskiplist;
这几个字段的作用和服务台导视图完全对应：
- header/tail：导视图上标着 "零食区起点" 和 "零食区终点"，让你瞬间定位第一个和最后一个商品（O (1) 复杂度）。比如想找最便宜的商品，直接从 header 开始；想找最贵的，直接定位到 tail。
- length：导视图上写着 "共 50 种商品"，不用数货架就知道总数（O (1) 复杂度）—— 这和链表的 len 属性功能相同，但链表需要遍历统计，跳跃表直接记录。
- level：导视图上标着 "最高 3 层导航"，告诉你最高层索引是多少，避免在不存在的高层导航中查找（O (1) 复杂度）。
二、跳跃表的工作流程：像顾客找商品一样简单
我们用 "找 30 元的商品" 这个场景，看跳跃表的查找过程（对应顾客在商场找 30 元商品）：
从最高层导航开始（比如 3 层）：
服务台导视图显示最高 3 层，顾客先看 3 层导航，发现 "0-50 元区" 的起点是 5 元薯片，终点是 50 元礼盒。30 元在这个区间内，于是下到 2 层导航。中层导航缩小范围（2 层）：
2 层导航标着 "5-15 元→15-30 元→30-50 元"，顾客从 5 元薯片出发，顺着 2 层导航的 forward 指针跳到 15 元牛肉干（span=2，中间有 2 个商品），再跳到 30 元饼干（span=3，中间有 3 个商品）。地面层精确查找（1 层）：
到了 30 元饼干的位置，发现正好是目标，查找结束。如果没找到，就顺着 1 层的 forward 指针逐个查看（因为 1 层是完整链表）。
这个过程完美体现了 "高层跳大步，低层走小步" 的效率优势 —— 比从第一个商品逐个查找快得多。
三、设计细节：为什么跳跃表要这样设计？
3.1、节点层数为什么随机？——"热门商品多挂导航"
每个新节点的层数（1-32 层）是随机生成的，就像商场会给热门商品挂更多层导航（比如畅销零食在高、中、低三层都有标记），普通商品可能只在地面层有标记。
随机层数的好处：
- 避免所有节点都挂 32 层导航（浪费空间）
- 统计上能形成 "高层节点少、低层节点多" 的金字塔结构，保证查找效率
这就像字典的哈希分布策略，通过概率平衡性能和空间。
3.2、为什么不用平衡树？——"导航系统比复杂树状图更实用"
有序数据结构中，平衡树（如红黑树）也能达到 O (logN) 效率，但 Redis 选跳跃表的原因：
- 实现简单：跳跃表的多层索引逻辑比平衡树的 "旋转调整" 简单（就像商场导航比复杂的树状分布图好懂）。
- 范围查询高效：比如找 "20-50 元的商品"，跳跃表从 20 元节点开始，顺着 1 层 forward 指针就能批量获取（类似链表的顺序遍历），平衡树需要复杂的左右子树遍历。
- 空间可控：层数上限 32，不会像平衡树那样因频繁调整导致空间波动（类似商场导航层数固定，不会突然增删楼层）。
3.3、与之前结构的配合：Redis 的 "结构组合拳"
跳跃表不是孤立存在的，而是和其他结构配合工作：
- 与 SDS 配合：用 SDS 存储节点的成员名称（obj），利用其动态字符串特性（如之前讲的空间预分配、长度记录）。
- 与字典配合：在有序集合中，Redis 会同时用字典（记录 member 到 score 的映射）和跳跃表（按 score 排序），形成 "快速查找 + 有序遍历" 的组合（就像商场既有储物柜按编号找东西，又有导航系统按价格找东西）。
四、总结：跳跃表的设计智慧
| 跳跃表组件 | 商场导航系统对应 | 技术价值 | 与其他结构的关联 |
|---|---|---|---|
| zskiplistNode.level | 商品的多层导航标签 | 分层查找，平均 O (logN) 效率 | - |
| forward 指针 | 导航标签的 "指向箭头" | 快速跳跃定位 | 类似字典的哈希定位，但支持有序 |
| span 跨度 | 导航标签的 "间隔数" | 快速计算排名（如 ZRANK 命令） | - |
| backward 指针 | 商品的 "后退箭头" | 支持反向遍历（如 ZREVRANGE） | 类似链表的 prev 指针 |
| score 分值 | 商品价格标签 | 作为排序依据 | - |
| obj 成员对象 | 商品名称牌 | 存储成员信息 | 用 SDS 实现，复用字符串优化 |
| zskiplist 管理结构 | 商场总导视图 | O (1) 获取全局信息（首尾、总数等） | 类似链表的 list 管理结构 |
跳跃表就像为 "有序数据快速访问" 量身定制的导航系统，它没有追求最复杂的结构，而是用 "多层索引 + 随机优化" 的简单思路，平衡了效率、实现难度和空间开销。这种设计思路和 Redis 的整体哲学一致 —— 为不同场景选择最合适的结构（字符串用 SDS、无序查找用字典、有序查找用跳跃表），最终实现 "又快又稳" 的性能表现。