第 7 章
跳表 skiplist：为什么不用红黑树
第七章：跳表 skiplist——为什么不用红黑树
7.1 为何选择跳表而非红黑树
这是 Redis 面试中最高频的底层问题之一。Redis 的有序集合（ZSet）选择跳表而非业界更常见的红黑树，原因是多维度的。
7.1.1 范围查询的差异
ZSet 最核心的操作之一是 ZRANGE/ZRANGEBYSCORE——在有序集合中按分值范围取出一批元素。
红黑树的范围查询：
红黑树逻辑结构：
30
/ \
20 50
/ \ / \
10 25 40 60
ZRANGEBYSCORE key 20 50 → 需要中序遍历找到 [20, 25, 30, 40, 50]
1. 找到下界 20：O(log N)
2. 从 20 开始中序遍历到 50：O(M)，但节点间跳转需要爬升父节点再下降
3. 平均每步需要访问父节点：缓存不友好
跳表的范围查询：
跳表第0层（有序链表）：
head → [10] → [20] → [25] → [30] → [40] → [50] → [60] → NULL
ZRANGEBYSCORE key 20 50：
1. 跳表查找下界 20：O(log N)
2. 沿第0层顺序遍历到 50：O(M)，所有节点物理相邻（链表顺序访问）
3. CPU 预取友好：第0层是标准链表，内存访问模式线性
这不是理论上的差异。对于 M=1000 的范围查询，跳表的第0层遍历几乎是纯线性内存访问，CPU 缓存命中率高；红黑树中序遍历的内存访问模式是树状跳跃，对现代 CPU 流水线不友好。
7.1.2 实现复杂度
红黑树插入/删除需要：
- 左旋（rotateLeft）
- 右旋（rotateRight）
- 变色（recolor）
- 父节点指针、兄弟节点访问
- 多种平衡调整 case（至少 6 种，加上删除的 case）
跳表插入/删除：
- 从最高层向下找到插入位置
- 记录每层的 update[] 指针数组（最多 32 个）
- 随机生成层高
- 修改指针
- 更新 span（跨度字段）
无需旋转，无需维护颜色，代码量约为红黑树的 1/3
7.1.3 并发性潜力
虽然 Redis 单线程处理命令，但这是跳表相对红黑树的内在优势：
红黑树旋转操作：
- 一次旋转可能影响 3 个节点（父、子、孙）
- 锁粒度粗，CAS 困难
- 无锁红黑树实现极为复杂
跳表：
- 每层的指针修改相对独立
- 已有成熟的无锁跳表实现（如 Java ConcurrentSkipListMap）
- 未来 Redis 多线程化的可扩展性更好
7.1.4 内存使用
红黑树节点固定字段：
left* + right* + parent* + color + key + value = 5 个指针 + 额外字段
跳表节点期望指针数（p=0.25，MAXLEVEL=32）：
期望层高 = 1/(1-p) = 1/(1-0.25) = 1.333 层
每层1个 forward 指针 → 期望 1.333 个 forward 指针
+1 个 backward 指针（第0层）
总计：期望约 2.33 个指针/节点（vs 红黑树的 3 个）
注意：这里的"更少"是概率期望，实际分布有方差
7.2 zskiplistNode 完整结构
7.2.1 C 结构定义（t_zset.c）
/* ZSet 跳表节点 */
typedef struct zskiplistNode {
sds ele; /* 成员值（SDS 字符串） */
double score; /* 分值（排序依据） */
struct zskiplistNode *backward; /* 第0层后退指针（双向链表用） */
struct zskiplistLevel {
struct zskiplistNode *forward; /* 前进指针（指向同层下一节点） */
unsigned long span; /* 跨度：本节点到 forward 之间的第0层节点数 */
} level[]; /* 柔性数组，实际层数在创建时确定 */
} zskiplistNode;
/* ZSet 跳表容器 */
typedef struct zskiplist {
struct zskiplistNode *header, *tail; /* 头尾节点指针 */
unsigned long length; /* 节点总数（不含哨兵 header） */
int level; /* 当前跳表的最大层数 */
} zskiplist;
7.2.2 内存布局示意（3层跳表，3个节点）
level[2] ─────────────────────────────────────────► NULL
header level[1] ──────────────► [node B] level[1] ──────► NULL
(哨兵) level[0] ──► [node A] level[0] ──► [node C] NULL
score=1.0 score=2.0 score=3.0
span=1 span=2 span=1
backward: NULL ◄── node A ◄── node B ◄── node C ◄── (tail)
│
zskiplist.tail
zskiplist.header→哨兵节点（ele=NULL, score=-inf）
zskiplist.tail →node C
zskiplist.length=3
zskiplist.level =3
span（跨度）字段的作用：span 存储从当前节点的某层 forward 指针所跨越的第0层节点数量。利用 span 可以在 O(log N) 时间内计算任意节点的排名（ZRANK）。
node A level[1] forward → node C, span=2
含义：从 A 的第1层直接跳到 C，跨越了 2 个第0层节点（A本身+B）
7.2.3 哨兵 header 节点
/* 创建跳表时，header 节点预分配 ZSKIPLIST_MAXLEVEL=32 层 */
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
zskiplistNode *zn =
zmalloc(sizeof(*zn) + level * sizeof(struct zskiplistLevel));
zn->score = score;
zn->ele = ele;
return zn;
}
zskiplist *zslCreate(void) {
int j;
zskiplist *zsl;
zsl = zmalloc(sizeof(*zsl));
zsl->level = 1;
zsl->length = 0;
zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL, 0, NULL);
for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
zsl->header->level[j].forward = NULL;
zsl->header->level[j].span = 0;
}
zsl->header->backward = NULL;
zsl->tail = NULL;
return zsl;
}
7.3 随机层高算法
7.3.1 算法实现
/* server.h */
#define ZSKIPLIST_MAXLEVEL 32 /* 最大层数 */
#define ZSKIPLIST_P 0.25 /* 晋升概率 */
int zslRandomLevel(void) {
static const int threshold = ZSKIPLIST_P * RAND_MAX;
int level = 1;
while (random() < threshold)
level += 1;
return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
7.3.2 概率分析
层高分布（p=0.25）：
层高 1：概率 = (1-p) = 0.75 ≈ 75%
层高 2：概率 = p(1-p) = 0.1875 ≈ 18.75%
层高 3：概率 = p²(1-p) = 0.046875 ≈ 4.69%
层高 4：概率 = p³(1-p) = 0.01171875 ≈ 1.17%
层高 k：概率 = p^(k-1)(1-p)
期望层高 E[level] = 1/(1-p) = 1/0.75 ≈ 1.333
期望比较次数（查找）：
E[comparisons] ≈ (log_{1/p} N) / p + 1/p
当 N=1M，p=0.25：≈ (log₄ 1000000) / 0.25 + 4 ≈ 10/0.25 + 4 ≈ 44 次
红黑树查找比较次数：
2 × log₂ N ≈ 2 × 20 = 40 次
两者相近，但跳表的常数因子更友好（缓存局部性）
7.3.3 为什么选 p=0.25 而不是 p=0.5
p=0.5 时（标准跳表）：
期望层高 = 2，期望指针数/节点 = 2
查找性能：O(log₂ N)
p=0.25 时（Redis 选择）：
期望层高 = 1.333，期望指针数/节点 = 1.333
查找性能：O(log₄ N) = O(log₂ N / 2)，但常数更大
Redis 选 p=0.25 的理由：
1. 减少内存：每节点期望指针数 1.333 < 2
2. 性能仍是 O(log N)，实际差异可忽略
3. 在 N=100-10000 的典型 ZSet 规模下，p=0.25 已足够
7.4 ZADD 操作完整流程
7.4.1 查找插入位置
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL]; /* 每层插入位置的前驱节点 */
zskiplistNode *x;
unsigned long rank[ZSKIPLIST_MAXLEVEL]; /* 每层前驱节点的累计排名 */
int i, level;
x = zsl->header;
/* 从最高层向下搜索 */
for (i = zsl->level-1; i >= 0; i--) {
rank[i] = (i == zsl->level-1) ? 0 : rank[i+1];
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele, ele) < 0))) {
rank[i] += x->level[i].span; /* 累加跨度 */
x = x->level[i].forward;
}
update[i] = x; /* 记录每层的前驱节点 */
}
7.4.2 插入节点并更新 span
level = zslRandomLevel();
if (level > zsl->level) {
/* 新层数超过当前最大层，初始化新层 */
for (i = zsl->level; i < level; i++) {
rank[i] = 0;
update[i] = zsl->header;
update[i]->level[i].span = zsl->length;
}
zsl->level = level;
}
x = zslCreateNode(level, score, ele);
for (i = 0; i < level; i++) {
/* 修改前进指针 */
x->level[i].forward = update[i]->level[i].forward;
update[i]->level[i].forward = x;
/* 更新 span：
新节点的 span = update[i].span - (rank[0] - rank[i])
update[i].span = rank[0] - rank[i] + 1 */
x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
update[i]->level[i].span = (rank[0] - rank[i]) + 1;
}
/* 层数未达到 level 的上层，span 增1 */
for (i = level; i < zsl->level; i++) {
update[i]->level[i].span++;
}
/* 设置后退指针 */
x->backward = (update[0] == zsl->header) ? NULL : update[0];
if (x->level[0].forward)
x->level[0].forward->backward = x;
else
zsl->tail = x;
zsl->length++;
return x;
}
7.4.3 插入操作可视化
初始跳表（3层）：
L2: head ──────────────────────────────► NULL
L1: head ──────► [10,s=10] ─────────► [30,s=30] ─► NULL
L0: head ──► [5] ──► [10] ──► [20] ──► [30] ─────► NULL
插入 score=15, ele="x"，随机层高=2：
update[0] = node[10] rank[0] = 2（从head到node[10]经过2步）
update[1] = head rank[1] = 0
新节点层高=2，插入后：
L2: head ──────────────────────────────────────── NULL
L1: head ──► [10] ──────► [15,new] ──► [30] ──── NULL
L0: head ──► [5] ──► [10] ──► [15,new] ──► [20] ──► [30] ─► NULL
span 更新：
new.level[0].span = 1（指向 node[20]，跨1步）
update[0]=node[10]: level[0].span = 1
new.level[1].span = update[1].level[1].span - (rank[0]-rank[1]) = ...
7.5 ZRANK 时间复杂度分析
long zslGetRank(zskiplist *zsl, double score, sds ele) {
zskiplistNode *x;
unsigned long rank = 0;
int i;
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele, ele) <= 0))) {
rank += x->level[i].span; /* 累加跨度即为排名 */
x = x->level[i].forward;
}
if (x->ele && sdscmp(x->ele, ele) == 0)
return rank;
}
return 0;
}
O(log N) 的来源：
ZRANK 的时间复杂度 = 跳表查找复杂度 = O(log N)
与普通查找的区别：不需要额外的"计数"操作
普通 BST 的 rank 查询需要维护子树大小（Augmented BST）
跳表的 span 字段本身就是一种排名计数器
查找路径上的 span 累加自然得到排名
7.6 ZRANGE 范围查询
/* ZRANGE key min max → O(log N + M) */
void zrangebyscoreGenericCommand(client *c, int reverse) {
/* 1. 解析 min/max，支持 -inf/+inf */
/* 2. 用 zslFirstInRange 在跳表中找到第一个满足条件的节点 O(log N) */
/* 3. 沿 level[0] 的 forward 顺序遍历，O(M) */
/* 4. 收集结果，支持 WITHSCORES, LIMIT offset count */
}
/* 找到范围内第一个节点 */
zskiplistNode *zslFirstInRange(zskiplist *zsl, zrangespec *range) {
zskiplistNode *x;
int i;
if (!zslIsInRange(zsl, range)) return NULL;
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward &&
!zslValueGteMin(x->level[i].forward->score, range))
x = x->level[i].forward;
}
x = x->level[0].forward; /* 现在 x 是第一个满足条件的节点 */
if (!zslValueLteMax(x->score, range)) return NULL;
return x;
}
7.7 ZSet 的双结构设计
7.7.1 为什么同时维护跳表和字典
/* t_zset.c — ZSet 对象使用两个结构 */
typedef struct zset {
dict *dict; /* 成员 → 分值的字典，O(1) 按成员查分值 */
zskiplist *zsl; /* 跳表，O(log N) 按分值范围查询 */
} zset;
两个结构各自解决一个问题：
| 操作 | 使用结构 | 复杂度 |
|---|---|---|
ZSCORE member |
dict | O(1) |
ZADD member score |
dict + skiplist | O(log N) |
ZRANK member |
skiplist | O(log N) |
ZRANGE min max |
skiplist | O(log N + M) |
ZINCRBY member delta |
dict（查分值）+ skiplist（更新位置） | O(log N) |
7.7.2 共享 sds ele（不复制内存）
/* zadd 操作：ele 指针被两个结构共享 */
zskiplistNode *znode = zslInsert(zs->zsl, score, ele);
dictEntry *de = dictAddRaw(zs->dict, ele, NULL); /* key 是同一个 sds 指针！ */
dictSetVal(zs->dict, de, &znode->score);
/* 删除时注意顺序：先从 dict 中找到 ele，再从跳表中删除 */
内存示意：
┌──────────────────────────────┐
sds ───► "member_name" (SDS 对象) │
└──────────────────────────────┘
▲ ▲
│ │
zskiplistNode.ele dictEntry.key
(跳表节点持有) (字典桶持有)
两者指向同一 sds 对象，不存在内存复制
7.8 内存占用对比：listpack vs skiplist+dict
场景：ZSet 有 100 个元素
member: "user:XXXX"（9字节），score: double（8字节）
listpack 编码（元素数 ≤ 128）：
Header: 6 字节
每个元素对（member+score）:
member element: encoding(1) + data(9) + backlen(1) = 11字节
score element: encoding(1) + data(8, double) + backlen(1) = 10字节
100对: 100 × 21 = 2100字节
end: 1字节
总计: ≈ 2107字节
skiplist + dict 编码（元素数 > 128 时使用）：
每个 zskiplistNode:
sds ele: sds header(3) + 9字节 + '\0' = 13字节（zmalloc对齐到16B）
score: 8字节（double）
backward: 8字节（指针）
期望 level 数: 1.333 层 → 2层（含 forward 指针×2 + span×2）= 32字节
节点 zmalloc: 16（zmalloc头）+8（score）+8（backward）+2×16（level）= 72字节
100节点 skiplist: 100 × (72 + 16) ≈ 8800字节
dict overhead（load factor 0.5, 128桶）: 128×8（桶）+ 100×(16+8)（entry）= 3424字节
总计: ≈ 12224字节
结论：listpack 约 2KB，skiplist+dict 约 12KB，差异约 6x
这就是为什么阈值（128元素）设计合理——小对象用 listpack 节省大量内存
7.9 小结
跳表的选择体现了 Redis 工程团队的务实哲学：
- 范围查询友好：第0层天然是有序链表，范围扫描 O(log N + M)，缓存友好
- 实现简单：无旋转无变色，代码量小，Bug 少
- 内存效率：p=0.25 时期望指针数仅 1.333，优于红黑树的 3 个固定指针
- 与 dict 双结构互补：跳表做范围，字典做点查，两种操作都是最优
跳表并非所有场景都优于红黑树——在纯点查场景（无范围查询）下，红黑树的常数更小。但 ZSet 的使用场景（排行榜、延迟队列、地理位置）本质上都需要范围查询，跳表在这里是最优解。