Redis 跳跃表（ZSet 底层实现）
你可能见过这张图：
┌───┐
│ 1 │──────────────┐
─────►└───┘ │
┌───┐ ┌───┐ ┌───┐ ┌───┐
─────►│ 3 │──│ 5 │──│ 7 │──────│ 9 │───► NULL
└───┘ └───┘ └───┘ └───┘
┌───┐ ┌───┐ ┌───┐ ┌───┐
─────►│ 2 │──│ 4 │──│ 6 │──────│ 8 │───► NULL
└───┘ └───┘ └───┘ └───┘
┌───┐ ┌───┐ ┌───┐ ┌───┐
─────►│ 1 │──│ 2 │──│ 3 │──────│ 4 │───► NULL
└───┘ └───┘ └───┘ └───┘这就是跳跃表（Skip List），ZSet 的底层实现之一。
为什么 Redis 选择了跳表而不是红黑树？跳表是怎么工作的？
为什么要跳跃表？
先从一个问题开始：如何在有序数组中查找一个元素？
- 顺序遍历：O(n)
- 二分查找：O(log n)
但有序数组的插入/删除是 O(n)，因为需要移动元素。
而链表的插入/删除是 O(1)，但查找是 O(n)。
跳跃表就是来解决这个矛盾的：让链表也能二分查找。
跳跃表的核心思想
第一次跳跃：建立索引
普通链表：
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → NULL建立一层索引（每两个节点抽一个）：
1 ────────────────────→ 5 ────────────────────→ 9 → NULL
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → NULL查找 7：
- 在索引层从 1 跳到 5，发现 5 < 7，继续
- 跳到 9，发现 9 > 7，从 5 降到原层
- 从 5 遍历到 7，找到
原来需要遍历 7 次，现在只需要 1 + 3 = 4 次。
多次跳跃：更稀疏的索引
┌───────────────────┐
│ 1 ────────────────→ 9 → NULL
▼
1 ────────────────→ 3 ────────────────→ 5 ────────────────→ 7 ────────────────→ 9 → NULL
▼ ▼ ▼ ▼ ▼
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → NULL查找 8：
- 第 2 层：1 → 9（9 > 8，降层）
- 第 1 层：5 → 9（9 > 8，降层）
- 第 0 层：遍历 7 → 8，找到
层数越多，查找越快。理论上，n 个节点的跳表高度约为 log₂n，每层最多遍历 1 个节点。
跳表的数据结构
Redis 中的实现
c
// 跳表节点
typedef struct zskiplistNode {
robj *obj; // 成员对象（SDS）
double score; // 分值（排序依据）
struct zskiplistLevel {
struct zskiplistNode *forward; // 前进指针
unsigned int span; // 跨度（用于计算 rank）
} level[];
} zskiplistNode;
// 跳表
typedef struct zskiplist {
struct zskiplistNode *header, *tail; // 头尾节点
unsigned long length; // 节点数量
int level; // 最大层数
} zskiplist;关键设计：随机层数
新节点插入时，层数是随机决定的：
java
/**
* Redis 使用这个算法决定层数：
*
* 每次有 50% 概率升一层
*
* 层数分布：
* 1 层：50%
* 2 层：25%
* 3 层：12.5%
* 4 层：6.25%
* ...
*
* 平均每个节点的层数约为 1/(1-p) = 2
* 当 p = 0.5 时
*
* 这样设计：
* - 保证上层节点是下层的子集（索引稀疏均匀）
* - 空间开销可控（层数期望为常数）
* - 实现简单，不需要平衡操作
*/Redis 的具体实现：
c
// 随机层数生成（Redis 源码）
int zslRandomLevel(void) {
int level = 1;
// ZSKIPLIST_P = 0.25，每层有 25% 概率升一层
while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
// 最大层数 32
return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}注意：Redis 使用 p=0.25（每层 25% 概率升一层），而不是 50%。
跳表的操作
插入操作
java
/**
* 跳表插入步骤：
*
* 1. 找到每一层的插入位置（记录前驱节点）
* 2. 生成随机层数
* 3. 创建新节点，逐层插入
* 4. 更新每一层的指针
*
* 时间复杂度：O(log n)
* - 查找位置：O(log n)（多层索引加速）
* - 插入节点：O(1)（只需要修改指针）
*/伪代码：
java
public void insert(zskiplist zsl, double score, robj obj) {
// 1. 找到每一层的插入位置
zskiplistNode[] update = new zskiplistNode[zsl.level];
int[] rank = new int[zsl.level];
zskiplistNode x = zsl.header;
for (int i = zsl.level - 1; i >= 0; i--) {
rank[i] = (i == zsl.level - 1) ? 0 : rank[i + 1];
while (x.level[i].forward != null &&
(x.level[i].forward.score < score ||
(x.level[i].forward.score == score &&
compare(x.level[i].forward.obj, obj) < 0))) {
rank[i] += x.level[i].span;
x = x.level[i].forward;
}
update[i] = x;
}
// 2. 生成随机层数
int level = randomLevel();
// 3. 创建新节点并插入
for (int i = 0; i < level; i++) {
x.level[i].forward = update[i].level[i].forward;
update[i].level[i].forward = x;
// 更新 span
}
}范围查询
java
/**
* ZRANGEBYSCORE 如何利用跳表？
*
* 1. 从最高层开始，找到第一个 >= min 的节点
* 2. 逐层下降，定位到具体位置
* 3. 顺序遍历收集结果
*
* 定位：O(log n)
* 遍历：O(m)，m 为返回元素数量
*
* 总复杂度：O(log n + m)
*/删除操作
java
/**
* 删除类似插入：
* 1. 找到每一层的节点位置
* 2. 更新前后指针
* 3. 释放内存
*
* 时间复杂度：O(log n)
*/为什么 Redis 选择跳表而不是红黑树？
这是面试经典问题，来看对比：
| 特性 | 跳表 | 红黑树 |
|---|---|---|
| 实现复杂度 | 简单（几百行） | 复杂（平衡旋转） |
| 范围查询 | 天然支持（顺序遍历） | 需要中序遍历 |
| 插入/删除 | 只改指针，均摊 O(log n) | 需要旋转，可能 O(log n) |
| 查找 | O(log n) | O(log n) |
| 空间复杂度 | O(n log n)（索引层） | O(n) |
| 线程安全 | 单线程无需加锁 | 多线程需要锁 |
Redis 选择跳表的原因
java
/**
* 1. 实现简单：
* - Redis 代码量有限，跳表更容易维护
* - 红黑树的旋转、染色等操作容易出错
*
* 2. 范围查询优势：
* - ZSet 需要频繁做 ZRANGE、ZREVRANGE
* - 跳表顺序遍历更自然
* - 红黑树需要中序遍历，代码复杂
*
* 3. 更容易实现：
* - Redis 作者 antirez 亲口说过：实现简单是重要原因
*
* 4. 内存开销可接受：
* - 跳表索引层约占用 2n 个节点
* - 对于现代内存不值一提
*
* 5. 单线程无需考虑并发：
* - 不需要像红黑树那样加锁
*/跳表 vs 红黑树 vs 平衡树
java
public class SkipListVsTree {
/**
* 跳表：
* - LevelDB、RocksDB 的 MemTable
* - Redis ZSet
* - 优势：实现简单，范围查询友好
*/
/**
* 红黑树：
* - JDK TreeMap
* - Linux 内核调度器
* - 优势：内存占用稳定，查找稳定 O(log n)
*/
/**
* B+ 树：
* - MySQL InnoDB 索引
* - 优势：磁盘友好，减少磁盘 IO
*/
/**
* 选择依据：
* - 数据在内存中，选跳表或红黑树
* - 数据在磁盘上，选 B+ 树
* - 需要简单实现，选跳表
*/
}ZSet 的双重索引
前面讲过，ZSet 同时使用跳表和哈希表：
java
/**
* ZSet 结构：
*
* typedef struct zset {
* dict *dict; // member → score，O(1) 查找分数
* zskiplist *zsl; // 按 score 排序，支持范围查询
* } zset;
*
* 为什么需要两个？
*
* 1. 跳表操作：
* - ZRANGE：按排名范围查（跳表天然有序）
* - ZRANK：获取排名（跳表记录了 span）
* - ZRANGEBYSCORE：按分数范围查
*
* 2. 哈希表操作：
* - ZSCORE：获取某成员的分数（O(1)）
* - ZREM：删除成员
*
* 3. 如果只用跳表：
* - ZSCORE 需要遍历，O(n)
* - 无法满足性能要求
*
* 4. 如果只用哈希表：
* - 范围查询需要遍历所有元素，O(n)
*
* 两者结合，各司其职
*/面试场景模拟
面试官：Redis ZSet 用什么实现的？
候选人：跳表和哈希表。
面试官：为什么用跳表而不用红黑树？
候选人（思考后）：主要有三个原因...
（好的候选人应该能展开讲）
- 实现简单：Redis 代码量有限，跳表的插入删除只需要改指针，不需要旋转平衡。
- 范围查询友好：ZSet 需要频繁做 ZRANGE 范围查询，跳表顺序遍历更自然，红黑树需要中序遍历。
- 单线程无需并发控制：跳表的指针修改在单线程环境下天然安全，红黑树的多线程操作需要加锁。
面试官：跳表是怎么保证上层索引是下层子集的？
候选人：通过随机层数。Redis 用 25% 的概率决定每层是否升级，所以上层节点数量大约是下层的 1/4。这样在查找时，上层找不到就降层继续找，最终一定能定位到目标。
性能分析
跳表的性能取决于层数和节点分布：
java
/**
* 跳表查找性能分析：
*
* 假设 n 个节点，p = 0.25（每层 25% 概率升层）
*
* 1. 层数期望：
* L(n) ≈ log_{1/p}(n) = log_4(n) ≈ log₂(n) / 2
* 例如 n = 1000000，L ≈ 10
*
* 2. 每层遍历期望：
* 每层最多遍历常数个节点（因为上层稀疏）
*
* 3. 总体时间复杂度：
* O(log n)
*
* 4. 与红黑树对比：
* - 期望复杂度相同
* - 红黑树更稳定（最坏情况也是 O(log n)）
* - 跳表有随机性，但概率极低
*/总结
跳跃表是 Redis ZSet 的核心数据结构，理解它需要理解：
| 概念 | 说明 |
|---|---|
| 多层索引 | 稀疏索引加速查找 |
| 随机层数 | 均匀分布的保证 |
| 指针操作 | 插入删除只需要改指针 |
| 与 dict 配合 | 满足不同操作的需求 |
留给你的问题
Redis 的跳表最大层数是 32，可以存储 2^32 个元素。
如果 Redis 存储了 2^32 个元素，跳表的实际层数会达到 32 吗？为什么？
提示：考虑随机层数的概率分布。