跳表（Skip List）深度实战：从随机层数、概率平衡到 Redis zset 与 LevelDB MemTable 的工程全解
跳表（Skip List）是 1989 年 William Pugh 在论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》里提出的一种概率性平衡的有序数据结构。它要解决的，是平衡二叉搜索树（AVL、红黑树、B 树）在工程里一个长期被忽视的痛点：为了维持"平衡"，它们不得不在每次插入删除时做复杂的旋转（rotation）或再平衡（rebalance），代码晦涩、并发改造地狱、调试时极难追踪一棵树为何失衡。跳表用一种近乎"耍赖"的方式绕开了这个问题——它不做任何显式平衡，而是靠随机层数让结构"以概率的方式"趋向于平衡，平均查找复杂度仍是 O(log n)，但实现只有二叉平衡树的零头。
这就是为什么今天我们能在 Redis 的有序集合（zset）、LevelDB/RocksDB 的内存表（MemTable）、Lucene 的倒排索引跳表、Java 的 ConcurrentSkipListMap、Linux 内核的 intervals 区间管理里反复看到它。本文从第一性原理出发，推导随机层数的概率保证，给出可插拔的工业级实现，并系统梳理它与平衡树的工程取舍、并发改造路径、以及在主流存储引擎里的落地形态与 12 项生产陷阱。
一、第一性原理：有序动态集合的困境
一个需要频繁插入、删除、按 key 查找、按范围扫描的有序动态集合，朴素做法有两种，却各有硬伤：
- 有序数组：二分查找 O(log n) 很香，但插入/删除要搬移元素，退化成 O(n)。
- 有序链表：插入/删除 O(1)（找到位置后改两个指针），但查找只能从头遍历，O(n)。
平衡二叉搜索树（BST）把两者统一到 O(log n)，代价是再平衡逻辑复杂。Pugh 的核心洞察是：能不能给链表"加几层快速通道"，使得查找时可以大步跨越，又不必为维持平衡而旋转？ 跳表就是答案——它把"有序链表"复制成若干层，越往上的层节点越稀疏，查找时从最稀疏的顶层开始，能跳就跳，跳不过去再下潜一层，最终在底层精确命中。
关键直觉：跳表不保证最坏 O(log n)，只保证期望 O(log n)，但失败概率随层数指数衰减。在工程上，"以 1/2 概率维持平衡"比"以复杂旋转强制维持平衡"便宜太多，且对并发友好——这正是它被工业界大量采用的根本原因。
二、结构定义：多层链表与"快速通道"
跳表由若干层有序链表叠加而成，每一层都是底层（第 0 层）的一个"稀疏子集"：
- 第 0 层：包含所有节点，是完整的有序链表。
- 第 1 层：包含约 1/2 的节点，是在第 0 层上"隔一个取一个"。
- 第 2 层：包含约 1/4 的节点，依此类推。
- 顶层：节点极稀疏，是快速通道的最高速档。
每个节点持有一组向右的 forward 指针（每层的下一个节点），以及可选的向下的指针（或按层数组组织）。头节点（head）拥有指向每一层起点的指针。一个典型的节点表示：
import random
from typing import Optional, List
class SkipNode:
__slots__ = ("key", "value", "forward")
def __init__(self, key, value=None, level=1):
self.key = key
self.value = value
# forward[i] 指向第 i 层的下一个节点；层号从 0 开始
self.forward: List[Optional["SkipNode"]] = [None] * level
结构示意（数字为 key，箭头表示同层 forward 指针）：
第 3 层: head ──────────────────────────────► 7 ──► NIL
第 2 层: head ──────────► 3 ────────────────► 7 ──► NIL
第 1 层: head ──► 1 ──► 3 ──────► 6 ────────► 7 ──► NIL
第 0 层: head ──► 1 ──► 3 ──► 4 ──► 6 ──► 7 ──► 9 ──► NIL
查找 9 时：第 3 层直接到 7（9 在 7 之后，本层到头）→ 下潜；第 2 层从 7 出发到 NIL → 下潜；第 1 层从 7 出发到 NIL → 下潜；第 0 层从 7 遍历到 9，命中。原本要 6 步的链表遍历，被压缩成 4 次"跨层 + 小步前进"。
三、随机层数：一枚硬币与几何分布
跳表的灵魂是随机层数（random level）。插入一个新节点时，不人为决定它出现在哪几层，而是反复抛一枚公平硬币（p = 1/2），正面就升一层，直到反面或达到上限 MAX_LEVEL：
def random_level(self, p: float = 0.5, max_level: int = 16) -> int:
level = 1
while random.random() < p and level < max_level:
level += 1
return level
这意味着一个节点出现在第 k 层（k ≥ 1）的概率是 (1-p)·p^(k-1)——典型的几何分布。于是：
- 约 1/2 的节点在第 0 层之上还出现 1 次（第 1 层）；
- 约 1/4 出现在第 2 层；
- 约 1/2^k 出现在第 k 层。
这种自相似的稀疏性，正是查找能"指数跨越"的概率基础。MAX_LEVEL 的选取取决于预期节点数 n：MAX_LEVEL ≥ log_{1/p}(n) 即可让最高层几乎不会浪费。对 n = 2^32 取 p=1/2，MAX_LEVEL = 32 绰绰有余；Redis 用 32，LevelDB 用 12（因其 MemTable 规模有限）。
致命细节：随机层数必须基于每次插入独立抛硬币，绝不能"固定每第 2^k 个节点升层"。后者会退化成确定性的静态结构，一旦插入顺序有偏（比如 key 单调递增），平衡性立刻崩塌。随机性不是装饰，是正确性的前提。
四、查找：从顶层俯冲而下
查找的核心是先"尽量在高层跳"，跳不过去就下潜。最关键的是：在每一层都要先停在当前能到达的最远节点，再决定下潜还是右移——不能在某一层一口气冲到底再统一下潜，否则会错过更上层能提供的跨越机会。标准实现返回"查找路径上每一层的前驱节点"，供插入/删除复用：
def _search(self, key):
"""返回 update[]：每层最后的小于 key 的节点（前驱），以及是否命中。"""
update = [None] * self.level
x = self.head
for i in range(self.level - 1, -1, -1): # 从最高层往下
while x.forward[i] is not None and x.forward[i].key < key:
x = x.forward[i]
update[i] = x # 第 i 层的前驱
x = x.forward[0] # 落到底层，看是否精确命中
found = x is not None and x.key == key
return update, x if found else None
查找路径天然给出"插入时新节点该接在谁的后面"。注意循环条件用 < key（严格小于），把"等于"留给最后一步精确判定，避免重复key在多层被错误处理。
五、插入：先搜后插，逐层掷硬币
插入 = 先 _search 拿到每层的 update 前驱 + 随机层数；若层数超过当前跳表高度，先把 head 在新增的层上接到现有最高节点；再把新节点像普通链表一样挂到每一层的 update[i] 之后：
def insert(self, key, value):
update, node = self._search(key)
if node is not None:
node.value = value # 已存在则更新 value，不重复插入
return
new_level = self.random_level(self.p, self.max_level)
if new_level > self.level:
for i in range(self.level, new_level):
update[i] = self.head # 新层的前驱统一是 head
self.level = new_level
new = SkipNode(key, value, new_level)
for i in range(new_level):
new.forward[i] = update[i].forward[i]
update[i].forward[i] = new
self.size += 1
这里有一个常被忽略的点：当 new_level > self.level 时，新增层的 update[i] 必须指向 head，因为新层上目前只有 head 和（可能）少量高层节点，新节点应当成为该层 head 后的第一个节点。漏掉这一步会让新增层形成悬空指针。
六、删除：逐层摘除与内存回收
删除与插入对称：先 _search；若命中，从第 0 层到第 (node.level-1) 层依次把 update[i].forward[i] 从指向 node 改回 node.forward[i]，逐层"绕过"被删节点；最后若最高几层被清空，要下调跳表高度 self.level，否则查找会空转在全是 head→NIL 的空层：
def delete(self, key):
update, node = self._search(key)
if node is None:
return False
for i in range(node.forward.__len__()):
if update[i].forward[i] is not node:
break # 更高层本就没有指向 node，提前结束
update[i].forward[i] = node.forward[i]
while self.level > 1 and self.head.forward[self.level - 1] is None:
self.level -= 1 # 收缩空层，避免查找空转
self.size -= 1
return True
内存视角：在 C/C++/Rust 里删除节点后必须显式
free/drop，否则内存泄漏；在带 GC 的语言里虽无泄漏，但跳表高度若不及时收缩，会让后续每次查找都白走若干空层，累积成可观的尾延迟。
七、复杂度推导：为什么期望 O(log n)
设 L 为单个节点的层数，则 P(L ≥ k) = p^(k-1)（从 1 层起算），期望层数 E[L] = 1/(1-p)。取 p = 1/2，期望层数 2；取 p = 1/4，期望层数 4/3。
查找的代价等于"遍历过的节点数"。Pugh 证明：在含 n 个节点的跳表里，一次查找期望访问的节点数为 O(log_{1/p} n)，具体是 (1/p)·log_{1/p} n + O(1)。直觉证明（反向视角）：从目标节点沿 forward 往回走，每一步"上跳一层"的概率约 p，"平走一步"的概率约 1-p，于是从目标回到 head 的期望步数 ≈ 在几何游走里的反向步数，量级正是 log_{1/p} n。
同时，跳表的最大高度 max_level 期望为 O(log_{1/p} n)（n 个节点各自独立抛硬币，最高者层数近似 log_{1/p} n + 常数），这意味着查找的层数循环本身也是 O(log n)。综合两层，插入、删除、查找的期望时间复杂度均为 O(log n)，且空间复杂度为 O(n)（期望节点指针总数 = n·E[L] = n/(1-p)，即常数倍于 n）。
这是期望界而非最坏界：理论上存在"每次都抛到 MAX_LEVEL"的极小概率坏情况，但概率 ≤ p^(MAX_LEVEL)，在工程参数下（如 p=1/2, MAX_LEVEL=32）约为 2^-32，比硬件比特翻转还罕见，可忽略。
八、可插拔工业级 Python 实现
把上述拼装成一个可直接落地的工具类，覆盖查找、插入、删除、范围扫描：
class SkipList:
def __init__(self, p: float = 0.5, max_level: int = 16):
self.p = p
self.max_level = max_level
self.level = 1
self.size = 0
self.head = SkipNode(None, None, max_level) # 哨兵，key=None 永不命中
def _search(self, key):
update = [None] * self.max_level
x = self.head
for i in range(self.level - 1, -1, -1):
while x.forward[i] is not None and x.forward[i].key < key:
x = x.forward[i]
update[i] = x
x = x.forward[0]
return update, (x if x is not None and x.key == key else None)
def random_level(self):
lvl = 1
while random.random() < self.p and lvl < self.max_level:
lvl += 1
return lvl
def insert(self, key, value=None):
update, node = self._search(key)
if node is not None:
node.value = value
return
lvl = self.random_level()
if lvl > self.level:
for i in range(self.level, lvl):
update[i] = self.head
self.level = lvl
new = SkipNode(key, value, lvl)
for i in range(lvl):
new.forward[i] = update[i].forward[i]
update[i].forward[i] = new
self.size += 1
def delete(self, key):
update, node = self._search(key)
if node is None:
return False
for i in range(len(node.forward)):
if update[i].forward[i] is not node:
break
update[i].forward[i] = node.forward[i]
while self.level > 1 and self.head.forward[self.level - 1] is None:
self.level -= 1
self.size -= 1
return True
def range_query(self, lo, hi):
"""[lo, hi] 闭区间范围扫描，O(log n + k)。"""
_, _ = self._search(lo)
# 从 lo 的底层前驱出发，沿第 0 层前进
x = self.head
while x.forward[0] is not None and x.forward[0].key < lo:
x = x.forward[0]
x = x.forward[0]
out = []
while x is not None and x.key <= hi:
out.append((x.key, x.value))
x = x.forward[0]
return out
该实现用哨兵 head（key=None）统一边界，避免每处判断 head 是否为空；range_query 给出跳表相对平衡树的一大卖点——范围扫描天然 O(log n + k)，无需中序遍历整棵子树。
九、与平衡树的工程对比
| 维度 | 跳表 | 红黑树 / AVL / B 树 |
|---|---|---|
| 平均查找 | O(log n) 期望 | O(log n) 最坏 |
| 插入/删除 | 改若干指针，无旋转 | 旋转/分裂合并，逻辑复杂 |
| 范围扫描 | O(log n + k) 极简 | 中序遍历，需迭代器状态 |
| 代码量 | 数十行，易写对 | 数百行，易写错 |
| 并发改造 | 分层加锁/无锁CAS友好 | 旋转使锁粒度极难做细 |
| 缓存局部性 | 节点分散，较差 | B 树节点紧凑，较好 |
| 最坏保证 | 仅期望（概率极高） | 严格最坏 |
| 典型落地 | Redis zset、LevelDB、Lucene、JUC | 内核、数据库索引、语言运行时有序容器 |
结论很清晰：当场景需要高并发写入、范围扫描、且能接受"期望而非最坏"的复杂度时，跳表几乎总是更优的工程选择；当需要严格最坏界或极致缓存局部性（如数据库磁盘页），平衡树/B 树仍不可替代。二者不是替代关系，是分工关系。
十、并发跳表：从粗锁到无锁 CAS
单线程跳表进了生产第一件事就是并发。改造难度远低于平衡树，因为跳表没有"旋转"这种会波及整棵结构的操作——一次插入只动 new_level 个局部指针。
方案 A：全局粗锁。 最简单，insert/delete/search 全加一把互斥锁。正确但吞吐随核数线性下降，只适合低并发。
方案 B：细粒度分层锁。 借鉴"hand-over-hand locking"：从顶层往下探路时，持有当前层节点的锁再去看下一层，释放上层锁。能把锁冲突面压到局部，但实现繁琐、易死锁。
方案 C：乐观无锁（CAS）。 工业主流。以 Java ConcurrentSkipListMap 为范本：
- 查找用纯读（无锁），找到目标层的前驱/后继；
- 插入时，先用 CAS 把新节点"挂"到最底层（
pred.casNext(null, newNode)），再用 CAS 逐层把上层 forward 指过去；任何一层 CAS 失败就重试整个插入（帮助完成别人正在做的操作）； - 删除用逻辑删除（mark node as deleted）而非立刻物理摘除：先把节点 marked，再把 forward 指针绕过它，最后由后续操作惰性回收，避免"正在读这个节点的线程突然看到指针消失"的 ABA/悬垂问题。
并发跳表的最大坑是 "查找路径在插入期间失效"：你探路时记录的前驱，可能在你 CAS 之前被别的线程删了。解决方案是"帮助式重试"——一旦发现前驱变了或已被 mark，就重跑
_search。这是无锁跳表正确性的核心，绝不能偷懒用全局锁糊弄。
十一、工业落地：从缓存到存储引擎
跳表不是学院玩具，而是藏在无数基础设施里的主力：
- Redis 有序集合（zset）： 当元素较多或含大 score 时，zset 底层由
listpack/ziplist切换为 skiplist + dict 的双结构——dict 提供 O(1) 按成员查 score，skiplist 提供 O(log n) 按 score 排序与ZRANGE/ZREVRANGE范围扫描。Redis 的 skiplist 还额外维护一个反向回溯指针（backward），支持从尾到头的逆序遍历。 - LevelDB / RocksDB MemTable： 内存中的可变有序表，所有写入先落 MemTable（skiplist 实现），
Get与区间Iterator都依赖它 O(log n + k) 的特性；MemTable 写满后整体冻结、转储为 SSTable。LevelDB 用MAX_LEVEL=12, p=1/4（期望层数 4/3），契合内存表规模。 - Lucene / Elasticsearch 倒排索引： 用跳表加速
nextDoc()/advance()等术语词典（Term Dictionary）的跳跃，使skipTo不必线性扫描。 - Java
ConcurrentSkipListMap/ConcurrentSkipListSet： JUC 里唯一支持高并发的有序 Map 实现，内部即无锁乐观跳表。 - Linux 内核：
mm/pagewalk、interval tree等区间管理里能看到跳表思想变种，用于稀疏区间的快速定位。
这些落地的共性：需要有序 + 高并发写 + 范围扫描，且工程团队不想维护一棵会旋转的树。
十二、12 项生产陷阱
- 随机层数与插入顺序耦合： 用"每 2^k 个升层"代替抛硬币，遇到单调递增 key 直接退化成链表。
- MAX_LEVEL 选太小： 大数据量下最高层几乎为空，查找被迫走底层，退化为 O(n)。
- 插入新层忘了把 update[i] 设为 head： 新增层形成悬空指针，后续查找在高层迷路。
- 删除后不收缩 level： 空层越积越多，每次查找都白走若干层，尾延迟悄悄上升。
- 用递归 find 导致爆栈： 深链场景下递归路径压缩/查找触发
RecursionError（Python 默认 1000）。 - 并发下前驱失效未重试： CAS 插入前前驱被别人删除/标记，不重跑
_search会写坏结构。 - 逻辑删除后物理回收时机错误： 过早 free 被其他线程持有的节点，造成悬垂指针（use-after-free）。
- p 取值与业务访问模式错配： 读多写少用大 p（更扁、查找更快）；写多读少用小 p（更省空间）。
- score 相等时的 tie-break 缺失： 有序集合里 score 相同必须再按 member 字典序二级排序，否则去重/排序语义错误。
- 范围扫描没从 lo 前驱出发： 直接从 head 走会漏掉边界，或重复遍历。
- 内存碎片： 每个节点独立分配、层数不定，长期高频增删产生碎片；C++ 可用节点池/内存池缓解。
- 把"期望 O(log n)"当"最坏 O(log n)"： SLA 极严苛的场景需配监控，警惕那 2^-32 概率的坏情况被硬件噪声放大。
十三、结语
跳表是"用概率换简单"的教科书级范例：它放弃了平衡树那种"每次都强制最优"的执念，转而用一枚硬币换取几乎总是最优，换来的是数十行就能写对、并发改造轻松、范围扫描天然的工程友好性。它与本站已发布的布隆过滤器、Count-Min Sketch、HyperLogLog、布谷鸟哈希、并查集、Trie、基数树、线段树/树状数组、KD-Tree、堆、单调栈、快速/归并排序共同构成"数据结构工程全谱系"——前者以概率与近似换空间与速度，后者以确定性换精确，二者在工程栈里互补共存。下一步可继续补全 B+ 树、LSM-Tree 合并策略、以及跳表在持久化内存（PMEM）下的失效排序（persistency）改造，把"有序动态集合"这条主线彻底打通。
发表评论 取消回复