title: “跳表：概率如何击败确定性复杂度” date: “2026-03-07T04:35:05+08:00” description: “从William Pugh 1990年的原始论文出发，深入解析跳表的概率平衡原理、Redis与LevelDB的技术选型逻辑、与红黑树的权衡分析，以及为什么这种"用随机换简单"的设计哲学在高性能系统中持续发光。” draft: false categories: [“数据结构”, “算法”, “系统设计”] tags: [“跳表”, “Skip List”, “Redis”, “红黑树”, “概率数据结构”, “并发编程”, “LevelDB”]

1989年，马里兰大学的William Pugh向 Communications of the ACM 投递了一篇仅四页的论文。这篇论文提出了一个看似荒谬的问题：能不能用掷硬币的方式，替代红黑树中那些令人头疼的旋转操作？

答案是肯定的。跳表由此诞生。

三十多年后，跳表成为Redis有序集合的底层实现、LevelDB和RocksDB的MemTable默认选择、Java并发包中ConcurrentSkipListMap的核心数据结构。然而，直到今天，大多数程序员对跳表的印象仍然停留在"面试题数据结构"——知道它存在，却不知道它为何能击败红黑树。

红黑树的旋转之痛

要理解跳表的价值，必须先理解红黑树的代价。

红黑树是计算机科学中最精巧的发明之一。它通过五条规则——节点要么红要么黑、根是黑的、红节点的孩子是黑的、每个节点到其后代叶节点的路径包含相同数量的黑节点——确保树的高度始终保持在O(log n)。这个保证是确定性的，不依赖任何概率。

但确定性是有代价的。每次插入或删除，都可能触发一连串的旋转和重新着色。以删除操作为例，如果删除的是一个黑色节点，可能需要执行多次旋转和颜色调整才能恢复平衡。一个经典的例子：删除操作在最坏情况下需要执行三次旋转。

这些操作的代码难以编写正确，更难以调试。红黑树的实现通常需要处理大量边界情况：父节点存在吗？叔节点是什么颜色？兄弟节点的孩子是什么颜色？每一个分支都可能隐藏着微妙的bug。Robert Sedgewick在2008年提出的左倾红黑树，正是为了简化这些复杂的边界条件——即使简化后，实现依然不简单。

Pugh的洞察在于：复杂的旋转操作本质上是为了"强制平衡"。能不能放弃强制，改用一种"期望平衡"的方式？跳表就是这个问题的答案。

概率平衡：掷硬币的数学

跳表的核心思想极其简单：在一个有序链表上，随机添加若干层"快速通道"。

最底层是完整的有序链表。往上一层，每个节点以概率p被选中，形成更稀疏的链表。以此类推，形成多层索引结构。搜索时，从最高层开始，如果当前节点的下一个节点值小于目标，就向右移动；否则，下降一层继续搜索。

这个简单的设计背后，是精妙的数学原理。

为什么是O(log n)？

设概率p = 1/4（Redis和LevelDB的默认值）。对于一个包含n个节点的跳表：

  • 平均高度：每个节点的期望高度是 1/(1-p) = 1.33层
  • 最高层期望高度：log_{1/p}(n) = log_4(n)
  • 搜索路径长度：从目标节点逆向追踪，每上升一层期望需要检查 1/p 个节点

因此，期望搜索时间约为 (log_4 n)/p，即O(log n)。

William Pugh在原始论文中给出了一个更直观的解释：跳表的结构与一棵"随机插入"的二叉搜索树高度相似。如果向一棵空的二叉搜索树随机插入n个元素，树的高度期望为O(log n)。跳表的随机层级分配，本质上是在模拟这种"随机插入"的效果。

最坏情况有多糟？

这是跳表最常被质疑的地方：既然是概率性的，会不会出现极度不平衡的情况？

理论上会。如果运气极差，所有节点都只有一层，跳表退化为普通链表，搜索变成O(n)。但这个概率有多低？

对于p = 1/2、n = 4096的跳表，搜索路径长度超过期望值3倍的概率小于十亿分之五。Pugh在论文中给出了更极端的例子：对于n = 65,536的跳表，搜索超过期望时间2倍的概率约为10^-18。

这个概率有多低？你被陨石击中的概率大约是10^-9。换言之，跳表"运气不好"的概率比被陨石砸中还要低九个数量级。

当然，这不是说跳表没有最坏情况问题。在实时系统中，任何操作的时间上限都很重要，这时红黑树的确定性保证就体现出价值。但对于绝大多数互联网应用，这个概率风险完全可以接受。

Redis的三个理由

2011年，有人在Stack Overflow上问：为什么Redis的有序集合（ZSET）用跳表而不是红黑树？Redis作者antirez亲自回答了三个原因。

第一：内存占用可控

红黑树的每个节点需要存储：键值、颜色标记、左右孩子指针、父指针（通常需要）。即使不考虑对齐问题，这些元数据也会占用相当可观的内存。

跳表的内存占用取决于节点高度。平均而言，每个节点包含 1/(1-p) 个指针。当p = 1/4时，每个节点平均约1.33个指针。更重要的是，这个值可以通过调整p来控制：p越小，内存占用越低，但搜索速度越慢。

antirez指出，通过调整参数，跳表的内存占用可以比B树更低。对于Redis这种内存敏感的系统，这是一个重要考量。

第二：范围查询更友好

Redis的ZSET有两个核心操作：单点查询（ZSCORE）和范围查询（ZRANGE、ZRANGEBYSCORE）。红黑树对两者都能提供O(log n)的查找，但范围遍历的常数因子更大。

红黑树的范围遍历需要处理树的分支结构。从中序遍历的角度看，访问下一个节点需要考虑右子树、父节点回溯等多种情况。而跳表在底层就是一个有序链表，范围遍历就是简单的指针跟随操作。

对于经常执行ZRANGE操作的Redis实例，跳表的缓存友好性更佳：连续访问的节点在链表中物理相邻，预取效率更高。

第三：实现简单，易于扩展

antirez特别强调了一个细节：因为跳表的简单性，他收到了一个补丁，实现了O(log n)的ZRANK操作（返回元素在有序集合中的排名）。这个补丁只对跳表做了很小的修改。

这个"易于扩展"的特性，源于跳表的结构简单性。每个节点的层级独立决定，没有全局约束。添加新功能（如记录跨度信息支持排名查询）不需要重新设计核心逻辑。

相比之下，红黑树的任何结构修改都需要重新审视平衡规则。添加字段可能破坏旋转的正确性，实现新操作可能需要修改多个辅助函数。

LevelDB的单写多读设计

跳表在LevelDB中的应用场景略有不同。LevelDB的MemTable是一个只增不减的结构：数据只会追加，删除操作实际是写入一个墓碑标记。最终，整个MemTable会被刷入磁盘成为SST文件。

基于这个特性，LevelDB的跳表实现做了一个精巧的设计：单线程写入，多线程并发读取，无需任何锁。

核心思路是利用内存屏障（Memory Barrier）。插入新节点时，LevelDB从底层向上逐层设置指针，每层设置完成后，新节点在该层就是"完全可见"的。读取线程可能看到部分更新（比如底层指针已设置，高层还未设置），但这只会导致它从更低的层级开始搜索，不影响正确性。

对于max_height_（当前最大层级）的读写，LevelDB使用std::atomic配合memory_order_relaxed。如果读取线程看到了旧的高度值，它只是从一个较低的层级开始搜索，最终也能找到目标。

这个设计的关键洞察是：跳表的层级结构是"叠加"的，高层只是底层的加速索引。即使高层完全缺失，底层的链表仍然完整可用。

// LevelDB的插入逻辑（简化版）
template<typename Key, class Comparator>
void SkipList<Key,Comparator>::Insert(const Key& key) {
  // 1. 找到插入位置
  Node* prev[kMaxHeight];
  Node* x = FindGreaterOrEqual(key, prev);
  
  // 2. 随机决定高度
  int height = RandomHeight();
  
  // 3. 创建新节点
  x = NewNode(key, height);
  
  // 4. 从底层向上逐层插入
  for (int i = 0; i < height; i++) {
    x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
    prev[i]->SetNext(i, x);  // 带内存屏障的设置
  }
}

为什么标准库不用跳表？

跳表有这么多优点，为什么C++ STL和Java的标准库（除ConcurrentSkipListMap外）仍然选择红黑树？

历史惯性

跳表发表于1990年，此时红黑树已经在标准库中站稳脚跟。SGI STL的实现（后来成为GNU STL的基础）选择了红黑树，这个选择被所有后续实现继承。标准库一旦确定，改变的成本极高。

确定性保证的价值

对于通用数据结构，最坏情况保证有其价值。库的使用者可能把它用于任何场景——包括实时系统。跳表无法承诺"每次操作都在X毫秒内完成"，这在某些场景下是不可接受的。

Doug Lea在Java并发包中选择跳表实现ConcurrentSkipListMap，恰恰是因为它的并发优势盖过了最坏情况的劣势。对于单线程场景，TreeMap（红黑树）仍然是默认选择。

缓存局部性

这是跳表的软肋。红黑树的节点大小固定，内存分配更规律。跳表的节点大小不一，且同一节点的多层指针可能分散在内存中。

在实践中，这个劣势通常被跳表更简单的操作逻辑抵消。Pugh的原始测试显示，跳表的插入和删除速度比非递归的AVL树快约1.5倍。

并发：跳表的隐藏王牌

跳表最大的优势可能不是单线程性能，而是并发友好性。

实现一个lock-free的红黑树是噩梦。删除操作可能触发多次旋转，每次旋转涉及多个节点的指针修改。如何原子地完成这一系列修改？基本做不到。

但实现一个lock-free的跳表相对直接。核心原因是：跳表的每个层级是独立的链表，插入或删除操作只需要修改相邻节点的指针。这比红黑树的旋转简单得多。

Java的ConcurrentSkipListMap使用了CAS（Compare-And-Swap）操作实现无锁并发。插入操作首先在底层完成，然后逐层向上推进。如果某一层的CAS失败，只需重试该层，不需要回滚整个操作。

sequenceDiagram
    participant T1 as 线程1
    participant T2 as 线程2
    participant L1 as 层1
    participant L2 as 层2
    
    T1->>L1: CAS插入节点A
    L1-->>T1: 成功
    T2->>L1: CAS插入节点B
    L1-->>T2: 成功
    T1->>L2: CAS插入节点A（高层）
    L2-->>T1: 成功
    T2->>L2: CAS插入节点B（失败，A已存在）
    L2-->>T2: 重试...

这种"分层独立"的特性，使得跳表成为高并发场景下有序数据结构的首选。Discord在2019年的技术博客中详细介绍了他们如何使用跳表变体处理服务器成员列表的并发更新，支撑了千万级在线用户。他们最初用Elixir实现了一个基于跳表思想的OrderedSet，后来用Rust重写后性能提升了数倍。

权衡的艺术

跳表与红黑树的选择，本质上是一个权衡问题：

维度 跳表 红黑树
时间复杂度（期望） O(log n) O(log n)
时间复杂度（最坏） O(n) O(log n)
空间开销 约1.33指针/节点 3指针+1颜色/节点
实现复杂度 低 高
范围查询 O(k)，k为返回元素数 O(k log n)
并发实现 简单 复杂
缓存友好性 一般 较好

没有完美的方案。如果你的场景需要严格的最坏情况保证，红黑树是正确选择。如果你的场景有大量范围查询或需要高并发，跳表更合适。如果你只是需要一个简单的有序字典，跳表的代码量可能只有红黑树的三分之一。

William Pugh在论文结尾写道：“从理论角度看，跳表是多余的。平衡树能做跳表能做的一切，而且有更好的最坏情况保证。但从实践角度看，跳表是一个足够简单、足够快、足够可靠的数据结构。”

三十多年后的今天，Redis、LevelDB、RocksDB、Java并发包的选择证明了这句话的预见性。有时候，放弃对"完美"的执念，拥抱"足够好"，反而是工程智慧的体现。

参考资料

  1. Pugh, W. (1990). Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM, 33(6), 668-676.
  2. Redis Sorted Set Implementation. GitHub Repository.
  3. LevelDB Source Code: db/skiplist.h.
  4. RocksDB Wiki: MemTable.
  5. Papadakis, T. (1993). Skip Lists and Probabilistic Analysis of Algorithms (Ph.D. thesis). University of Waterloo.
  6. Fomitchev, M., & Ruppert, E. (2004). Lock-free linked lists and skip lists. PODC ‘04.
  7. Sedgewick, R. (2008). Left-leaning red-black trees. Draft.
  8. Java ConcurrentSkipListMap Source Code. OpenJDK.
  9. Discord Blog (2019). Using Rust to Scale Elixir for 11 Million Concurrent Users.