跳表 — 算法 — 计算机科学

1990 年，威廉·普格（William Pugh）在《ACM 通讯》发表了《跳表：平衡树的概率替代》，提出了跳表（Skip List）这一数据结构。

普格开篇写道："平衡树……可以用于同样的问题，但效率要低得多，而且实现和调试更加困难……我们相信跳表比平衡树的代码更容易实现，而且更快。"三十年后，跳表成了 Redis、LevelDB 等重要存储系统的核心数据结构。

破除误解：跳表不是"更快的平衡树"

普格论文标题里那句"更快"（faster）容易让人误读。把渐进复杂度摆在一起看：

	查找	插入	删除
红黑树	$O(\log n)$ 最坏	$O(\log n)$ 最坏	$O(\log n)$ 最坏
跳表	$O(\log n)$ 期望	$O(\log n)$ 期望	$O(\log n)$ 期望

跳表在渐进意义上没有更快，而且保证还更弱——它把"最坏情况"降级成了"期望情况"。在缓存局部性上它通常还更差：每跳一层就是一次指针追逐，而平衡树至少是紧凑的父子关系。

那它凭什么进 Redis、进 LevelDB？三个理由，一个都不是"更快"：

能写对。核心代码约百行，没有旋转、没有着色规则。红黑树的正确实现通常三五百行，且极难调试——工程可靠性本身就是一种性能。
能并发。这是最重要的一条，下文详述：跳表的修改是局部的单指针写，可以无锁；平衡树的旋转牵动多个节点，几乎只能加锁。
能范围查询。最底层就是一条完整有序链表，ZRANGEBYSCORE 这类"取出区间内全部元素"的操作天然高效。

记住这个判断顺序：数据结构的胜负很少由渐进复杂度决定；相同复杂度下，决定选择的是常数因子、并发性和实现成本。

动机：有序数据结构的困境

链表：插入/删除 $O(1)$，但查询 $O(n)$（需要顺序扫描）。

平衡二叉搜索树（AVL、红黑树）：查询、插入、删除均为 $O(\log n)$ ，但实现复杂——红黑树的旋转和重新着色规则是出了名的难以正确实现，调试困难，且不易实现并发版本。

跳表的承诺：用概率和多层链表，在期望 $O(\log n)$ 时间内完成所有操作，实现简单，且天然支持并发。

结构：多层有序链表

跳表的本质是多层有序单链表的叠加：

第 0 层（最底层）：包含所有元素，按键值有序排列
第 1 层：包含约一半元素（第 0 层的随机子集）
第 2 层：包含约四分之一元素
第 $k$ 层：约包含 $n / 2^k$ 个元素
顶层通常只有 1–2 个元素

每个节点有指向同层下一个节点的指针，也有指向下一层同一节点的指针。

层 3: ----[1]----------------------------[9]----
层 2: ----[1]----------[5]-------------[9]----
层 1: ----[1]---[3]----[5]---[7]------[9]----
层 0: ----[1]-[2]-[3]-[4]-[5]-[6]-[7]-[8]-[9]-
```

查找：从顶层向下跳

查找键 $k$，从最高层的头节点开始：

当前节点 = 头节点（最高层）
对每一层（从高到低）：
  向右移动，直到下一个节点的键 > k 或到达末尾
  向下一层
若当前节点的键 = k：找到，返回
否则：不存在
```

每层向右跳过约一半的节点，总比较次数期望约 $2\log n$ 。

走一遍：在上面那张图里查 key = 7。

步	位置	看到的下一个节点	判断	动作
1	头节点，层 3	`[1]`	$1 \le 7$	右移到 `[1]`
2	`[1]`，层 3	`[9]`	$9 > 7$，跳过头了	下降到层 2
3	`[1]`，层 2	`[5]`	$5 \le 7$	右移到 `[5]`
4	`[5]`，层 2	`[9]`	$9 > 7$	下降到层 1
5	`[5]`，层 1	`[7]`	$7 \le 7$	右移到 `[7]`，命中

5 次比较，而在层 0 从 [1] 一路扫到 [7] 需要 7 次。$n = 9$ 时这点差距不值一提——跳表的意义在于差距怎么增长：链表是 $n$，跳表是 $\log n$ 。$n$ 涨到一百万，链表平均 50 万次比较，跳表约 40 次。

注意每一步的逻辑只有一条：能跳就跳，跳过头就下一层。没有旋转、没有重新着色、没有"叔叔节点是红色还是黑色"的分支表——这就是普格所说"更容易实现和调试"的具体含义。

插入：随机化高度

插入新节点时，用随机抛硬币决定其高度：

level = 1
while random() < 0.5 and level < MaxLevel:
    level += 1
```

每增加一层的概率为 $p = 0.5$（可调整），节点高度为 $k$ 的概率为 $(1-p)p^{k-1}$ ，期望高度为 $1/(1-p)$，最大高度约 $\log_{1/p} n$ 。

然后在各层适当位置插入该节点。时间复杂度期望 $O(\log n)$ 。

性能分析

操作	期望时间	最坏情况（极低概率）
查找	$O(\log n)$	$O(n)$
插入	$O(\log n)$	$O(n)$
删除	$O(\log n)$	$O(n)$
空间	$O(n)$	$O(n \log n)$

"最坏情况"在随机化跳表中发生的概率极低——以 $n = 10^6$ 为例，操作退化到 $O(n)$ 的概率约为 $n^{-\Omega(\log n)}$ ，可以忽略不计。

为什么工业界选择跳表？

实现简单：跳表的核心代码约 100 行，而正确实现红黑树通常需要 300–500 行，且调试极为困难。

并发友好——这是最被低估、也最有分量的一条。区别在于一次修改牵动多少节点：跳表插入只改若干条 next 指针，每条都是一次独立的单字写入，可以用 CAS（Compare-And-Swap）原子完成；红黑树插入可能触发一连串旋转与重新着色，牵动祖父、叔叔、兄弟节点，这些改动必须一起生效，否则中途读到的树是非法的。前者能做成无锁（lock-free），后者几乎只能加锁。

Java 的 ConcurrentSkipListMap（JDK 6 起，Doug Lea 实现）就是无锁跳表：读操作完全不加锁也不重试，写操作靠 CAS 加"逻辑删除标记"处理竞争——想删一个节点时先插入一个标记节点，让其他线程知道"这里正在拆"，避免丢失并发插入。它是 JDK 里唯一的并发有序 Map，也是"为什么不用并发红黑树"的答案。

缓存友好的遍历：底层链表支持高效的顺序遍历（如范围查询），这对数据库场景至关重要。

LevelDB 和 RocksDB：Google 的 LevelDB 和 Meta 的 RocksDB 用跳表实现内存中的有序写缓冲区（MemTable），支持高速写入和有序遍历。

现场：Redis 到底怎么用跳表

Redis 的有序集合（Sorted Set，命令 ZADD/ZRANGE/ZRANGEBYSCORE）是跳表最广为人知的工业应用——排行榜、延时队列、时间线，背后都是它。但真实实现比"用了跳表"这句话丰富得多，几个细节值得看：

1. 参数不是 1/2，是 1/4。 Redis 源码 src/t_zset.c 里写着：

#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */
```

为什么把 $p$ 从教科书的 $1/2$ 降到 $1/4$？因为每个节点的期望指针数是 $1/(1-p)$：$p = 1/2$ 时是 2 个，$p = 1/4$ 时只有 1.33 个。对一个可能存着上亿成员的排行榜，这是三分之一的指针内存。代价是每层要多走几步才跳过头，比较次数略增——普格原论文就分析过这个权衡，并指出除非特别在意运行时间的波动，$p = 1/4$ 是更省的选择。Redis 站在内存这一边。

2. 层高上限 32 是硬编码的。 不是动态算的，是一个常数。这带来一个副作用：随机层高必须截断在 32，所以理论分析里"层高无界"的假设在实现中不成立——不过在 $p=1/4$ 下，一个节点长到 32 层的概率是 $4^{-31}$ ，这辈子都不会发生。

3. 跳表从来不是单干的。 Redis 的 zset 同时维护跳表 + 哈希表：哈希表负责 ZSCORE（成员 → 分数）的 $O(1)$ 查询，跳表负责 ZRANGEBYSCORE 的 $O(\log n)$ 范围查询。两个结构指向同一批成员，用双倍元数据买下"点查快 + 范围查快"。

4. 小集合根本不用跳表。 Redis 7 起，成员数 ≤ zset-max-listpack-entries（默认 128）且每个成员 ≤ zset-max-listpack-value（默认 64 字节）时，zset 用紧凑连续内存的 listpack（Redis 7 之前叫 ziplist）编码——线性扫描，但内存占用远低于带指针的跳表节点，且完全没有指针跳转的缓存缺失。超过任一阈值才转成跳表，且不再转回去。

第 4 点是全篇最该记住的工程判断： $O(\log n)$ 只在 $n$ 大的时候才划算。$n = 50$ 时，线性扫一段连续内存比在跳表里跳 3 层指针更快——渐进复杂度赢了，常数因子和缓存局部性输了。成熟系统的做法不是选一个数据结构，而是按规模切换。

代价与争议

最坏情况不保证：与 AVL 树、红黑树不同，跳表的性能是概率性的。但这里有个容易混淆的地方值得说清：跳表的随机性来自内部抛硬币，不来自输入数据。所以它不像朴素哈希表那样存在"精心构造的输入触发最坏情况"的攻击面——攻击者猜不到你的硬币。真正的风险是另一个：随机数种子可被预测。如果层高由一个可推断的伪随机源生成，攻击者原则上能反推出层高分布并构造退化序列。这也解释了为什么"随机性依赖"这条不只是性能问题，还是安全问题。

空间开销：每个节点期望 $1/(1-p)$ 个前向指针（$p=1/2$ 时 2 个，$p=1/4$ 时 1.33 个），加上必须为每层单独存指针数组，空间常数大于只需两个孩子指针的红黑树。

在磁盘和现代 CPU 上败给 B+ 树：这是最实在的一条。B+ 树把几十上百个键塞进一个节点（对齐到磁盘页或缓存行），一次 IO / 一次缓存加载就能推进一大步；跳表每跳一次就是一次指针追逐（pointer chasing），几乎必然是一次缓存缺失。所以数据库索引清一色 B+ 树，跳表活跃在纯内存、需要有序、且并发写很重的那一小块地盘上——正是 Redis zset 和 LSM 树 MemTable 的形状。

它没有赢，是找到了自己的位置：普格 1990 年提出跳表时的定位是"平衡树的替代品"，三十多年后的实际结局更精确——它没有取代平衡树，而是占住了平衡树最不擅长的那个角落。这在算法史上是常态：新结构很少全面胜出，它们赢在某一组约束下。

跨域连接

概率论：层高服从几何分布，性能保证靠的是集中不等式：证明的不是"平均还行"，而是"偏离期望的概率随规模指数衰减"。这一点很关键——随机性来自内部抛硬币而非输入，所以不存在"精心构造的输入触发最坏情况"，除非随机数种子可被预测。
并发：真正的分水岭是一次修改牵动多少节点。插入只改若干条指针，每条都能用一次原子比较交换完成；平衡树的旋转牵动祖父、叔叔与兄弟，这些改动必须一起生效，否则中途读到的树是非法的。前者能做成无锁，后者几乎只能加锁。
哈希：哈希把键打散，顺序信息随之被抹掉，"下一个比它大的键是谁"再也答不了。这个信息一旦丢失无法从结构中恢复，所以有序集合的实现会同时挂一张哈希表与一条跳表，用双份元数据买下点查快与范围查快两件事。
B 树与 LSM 树：磁盘与缓存改写了胜负。B 树把几十上百个键塞进一个对齐到页或缓存行的节点，一次加载推进一大步；跳表每跳一层就是一次指针追逐，几乎必然缓存缺失。所以索引结构在磁盘上清一色是前者，跳表活跃在纯内存、需要有序、并发写重的那一块地盘。
风险与不确定性：期望意义的对数复杂度与最坏意义的对数复杂度，渐近记号一样，保证的性质完全不同。对延迟敏感的在线系统，两者不能互换——正如对破产敏感的决策不能只看期望收益。选数据结构时该先问要的是哪一种保证。

参考文献

Pugh, W. Skip Lists: A Probabilistic Alternative to Balanced Trees. CACM 33(6), 668–676 (1990).
Pugh, W. A Skip List Cookbook. Technical Report CS-TR-2286.1. University of Maryland, 1990.（含 $p$ 取值的空间/时间权衡分析）
Herlihy, M., Lev, Y., Luchangco, V. & Shavit, N. A Provably Correct Scalable Concurrent Skip List. OPODIS 2006.
Redis 源码 src/t_zset.c（ZSKIPLIST_MAXLEVEL / ZSKIPLIST_P 定义与 zslRandomLevel 实现）。

破除误解：跳表不是"更快的平衡树"#

动机：有序数据结构的困境#

结构：多层有序链表#

查找：从顶层向下跳#

插入：随机化高度#

性能分析#

为什么工业界选择跳表？#

现场：Redis 到底怎么用跳表#

代价与争议#

跨域连接#

参考文献#

延伸阅读#