树系列第 15 篇：跳表——概率平衡的层级结构

本文是“树系列”的第 15 篇。第 8 篇我们讨论过平衡的必要性：一颗普通的二叉搜索树在数据有序插入时会退化成链表，查找从 O(log n) 变成 O(n)；第 13 篇我们通过 B 树看到了“层数变少”的直觉：一棵树只有矮，查找才快。今天我们要聊的主角是跳表（Skip List）。它没有“旋转”，没有“变色”，甚至没有严格意义上的“平衡”操作，它只靠一枚硬币，就把结构维持在“大概率平衡”的状态。它不是树，却和树分享同一个灵魂：用层级结构缩短查找路径。

0. 从第 8 篇和第 13 篇出发：我们想要什么

先快速回顾一下前两篇留给我们的两个问题。

第 8 篇告诉我们：二叉搜索树的性能完全取决于树高。如果插入顺序恰好是有序的，每次插入的新节点都会挂在最右边，树高变成 n，查找退化成从头到尾的遍历。为了解决这个问题，AVL 树发明了旋转：每当左右子树高度差超过 1，就通过一次或两次旋转把树“扶正”。红黑树则用颜色约束路径长度，让最长路径不超过最短路径的两倍。这些方案都很聪明，但它们都有一个共同点：为了保持平衡，每次插入和删除之后都要执行额外的工作，旋转、重染色、回溯祖先，代码写起来不轻松，出错的可能性也随之增加。

第 13 篇给我们看了另一条路：B 树通过增加每个节点的分支数来降低树高。同样是一百万个键，二叉搜索树需要大约 20 层，而一棵 100 阶的 B 树只需要 3 到 4 层。为什么？因为“层数 = 走多少步”的直觉在树里是成立的：每一层是一段必须经过的旅程，层数越少，旅程越短。但 B 树的每个节点能装很多键，这要求节点内部有一定程度的顺序存储，在内存场景下反而可能带来额外的比较成本。

把两个问题合并在一起，我们想要的东西就很清楚了：

第一，我们要一种有序的结构，能够高效支持查找、插入、删除、求前驱后继、区间遍历；

第二，我们不想在每次插入删除后都费劲地做“修复平衡”的工作；

第三，我们希望结构足够简单，简单到哪怕出 bug 也容易排查，简单到在多线程环境里也容易加锁。

跳表给出了一个令人惊讶的回答：把有序链表多铺几层“快车道”，然后用抛硬币来决定每个节点出现在哪些层。实现它只需要几十行代码，却能在期望意义上做到 O(log n) 的查找、插入和删除。

1. 问题：有序链表的查找为什么是 O(n)

让我们从最朴素的数据结构开始：一条有序链表。

假设我们有一个存储整数的有序链表，键值从小到大排列：1、5、12、23、38、44、50、67、81、99。链表的每个节点除了保存数据之外，只保存一个指向下一个节点的指针。这是一个非常节俭的结构：插入一个新节点只需要找到正确的位置、改两个指针，删除一个节点也只需要把前驱的指针绕过它。

但代价是什么呢？代价是查找。要判断 67 在不在链表里，我们只能从 1 开始，沿着指针一个节点一个节点地往后走：1 → 5 → 12 → 23 → 38 → 44 → 50 → 67。找到 67 需要走 8 步。如果找 99，就需要走完整个链表。平均下来，查找一个随机键要走 n/2 步，最坏要走 n 步。用大 O 记号表达：有序链表的查找是 O(n)。

上面这张图里，橙色节点 67 是我们要找的目标，灰色节点是查找途中必须经过的节点。注意一个细节：每个节点都长着同样的“脸”，提供的信息量完全一样，我们没有任何“跳过中间节点”的办法。

那么，数组呢？数组支持二分查找：把 67 和中间元素比较，一次就能排除一半。但数组的插入和删除很痛苦——在有序数组中间插入一个元素，需要把后面所有元素整体后移，平均移动 n/2 个元素，是 O(n) 的代价。如果插入和删除频繁发生，数组的“搬移税”会非常可观。

所以矛盾出现了：

操作	有序数组	有序链表
查找	O(log n)（二分）	O(n)（只能线性走）
插入	O(n)（搬移元素）	O(1)（知道位置后）
删除	O(n)（搬移元素）	O(1)（知道位置后）
内存	连续、紧凑	分散、每节点带指针

数组赢在查找，链表赢在插入删除。我们能不能设计一个结构，同时拿到两边的优点：像链表一样插入删除便宜，又像数组二分一样查找便宜？

很多人第一反应是：链表不能随机访问，所以没法二分。这个结论本身没错，但它的前提是“链表只有一层”。如果一条链表有好多层，高层指针可以一次跳过大量节点，我们不就变相获得了“跳着访问”的能力吗？

这就是跳表想法的起点。与其在树的形态上继续打转，不如回到链表，给它装上“快速通道”。

1.1 复杂度之外的现实约束

在继续往下走之前，值得先停下来问一个问题：既然数组和链表各有优缺点，我们为什么不能简单地说“数组二分 + 链表插入”呢？

答案在于，真实程序从来不是只做一个操作。一个典型的有序容器使用模式是：插入一批数据，然后反复查询，偶尔删除，时不时还要按范围扫描。如果只盯着“单次查找”的复杂度，数组似乎是赢家；但如果把“插入时搬移 n 个元素”的成本摊到整个生命周期里，数组很快就会拖垮整体性能。同理，如果只看“插入 O(1)”，链表似乎完美，但查找 O(n) 会让每一次查询都变成灾难。

更隐蔽的问题是内存和实现成本。数组二分需要一个支持随机访问的连续内存区域，数据量大了以后，连续分配本身就可能失败；链表虽然不需要连续内存，但每个节点都要多存一个指针，遍历时还要频繁跳转，缓存命中率不高。跳表之所以有意义，不是因为它在单一指标上碾压两者，而是因为它在“查找、插入、删除、范围遍历、内存占用、实现难度”这六个维度上都没有明显短板。

还有一个常被忽略的工程因素：代码的维护成本。平衡树实现中旋转方向搞反、父指针更新遗漏，都是极难排查的 bug；跳表的核心循环只有十几行，任何有链表基础的程序员都能读懂。在很多公司里，“三个月后接手的人能不能改对”比“常数因子快 20%”重要得多。这也是为什么跳表能从一个 1989 年的论文结构，走进 Redis、LevelDB 和 Java 标准库。

2. 直觉起源：给链表加“快速通道”

2.1 第一层加速：每隔一个节点放一个快捷指针

想象一条普通的有序链表：1 → 5 → 12 → 23 → 38 → 44 → 50 → 67 → 81 → 99。现在，我们做一个实验：给链表增加一条“快车道”，这条快车道上只有每隔一个节点的那些节点，并且每个快车道节点都保存一个“跳过下一个节点”的指针。

也就是说，除了原始的底层指针（每个节点指向它的直接后继），我们再给 1、12、38、50、81 这几个节点各加一个“二倍速”指针：1 → 12 → 38 → 50 → 81，一次跳两个节点。

查找 67 的时候，我们可以先在快车道上走：1 → 12 → 38 → 50。下一个快车道节点是 81，已经超过 67，说明 67 不在快车道节点里，肯定落在 50 和 81 之间的“缝隙”里。于是我们降回底层，从 50 往后走：50 → 67，两步命中。

算一下总步数：快车道上走了 3 步（1→12→38→50），底层走了 2 步（50→67），一共 5 步，比原来从 1 一路走到 67 的 8 步少。虽然看起来只省了一点点，但请注意：链越长，省得越多。如果链表有一百万个节点，快车道可以把步数从一百万减到五十万，这依然不够好，但方向是对的。

2.2 第二层加速：再加一层快车道

既然一层快车道有用，为什么不再加一层？

我们在“二倍速快车道”的基础上，再挑一半节点出来，组成一条“四倍速快车道”：1 → 38 → 81。现在查找 67 的路径变成：在最高层从 1 走到 38，下一个是 81，超过 67，于是下降到第二层；第二层从 38 往后是 50，还没有超过 67，继续走到 50；再下一个是 81，超过目标，下降到底层；底层从 50 走到 67，命中。

步数统计：最高层 1 步（1→38），第二层 2 步（38→50 及比较发现 81 过大），底层 2 步（50→67），一共约 5 次指针移动和若干次比较。对于这个只有 10 个节点的例子，改善有限，但你可以想象：每加一层，能跳过的节点数就翻一倍。一层跳 2 个，两层跳 4 个，三层跳 8 个……如果层数足够多，一次跳跃覆盖的范围可以和“二分查找每次排除一半”相媲美。

2.3 理想跳表：一座“节点金字塔”

如果每一层的节点数都恰好是下一层的一半，而且高层节点均匀地散布在整个链表上，我们就得到了一座完美的“节点金字塔”：

在这座金字塔里，查找就像坐电梯：先在最高层快速向右“飞”，快到目标时下降一层继续飞，最后落到地面上精确地走到目标。每一层都把搜索区间缩小一半，整个过程和二分查找的“每次排除一半”一模一样，只是载体从连续内存变成了多层链表。

2.4 问题来了：谁来决定每个节点的层数

理想跳表看起来很美，但仔细一想就会发现一个麻烦：节点的层数不能提前静态定好。如果按“第 k 个节点出现在第 log n 层”这样的规则安排，那么插入一个新节点时，它后面的所有节点都要重新安排层数，等价于把整条链表重建一遍，插入又变回 O(n) 了。

所以我们换一个思路：不追求“精确的完美金字塔”，而是给每个节点随机决定它出现在哪些层。比如抛硬币，正面就让节点多长一层。绝大多数节点只有底层，一部分节点有两层，更少一部分有三层、四层。从整体期望来看，每一层大约保留下一层一半的节点——结构不是被“计算”出来的，而是被“抛”出来的。我们放弃了确定性，换来了插入删除的简单，这就是跳表的核心哲学。

在进入查找和插入的细节之前，先把完整结构说清楚。

2.5 参数 p：为什么是 1/2，也可以是 1/4

前面一直假设“每层保留下一层一半的节点”，这个“一半”就是概率参数 p = 1/2。但 p 并不是只能取 1/2，它可以是任何 (0, 1) 之间的数，常见取值还有 1/4 和 1/3。

p 的取值背后是一个清晰的空间换时间权衡：

p 越小，节点长到高层的概率越小，整张表的平均层数越低，指针总量越少，内存越省；但每一层里相邻两个高层节点之间隔着更多底层节点，查找时在同一层内需要向右走的期望步数就变多。

p 越大，高层节点越多，每次跳跃覆盖的跨度越大，层内步数变少；但每个节点平均占的层数变多，指针总量上涨。

把这两股力量放在一起，可以得到一个经典结论：期望查找代价大约正比于 (1/p) × log_{1/p} n。代入 p = 1/2，得到 2 × log₂ n；代入 p = 1/4，得到 4 × log₄ n。把对数换底算一下会发现，两个表达式的常数因子其实非常接近，也就是说，把 p 从 1/2 调成 1/4，期望查找时间几乎不变，但每个节点的平均指针数从 2 降到约 1.33，内存省了约三分之一。这就是 Redis 把 p 定为 1/4 的原因：在几乎不损失速度的前提下，节省可观的内存。

值得一提的是，p 的选择还影响“最大层数”的期望：p = 1/2 时约 log₂ n，p = 1/4 时约 log₄ n。层数少，意味着查找时“下降”的次数少，但每一层的“横向滑动”次数多；反之亦然。它们互相补偿，最终的总步数在常数级别上差别不大。理解了这层关系，你在设计自己的跳表时就不会盲目照抄参数，而是能根据“内存贵还是时间贵”做出选择。

3. 跳表的完整结构：多层有序链表

3.1 从“节点”到“塔”

在普通链表里，一个节点只有一个“后继指针”。在跳表里，一个节点可以有多个“后继指针”，每个指针属于不同的层。如果一个节点出现在第 0 层、第 1 层和第 2 层，我们就说它是一个“高度为 3 的塔”，它内部保存着一个长度为 3 的指针数组：forward[0] 指向第 0 层的后继，forward[1] 指向第 1 层的后继，forward[2] 指向第 2 层的后继。

注意：同一个节点的不同层指针可以指向不同的后继。比如在上面的示意图里，第 2 层的指针可以从 50 直接跳到 81，而第 0 层的指针只能一步一步走到 67。这没有任何矛盾，因为每一层本来就是一条独立的有序链表，只是共享同一批节点而已。

3.2 四要素：底层全量、高层子集、哨兵头、层数上限

一个标准跳表由四个部分构成：

第一，底层（第 0 层）必须包含全部节点。这是跳表正确性的根基：无论查找时从哪一层下来，最后总能回到一条包含所有节点的完整链表，因此任何键都不会“漏掉”。

第二，第 k 层是第 k−1 层的一个子集（在理想情况下大约一半）。高层节点永远同时也是低层节点，不存在“某个节点只在第 3 层、不在第 0 层”的情况。

第三，头节点（哨兵）。跳表需要一个不保存实际数据的头节点，它出现在所有层，作为每一层链表的起点。头节点扮演两个角色：一是给查找提供统一的起点，二是让“插入在链表最前面”和“删除链表第一个节点”这两类边界操作不需要特殊判断。头节点的键可以想象成负无穷，任何真实键都比它大。

第四，层数上限 maxLevel。我们不可能让节点无限长高，所以会设置一个上限，比如 32。只要元素数量不超过 2^32 这个量级，32 层就绰绰有余。后面讲工程实现时我们再细说怎么选这个值。

在这张图里，头节点同时是四条链表的起点。你可能注意到：图上所有高层指针都用虚线表示，底层用实线表示。这是跳表示意图的通用画法——高层是“快车道”，底层是“地面公路”。

3.3 跳表与树的对应关系：它不是树，但胜似树

跳表明明不是树，为什么放在“树系列”里讲？因为它的本质结构和树高度相似，只是把树的“节点+左右孩子”重新组织成了“节点+多层后继”。

一棵二叉搜索树，从上往下看，每一层只有一部分节点；从下往上看，最底层的“叶子们”按中序遍历恰好组成一个有序序列。跳表也一样：第 0 层就是那个完整的有序序列（相当于把所有节点按中序展开），第 1 层是序列中抽出的“代表节点”，第 2 层又从第 1 层抽出代表。每一层相当于二叉搜索树的某一层截面，越往上节点越少，越接近树的顶部。

还可以换个角度看：把每个节点的 forward 指针数组竖起来，节点就变成了一座塔；塔与塔之间按层连接。如果把“层”当作“深度”的镜像，跳表就是一棵倒过来画的树——树的根在最高层，叶子在底层。

树里每个节点有“左子树、右子树”，跳表里每个节点有“前驱、后继”；树靠旋转保持平衡，跳表靠概率保持平衡。理解了这层对应关系，你以后读任何跳表源码时，都可以在心里把 forward 数组翻译成“右指针们”，把“下降一层”翻译成“进入子树”。

3.4 把结构翻译成人话：三层楼的图书馆

如果上面的图和术语让你有点晕，试试这个生活化的类比。

想象一座三层楼的图书馆。第一层（底层）书架上按书名排满了所有书，一本书紧挨着一本书；第二层只有一部分“重点书”，每本重点书之间隔着一本普通书；第三层只放最经典的几本“镇馆之宝”。

你手里有一张借书单，要找一本叫《跳表入门》的书。你不会从第一层第一本开始一本一本找，而是直接上三楼：三楼的书少，一眼就能看到《数据结构基础》，再往后看《算法导论》——按字母序，《跳表入门》应该在这两本之间，于是你下到二楼；二楼在这两本之间放着《算法竞赛入门》《跳表入门》……你一眼看到了目标，直接下到一楼把它抽出来。

这座图书馆的“楼层”就是跳表的“层”，“三楼的书”就是高层节点，“下到二楼”就是下降一层。图书馆永远保证：越高的楼层书越少，但一楼永远有全部的书。这样找书时，你既能借助高层的“远眺”快速缩小范围，又不会因为高楼层的书不全而漏掉目标。

这个类比还解释了为什么跳表适合“范围查询”：如果你想把《数据结构基础》到《算法导论》之间的所有书都借出来，只需要在底层沿着书架从第一本一直走到最后一本，中间经过的每一本都是答案。树结构做同样的事需要反复“中序遍历找后继”，跳表只需要一次顺序遍历。

4. 查找：从最高层向右，太大就下降

4.1 查找算法的两条规则

跳表查找只有两条规则：

规则一：在当前层，只要下一个节点存在、并且它的键小于目标，就向右移动，移到下一个节点；

规则二：如果下一个节点不存在，或者它的键不小于目标，就下降一层。

一直重复到第 0 层。最后，第 0 层的“下一个节点”就是答案：如果它的键等于目标，查找成功；否则目标不在表中。

为什么从最高层开始？因为最高层每走一步跨越的键最多，可以最快地把搜索区间缩小。为什么下降到下一层而不是返回？因为“下降”相当于承认“这一层已经走到尽头，目标只可能落在我和下一个节点之间”，而下一层包含了这一层所有节点，所以目标如果存在，一定还在我后面的区间里，不需要回头。

用伪代码写出来非常短：

def search(head, target, max_level):
    cur = head
    for level in range(max_level - 1, -1, -1):
        while cur.forward[level] is not None and cur.forward[level].key < target:
            cur = cur.forward[level]
    candidate = cur.forward[0]
    return candidate if candidate is not None and candidate.key == target else None

整个函数只有一个双重循环：外层从高到低走遍每一层，内层在一层内向右滑动。没有递归、没有回溯、没有复杂的终止条件。

4.2 完整走查：查找 67

我们用前面那张理想跳表走一遍查找 67。为了看得清楚，把路径拆成四个阶段。

阶段一：第 3 层（最高层）

从 HEAD 出发，先看第 3 层：1 < 67，向右；38 < 67，向右；再看 81 ≥ 67，不能再走了。此时我们知道了关键信息：67 一定在 38 和 81 之间。

阶段二：下降到第 2 层

带着“67 在 38 和 81 之间”这个信息，从 38 的第 2 层指针出发：50 < 67，向右；再下一个是 81，不小于 67，停止。区间缩小为“50 到 81 之间”。

阶段三：下降到第 1 层

从 50 的第 1 层指针出发：下一个是 81？不，第 1 层里 50 的后继其实也是 81（注意理想跳表的第 1 层只有 1、12、38、50、81）。但等等，这里要小心：这张图里第 1 层 50 的下一个节点是 81，直接比较发现 81 ≥ 67，停止并下降。为什么中间没有 67？因为 67 恰好不在第 1 层。这没问题，我们继续下降到第 0 层。

阶段四：第 0 层精确命中

第 0 层包含所有节点：50 的后继是 67，67 不小于 67，停止；然后检查第 0 层“下一个节点”，发现它的键正好等于 67，查找成功。整条路径是：HEAD(3层) → 1(3层) → 38(3层) → 38(2层) → 50(2层) → 50(1层) → 50(0层) → 67(0层)，一共走了 7 次指针移动，而普通链表从 1 走到 67 需要 7 次移动，看起来差不多？别急，这只是 10 个节点的玩具例子。当节点数量增长到百万级时，普通链表要走 50 万步，跳表只需要约 20 次指针移动加 20 次下降。

4.3 为什么不会错过目标

这是跳表正确性最核心的问题，值得停下来想清楚。

假设查找目标 x，算法在第 k 层停在了节点 p，原因是 p 的下一个节点 q 的键 ≥ x（或者 q 不存在）。此时我们能断言：x 如果存在，一定位于 p 之后、q 之前（含 q）。为什么？因为第 k 层是有序链表，p 之前的节点都小于 x（否则算法不会走到 p），而 q 是第一个不小于 x 的节点，所以 [p, q) 这个区间里不可能再有第 k 层的节点。

现在算法下降到第 k−1 层，从 p 继续。第 k−1 层包含第 k 层的所有节点，所以 q 在第 k−1 层也存在（除非 q 是链尾）。因此，从 p 在第 k−1 层的后继开始，一路向右，一定会在到达或超过 q 之前覆盖 [p, q) 区间里的所有节点——x 如果存在于表中，它必然在这个区间里，也必然被经过。

用归纳法说：算法维护一个不变量——“当前节点 p 的键小于 x，且 x 只可能位于 p 的右侧区间”。初始时 p 是 HEAD，键为负无穷，整个链表都在右侧，不变量成立；每一层向右移动和向下下降都保持这个不变量；到达第 0 层后，不变量加上“第 0 层包含所有节点”，就保证了候选节点要么是 x，要么 x 不存在。这就是“不会错过目标”的严格证明，它完全不依赖节点层数的随机分布——哪怕随机数生成器质量很差，正确性也不受影响，受影响的只是速度。

4.4 动手体验

光看图可能还不够直观，你可以在下面的可视化实验室里亲手操作：选择“跳表”，观察查找时指针如何在层与层之间跳跃，也可以自己动手插入和删除节点，看看抛硬币的结果如何影响结构形状。

建议做一个实验：插入大约 30 个随机键，然后反复查找同一个目标，观察每次路径的层数分布。你很快会发现，大部分查找都只经过高层少数几次跳跃，真正在底层走的步数很少——这正是期望 O(log n) 的直观来源。

4.5 查找的边界情况：太小、太大、空表

走查一个“命中”的案例之后，再看三个边界情况，你会发现查找算法的终止条件天然处理了它们。

第一种，目标比所有键都小。比如表里最小的键是 1，要找 0。算法从最高层开始，第一个下一个节点就是 1，而 1 < 0 不成立，所以每一层都直接下降，最后在第 0 层停下，候选节点是 1，发现 1 ≠ 0，返回“不存在”。整个过程没有向右走一步，正确。

第二种，目标比所有键都大。比如表里最大的键是 99，要找 100。算法在每一层都会一路向右滑到链尾（下一个节点不存在），然后下降；在第 0 层滑到末尾后，候选节点是“空”，直接返回“不存在”。注意：即使高层在某个节点停了，下降后依然能从那个节点继续向右，直到每层都走到底，不会出现“卡在中间下不来”的情况。

第三种，空表。头节点的所有层都指向空。算法从最高层开始，第一眼就发现“下一个节点不存在”，于是逐层下降，最后在第 0 层候选为“空”，返回“不存在”。空表查找不需要任何特殊代码。

还有一个容易忽略的细节：查找过程永远不会“回头”。每一层都只向右移动，层与层之间只向下切换。这个“单调性”是查找时间复杂度分析的基础，也是跳表能轻松改成无锁并发读的原因——只读遍历不修改任何状态，多个读线程可以共享同一个结构而互不干扰。

4.6 查找的递归视角：同一个算法的另一种写法

把查找算法换一种写法，能帮你更深刻地理解它的本质。下面是递归版的思路：

search(cur, level, target)：如果 level 小于 0，检查 cur 的下一个节点是不是 target，返回结果；否则，如果 cur 在 level 层的下一个节点存在且键小于 target，就把 cur 移到那个节点，继续在同一层递归；否则，把 level 减一，继续递归。

这个递归的终止条件是“层数降到 -1”，代表我们已经在第 0 层完成了最终判断。仔细观察会发现，递归版和循环版做的动作完全一样，只是把“内层循环”变成了“同层递归”，把“外层循环”变成了“降层递归”。

递归视角的好处是能看清两个不变量：第一，进入任何一次递归时，cur 的键都严格小于 target；第二，target 如果存在，一定位于 cur 右侧的区间里。递归每次要么把 cur 向右推（区间左端右移），要么把 level 减一（进入更细的层次），无论哪一步，都不会丢失“目标在 cur 右侧”这个信息。所以递归必然终止，且结果必然正确。

真实的工程实现几乎都用循环而非递归，原因很朴素：递归需要函数调用栈，每一层下降都多一层栈帧，虽然深度只有 O(log n)，但函数调用的开销和栈溢出的风险都不如循环可控。理解递归写法，只是为了让你更清楚地看到算法的结构。

5. 插入：先查找定位，再抛硬币决定层数

5.1 为什么插入不能“直接连”

在普通链表中，插入只需要三步：找到前驱，把新节点的后继指向前驱的后继，再把前驱的后继指向新节点。跳表多了一个问题：新节点到底出现在哪些层？

如果只插入在第 0 层，跳表就退化成了普通链表，高层快车道永远等不到新节点，查找性能会随着插入次数逐渐变差。如果插入在全部层，那么每个新节点都成为最高层节点，金字塔结构被破坏，高层节点数量失控，查找同样退化。层数的选择，直接决定跳表的性能。

跳表的答案是一枚硬币：从第 1 层开始，每抛一次正面，就把节点的高度加一，直到抛到反面或达到 maxLevel 为止。也就是说：

节点出现在第 0 层的概率是 1（必须）； 出现在第 1 层的概率是 1/2； 出现在第 2 层的概率是 1/4； 出现在第 3 层的概率是 1/8； ……出现在第 k 层的概率是 2 的负 k 次方。

用公式表达：P(层数 ≥ k) = 2^−k。这是一条指数衰减的曲线：一半节点只有一层，四分之一节点有两层，八分之一节点有三层。平均下来，每个节点大约占 1/(1−1/2) = 2 层，也就是平均两个指针。

这棵“概率树”的每一层往右走，概率就乘以 1/2。注意这和平衡树的本质区别：没有任何“检查—修复”步骤。节点长多高，完全由随机数决定，插入操作不会因为“破坏了平衡”而做任何额外工作。

5.2 插入算法的完整步骤

插入一个键 x 分四步：

第一步，查找并记录每层的前驱。从最高层开始，用和查找完全相同的规则向右移动和下降，但每下降一层之前，把当前节点记入数组 update[level]。这个数组的含义是：新节点在第 level 层插入时，它前面紧挨着的节点是谁。这有点像在纸上记下“每一层我应该插在谁后面”。

第二步，抛硬币确定新节点的层数 new_level。如果 new_level 超过了当前跳表的层数，就把 head 的指针数组扩充到 new_level，并把多余层里 update[level] 指向 head 本身（因为新节点是这些层的第一个节点）。

第三步，创建节点，逐层链接。对于从 0 到 new_level−1 的每一层，执行：新节点.forward[level] = update[level].forward[level]；update[level].forward[level] = 新节点。这一步和普通链表的插入一模一样，只是要重复做多次。

第四步，更新跳表层数。如果 new_level 大于当前记录的最大层数，把最大值更新为 new_level。

def insert(head, target, max_level, rng):
    update = [None] * max_level
    cur = head
    for level in range(max_level - 1, -1, -1):
        while cur.forward[level] is not None and cur.forward[level].key < target:
            cur = cur.forward[level]
        update[level] = cur

    new_level = random_level(rng, max_level)
    if new_level > head.level:
        for level in range(head.level, new_level):
            update[level] = head
        head.level = new_level

    node = SkipNode(target, new_level)
    for level in range(new_level):
        node.forward[level] = update[level].forward[level]
        update[level].forward[level] = node

整个插入过程没有任何递归、没有旋转、没有重新染色，最复杂的部分只是那个 update 数组。

5.3 插入配图：插入 67（硬币结果：3 层）

假设当前跳表最高到第 3 层，我们要插入 67，而随机数给 67 分到了 3 层。

插入前，定位得到的每层前驱分别是：第 3 层是 38，第 2 层是 50，第 1 层是 50，第 0 层是 50。

插入后，67 这尊“三层塔”被逐层焊进链表：在第 0 层，50 的后继从 81 变成 67，67 的后继是 81；在第 1 层同理；在第 2 层，50 的后继变成 67；在第 3 层，67 没有指针，因为它只有 3 层，最高层是第 2 层（层号从 0 数起）。

仔细观察可以发现：插入只改动 update 数组里记录的那些节点的指针，其他节点完全不受影响。这就是链表式结构的最大优点——局部性。它不像数组插入要移动后半段，也不像平衡树可能要从叶子一路旋转到根。

5.4 重复键怎么办

真实世界里，键常常不是唯一的。跳表处理重复键有三种常见策略：

策略一，拒绝重复。查找时如果发现键已经存在，直接返回失败，不插入。这适合把跳表当集合（Set）用的场景，比如 ConcurrentSkipListSet。

策略二，允许重复。相同键的节点可以同时存在多个。此时查找要稍微改一下：内层循环的比较条件从“小于 target”改成“小于等于 target”，这样搜索会定位到一组重复键的最后一个（或第一个，取决于写法），删除时也只删一个。Redis 的有序集合就是这么干的：分数允许相同，成员按字典序排列。

策略三，键不重复但值可覆盖。把跳表当映射（Map）用，插入相同键时直接更新节点里保存的值。Java 的 ConcurrentSkipListMap 就是这样：键必须唯一，重复插入等于“更新”。

无论哪种策略，核心的层数机制都不变。重复键只影响“比较相等时怎么处理”，不影响跳表的结构和复杂度。

5.5 插入的复杂度与 update 数组的复用

插入操作的代价可以分成两部分：定位和链接。

定位阶段和查找一模一样，期望 O(log n) 次指针移动。链接阶段要做的事是：对每一层执行一次指针改写。新节点的层数期望是 1/(1−p)，p = 1/2 时是 2，但注意层数有概率长到 O(log n)，所以链接阶段的期望代价其实是“层数的期望上界”，也就是 O(log n)。把两部分加起来，插入的总期望代价就是 O(log n)。

很多人第一次写跳表时会对 update 数组感到困惑：为什么查找已经知道“最终前驱”了，还要每层都记一个？答案在于，查找结束时 cur 只停在某一层的某个节点上，而新节点要接入的层数可能远多于“cur 所在的层”。比如新节点被硬币决定了 10 层，但查找结束时的 cur 只停在第 0 层，如果没有提前记录第 1 层到第 9 层的前驱，链接时根本不知道该从哪个节点接出来。update 数组的本质，就是把查找路径上“每一层下降点”都留一个快照。

update 数组还有一个妙用：它天然支持“检查键是否已存在”。查找结束时，第 0 层的候选节点就是 update[0] 的下一个节点。如果它的键等于 target，说明重复，可以直接决定是拒绝、更新还是允许插入，而不需要再从头找一遍。这也是为什么 Redis 的 zslInsert 和 Java 的 ConcurrentSkipListMap 的 put 都把“查找 + 记录前驱”合并成一步。

最后想强调一个反直觉的事实：插入一个很高层的新节点，不会破坏其他高层节点的“稀疏性”。从局部看，它只是在每层插入了一个节点；从全局看，每层节点数只是增加了 1。随机过程保证的是长期统计性质：经过大量插入后，每层节点数仍然近似是下一层的一半，就像抛一万次硬币，正面比例稳定在 1/2 附近一样。不需要任何“修复”，统计规律自己会完成平衡。

6. 删除：定位后逐层摘除

6.1 删除的三步

删除比插入更简单，因为不需要抛硬币。

第一步，查找并记录每层的前驱，和插入完全一样。如果最后在第 0 层发现目标不存在，删除失败，直接返回。

第二步，逐层摘除。从第 0 层到目标节点的最高层，对每一层执行：update[level].forward[level] = target.forward[level]。也就是让每一层的前驱“绕过”被删节点，直接指向它的后继。

第三步，可选地降低跳表层数。如果被删节点是最高层的最后一个节点，删除后 head 在那些层指向空，就可以把跳表的最大层数调低，避免以后每次查找都从很空的层开始空转。这一步是纯优化，不做也不影响正确性。

def delete(head, target, max_level):
    update = [None] * max_level
    cur = head
    for level in range(max_level - 1, -1, -1):
        while cur.forward[level] is not None and cur.forward[level].key < target:
            cur = cur.forward[level]
        update[level] = cur

    victim = cur.forward[0]
    if victim is None or victim.key != target:
        return False

    for level in range(victim.level):
        update[level].forward[level] = victim.forward[level]

    while head.level > 1 and head.forward[head.level - 1] is None:
        head.level -= 1
    return True

6.2 删除配图：删除 50（塔高 2）

删除前，50 出现在第 0 层和第 1 层。我们记录下：第 0 层前驱是 38，第 1 层前驱是 12。

删除后，第 0 层中 38 的后继直接指向 67，第 1 层中 12 的后继直接指向 81。50 这座塔从两层链表中同时消失。

删除操作同样只有局部影响：被删节点前后的若干指针被改写，其余节点原封不动。它和插入共享同一个查找骨架，所以只要把查找和插入写对，删除几乎不会引入新类型的 bug。

6.3 删除的常见错误

删除虽然简单，生产代码里仍有两个高频错误值得单独提醒。

第一个错误：摘除时只处理第 0 层。如果目标节点出现在第 0 层和第 2 层，而你只修改了第 0 层的前驱指针，那么这个节点会继续“悬”在第 2 层。之后的查找仍然可能从第 2 层经过它，虽然它的键还在表里“可见”，但它已经不在第 0 层链表中，结构的一致性被破坏，最坏情况下会形成环。正确做法是从第 0 层一直处理到 victim.level 的每一层。

第二个错误：删除后不收缩 head 的层数。假设表里曾经有一个 20 层的节点，被删之后最高层只剩 5 层，但 head 仍然报告“最高 20 层”。每次查找都会从第 19 层开始，发现下一个节点为空，白白空降 15 层。正确性不受影响，性能却会劣化。虽然单次空降只有 O(log n) 的常数损失，但在高频查找场景里，这个损失会稳定地叠加。

这两个错误都源自同一个思维盲区：把跳表当成“一条链表”而不是“一组链表”。记住，每一层都是一条独立的链表，所有层必须同时保持完整，删除才算完成。

7. 概率与复杂度：抛硬币为什么能让结构“期望平衡”

7.1 先回答一个朴素的问题：随机真的靠谱吗

任何一个第一次接触跳表的人都会问：**靠抛硬币决定结构，靠谱吗？**万一运气特别差，所有节点都只有一层，跳表不就变回普通链表了吗？万一运气特别好，所有节点都长到最高层，跳表不就变成一条到处都是冗余指针的“胖链表”了吗？

这两个问题的答案都是：有可能，但概率小到可以忽略，而且这种“差运气”只会出现在极端情况下。数据结构理论里有一类概念叫“期望复杂度”：我们允许结构在极少数情况下表现糟糕，只要平均表现好，并且糟糕的概率可以控制，就可以接受。跳表就是这类结构的代表——它用概率换掉了确定性，用“大概率好”换掉了“保证好”。

为了理解这一点，我们先搞清楚一个节点到底会占多少层。

7.2 单个节点的层数：几何分布

假设每层出现的概率是 1/2，那么：

节点至少 1 层的概率是 1； 节点至少 2 层的概率是 1/2； 节点至少 3 层的概率是 1/4； 节点至少 k 层的概率是 2 的负 k 减 1 次方（如果从第 1 层数起）或者 2 的负 k 次方（如果从第 0 层数起）。

这是一个典型的几何分布。几何分布有个非常优雅的性质：它的期望等于 1/p，也就是 1/(1/2) = 2。意思是，一个节点平均只占 2 层：底层加一个额外的层。一万个节点的跳表，平均只需要大约两万个指针——空间开销大约是“每个节点一个指针”的普通链表的两倍。这个代价非常小，换来的是查找从 O(n) 变成 O(log n)。

还可以从另一个角度理解：虽然每个节点平均只有 2 层，但“至少有 k 层的节点”数量按指数衰减。一百万个节点的表里，有大约 50 万个节点至少 2 层、25 万个至少 3 层、12.5 万个至少 4 层……以此类推，到第 20 层时，期望只剩大约 1 个节点。也就是说，虽然每个节点都很“矮”，但总有一小撮节点足够“高”，足以支撑从顶层直达底层的快速通道。

7.3 最大层数：为什么大约是 log n

现在我们想知道整张表的最高层大概有多高，因为查找从最高层开始，层数直接决定了“要下降多少次”。

设 n 个节点。一个节点高度至少 k 的概率是 2 的负 k 次方，所以高度至少 k 的节点数的期望是 n / 2^k。当这个期望小于 1 时，说明“再往上加一层，大概率就找不到节点了”，所以合理的最大层数 k 满足 n / 2^k ≈ 1，解得 k ≈ log₂ n。

这个结论和树高如出一辙：二叉搜索树的高度是 log₂ n，跳表的层数期望也是 log₂ n。第 13 篇我们讨论“层数决定路径长度”的直觉在这里原样成立——查找每下降一层，就相当于树里从根往下走一层；下降 log n 次之后必然到达底层。

如果使用 p = 1/2，最大层数的期望大约是 log₂ n；如果使用 p = 1/4（Redis 的选择），这个值大约是 log₄ n = (1/2)log₂ n，层数更少，但每层之间的跳跃跨度更大，期望比较次数会多一些常数因子。这是“层数”和“每层比较次数”之间的权衡。

7.4 查找为什么期望 O(log n)

完整的期望分析比较复杂，这里给你一个足够准确的直觉版本。

把查找路径倒过来看：从目标节点开始，在第 0 层向前看。某个节点只出现在第 0 层时，查找只能一步一步走；但每当我们遇到一个“至少 2 层”的节点，就可以借助它的高层指针往前跳一大段。在随机结构下，查找路径中“连续只有第 0 层节点”的期望长度是一个常数——因为任意一段连续的低层节点，长度超过常数的概率按指数衰减。

更标准的分析是这样：从底层目标位置开始，向上追溯查找路径。每一步，当前节点要么来自左侧节点的第 k+1 层指针（概率 1/2，且向前跳一步），要么来自同一层左侧节点（概率 1/2，层数减一）。这本质上是一个“随机游走”：向左看一步、向上一层。向左看最多进行常数次，向上最多进行 O(log n) 次，所以期望路径长度是 O(log n)。

最后，每一步在某一层内向右滑动时，虽然可能连续经过多个节点，但期望步数也是常数。把“层数下降 O(log n)”和“每层期望常数步”乘起来，就得到了期望 O(log n) 的查找时间。插入和删除的定位阶段和查找完全相同，所以它们同样是 O(log n) 期望；再加上插入时的随机层数生成 O(1)、链接 O(层数) = O(log n) 期望，结论不变。

7.5 最坏情况：运气差会怎样

诚实地面对最坏情况：跳表的最坏查找时间确实是 O(n)。

什么时候会退化？当随机层数生成器每次都给出相同结果时。比如连续抛了 n 次反面，所有节点都只有第 0 层，跳表退化成普通有序链表，查找变成 O(n)。这件事发生的概率是 2 的负 n 次方：n = 1000 时，概率大约为 10 的负 301 次方——比“连续中十次彩票头奖”还小无数个数量级。工程上完全可以忽略。

但理论家不会满足于“几乎不会”。红黑树、AVL 树保证的是最坏 O(log n)，跳表保证的只是期望 O(log n)。这个区别在两类场景里很重要：

第一类，强实时系统。如果某个操作必须在严格的时间上限内完成（比如飞行控制系统里一次查找不能超过 10 微秒），那么“平均快但偶尔慢”的跳表就不如红黑树让人安心。

第二类，对抗性输入。如果攻击者能控制插入顺序、甚至能观测或影响随机数生成器的输出，理论上可以构造出让跳表退化的输入序列。经典的“哈希碰撞攻击”也是同一个原理：伪随机分布被破坏后，期望分析失效。防御办法是使用加密安全的随机源，或者在随机层数里混入插入时的真实时间。

除了这两个场景，绝大多数应用（数据库、缓存、并发容器）都接受期望复杂度。它们更看重平均吞吐和实现的可靠性，而跳表恰好在这两方面都极其出色。

7.6 一张图总结复杂度

操作	平均/期望	最坏	备注
查找	O(log n)	O(n)	最坏需要全表退化成单层
插入	O(log n)	O(n)	定位占主导，链接是 O(层数)
删除	O(log n)	O(n)	定位占主导，摘除是 O(层数)
求前驱/后继	O(log n)	O(n)	从目标节点沿底层移动一步
区间遍历	O(log n + k)	O(n + k)	k 是区间长度，遍历全在第 0 层
空间	O(n) 期望	O(n log n)	平均每节点 2 个指针（p=1/2）

注意“空间最坏 O(n log n)”这一行：如果每个节点都长到 maxLevel，指针总数会是 n × maxLevel。但由于概率衰减，这种极端几乎不可能出现。Redis 用 p = 1/4 正是为了把平均指针数从 2 降到约 1.33，省下约三分之一的内存。

7.7 期望分析的标准证明骨架（进阶）

如果你已经掌握了期望和概率的基本记号，这里给你一套完整的证明骨架，它来自 William Pugh 1989 年发表跳表的原始论文，思路清晰且只用到了最基础的概率工具。

第一步，倒着看查找路径。正向查找是从头节点开始、向右再向下的；但分析时反过来更容易：从目标节点在第 0 层的位置出发，沿着“指针是从谁那里来的”一路回溯到头节点。倒着走时，每一步只有两种可能：当前位置在第 k 层，它可能是由左侧某个节点在第 k+1 层的指针“跳”过来的，也可能是由左侧同一个节点在第 k 层的指针“走”过来的。

第二步，给回溯路径定价。假设当前在第 k 层，向左回溯一步。左侧节点在 k+1 层也有指针的概率是 p（因为每层保留下一层约 p 比例）。如果它有，说明当前这一步是“从上层跳下来”的，那么回溯路径向上走一层；如果它没有，则停留在同一层继续向左。于是，回溯过程变成了一枚硬币：每向左看一个节点，有 p 的概率“上升一层”，有 1−p 的概率“继续同层”。

第三步，计算期望步数。上升层数最多是最大层数 O(log n)。在同层内连续向左看的期望次数是常数：因为每向左看一次，有 1−p 的概率停留，停留次数服从几何分布，期望是 1/(1−p)，当 p = 1/2 时就是 2。把“上升 O(log n) 次”和“每次上升之间期望常数步”相乘，就得到整个回溯路径的期望长度 O(log n)。

第四步，把“期望”升级成“高概率”。期望分析只说明平均值，更强的结论是：查找时间以很高的概率不超过 O(log n) 的常数倍。证明思路是观察回溯路径中“上升”次数相当于 n 次独立伯努利试验中连续成功段的总长，可以用 Chernoff 界证明“某条路径特别长”的概率随 n 增大指数衰减。工程上通常不写这么细，但知道这个结论会让你对“跳表靠谱吗”更有底气：它不仅是平均好，而且以压倒性概率好。

第五步，插入和删除直接复用这个结论。它们的定位阶段就是一次查找，剩下的指针操作只有 O(层数) 次，而层数本身以高概率是 O(log n)。所以三种操作共享同一个证明骨架。

这套证明最漂亮的地方在于：它几乎不依赖具体的键值分布，只依赖随机层数的独立性。换句话说，无论你的数据是有序的、逆序的、还是恶意构造的，只要随机源是好的，期望复杂度就成立。这也是跳表与“依赖输入顺序的朴素 BST”最根本的区别。

8. 工程实现细节：从玩具到生产级

8.1 maxLevel 到底取多少

前面说过，最大层数 k 应该满足 n / 2^k ≈ 1，也就是 k ≈ log₂ n。问题是 n 是动态变化的，我们不可能每次插入都重新计算。

工程上的做法是给一个足够大的固定上限：

如果 p = 1/2，n 最多有 2^32 个键，那么 32 层就永远够用；如果 n 可能达到 2^64 的量级（几乎不可能），取 64。 很多实现直接取 32：在 64 位机器上，一个 32 层节点的指针数组正好占 256 字节，对齐良好。 Redis 的做法略有不同：它用 ZSKIPLIST_MAXLEVEL = 32，同时把 p 调成 1/4，这样在 2^32 个元素时最大期望层数约 16，32 层是四倍裕量。

另一种动态方案：在每次插入后把 maxLevel 更新为当前层数加 1，比如“节点层数超过当前最大层数时，将最大层数设为旧值加 1”。这能保证层数始终是 O(log n) 而不是固定常数，适合元素数量增长巨大的场景，但代码稍微复杂一点。

8.2 随机层数生成：不只是“抛一次硬币”

教科书里写“抛硬币”，工程实现里当然不能真的抛硬币，而是要高效地生成几何分布随机数。

最简单的实现：循环调用随机数，每次有 1/2 概率加一层。

def random_level(rng, max_level):
    level = 1
    while level < max_level and rng.random() < 0.5:
        level += 1
    return level

这个写法正确，但平均循环 2 次，且每次调用都生成一个浮点数，性能一般。更快的方法是利用二进制位：

def random_level_fast(rng, max_level):
    bits = rng.getrandbits(32)
    level = 1
    while level < max_level and (bits & 1) == 1:
        level += 1
        bits >>= 1
    return level

一次生成 32 个随机位，然后数最低位的连续 1 的个数——连续 k 个 1 的概率正好是 2 的负 k 次方，和“抛 k 次硬币全正面”完全等价。Redis 的 zslRandomLevel 用的就是这个思路：它取一个 32 位随机数，把最高位的 1 的位置当作层数，配合 p = 1/4 和掩码实现。

这里有一个常被忽视的坑：随机数生成器的质量会影响跳表性能。如果使用低质量的线性同余生成器，连续随机数可能呈现可预测的规律，导致层数分布偏离几何分布。在并发场景下还要注意随机源是否线程安全。生产代码里用线程局部随机数（ThreadLocalRandom）是最常见的做法。

8.3 哨兵头节点：让边界情况消失

跳表的头节点是“假节点”：它的键不参与比较（通常设为最小可能值或根本不存键），但它的指针数组长度等于当前最大层数。

有了哨兵头，下面的边界情况全部自动消失：

插入到链表最前面：新节点的前驱是 HEAD，和普通插入一样处理； 删除第一个真实节点：HEAD 的指针被改写，无需特殊判断； 空表：HEAD 的所有层都指向空，查找直接在最高层发现“下一个不存在”，一路下降到第 0 层，返回“不存在”。

对照普通链表的哨兵节点，跳表哨兵唯一的区别是它同时出现在所有层。它本质上是一个“多层的哑节点”。

8.4 空间开销：平均每个节点几个指针

p = 1/2 时，期望指针数 = 每节点 2 个，n 个节点共 2n 个指针；p = 1/4 时，期望 4/3 ≈ 1.33 个指针，共 4n/3 个。

和红黑树对比：红黑树每个节点需要 left、right、parent 三个指针（或者用缓存友好的方式省掉 parent），加上 1 位颜色标记。跳表每个节点只需要 forward 数组，没有父指针。所以“跳表更费内存”的说法其实不准确——在 p = 1/4 时，跳表的总指针数和红黑树相当，甚至更少；在 p = 1/2 时，跳表大约是红黑树的 1.5 倍指针量。

真正值得注意的是缓存局部性。跳表的指针分散在堆上，高层指针会跳到很远的内存地址，而红黑树/数组结构更连续，CPU 缓存命中率更高。这就是为什么“理论复杂度相同”的结构，实测性能可能差出几倍。跳表强在实现简单和并发友好，弱在缓存不友好；B 树强在缓存/磁盘友好，弱在实现复杂。没有免费的午餐。

8.5 并发友好：为什么跳表适合多线程

这是跳表在工程界大受欢迎的关键原因之一，值得单独说。

平衡树在并发更新时很痛苦：一次旋转可能改变多个节点的父子关系，锁的粒度和范围都很难设计。跳表的更新只影响 O(log n) 个节点的局部指针，天然适合“细粒度并发”。

最常见的实现是 Java 的 ConcurrentSkipListMap：它用无锁的 CAS（比较并交换）来修改指针，删除节点时先给节点打上“标记”（一个特殊的哨兵后继），再执行物理删除。这样即使多个线程同时操作，也不会出现“一个线程读到另一个线程正在删除的节点”的悬挂指针问题。

无锁跳表的正确性分析很深，但它的直觉很简单：每一层的链接操作都是“局部小事务”，CAS 失败就重试；标记节点保证并发遍历者不会在删除进行到一半时读到半成品。相比平衡树需要在整条路径上加锁，跳表的并发更新成本低得多。

8.6 实现陷阱清单

写跳表时最常见的五个坑，列在这里帮你避雷：

第一，比较条件写反。查找时应该用“下一个节点的键小于目标”向右，有人写成“小于等于”，结果查找会越过相等键，导致“明明存在却找不到”。

第二，update 数组长度不够。如果新节点的层数超过 maxLevel，而 update 只申请了旧最大层数的空间，越界访问会静默破坏内存。Redis 的解法是固定 32 层，层数超过时直接截断。

第三，忘记更新 head.level。插入后跳表层数变大，但 head 还是旧长度，下次查找从过低的层开始，性能会悄悄退化。

第四，删除时没有处理“最高层被删空”。虽然不影响正确性，但会让空层越来越多，白费比较。

第五，随机层数生成器返回 0 层。层数必须至少是 1（至少出现在第 0 层），否则新节点“悬空”，整个底层链表断裂。

8.7 内存布局与缓存局部性

跳表在理论上是 O(log n)，在工程上它的实际速度却强烈依赖“指针跳到哪里”。这就要说到 CPU 缓存。

现代 CPU 读取内存时，不是按字节读，而是按“缓存行”（通常 64 字节）成块读入。如果程序访问的内存地址彼此相邻，第二次访问大概率命中缓存，速度可以快几十倍；如果地址随机跳跃，每次都要从主存取数据，延迟高达几十纳秒。数组和 B+ 树的节点天然连续，预取器可以提前把后面的数据搬进缓存，所以缓存命中率很高。跳表则相反：高层指针指向的节点散布在整个堆里，访问顺序几乎是随机的，缓存命中率天然吃亏。

这一点在数据量大时尤其明显。十万个节点的跳表，指针总跨度可能达到几十兆字节，一次查找在高层跳跃时，每一步都可能触发缓存未命中。虽然比较次数只有 O(log n)，但每次比较都伴随一次内存延迟，常数因子可能比红黑树大。这也是为什么“理论复杂度相同”的两个结构，实测性能却可能差出两三倍。

工程上有几种缓解手段。第一种，降低 p 值，减少每个节点的指针数，让整张表更紧凑，提高缓存命中概率，Redis 就是这么做的；第二种，把节点按“层”而不是按“节点”存储，也就是所谓“层优先布局”，让同一层的节点尽量连续分配，但这会显著增加插入删除的复杂度；第三种，干脆换用缓存友好的 B+ 树变体，在内存数据库（如 SQLite 的内存模式、部分嵌入式引擎）里，B+ 树的实测性能常常反超跳表。

所以一个成熟的工程师不会只看大 O：跳表赢在实现简单和并发友好，输在缓存局部性。选择数据结构时，要把“数据规模、访问模式、是否并发、是否内存常驻”全部放上桌，而不是背一个复杂度表就下结论。

9. 应用：从 Redis 到数据库再到 Java 并发容器

9.1 Redis 有序集合（ZSET）：最著名的跳表用户

提到跳表，绝大多数人第一个想到的就是 Redis 的 ZSET（有序集合）。Redis 的作者 antirez 在源码注释里写过选择跳表而不是平衡树的原因，总结起来是四条：

第一，实现简单。平衡树的旋转逻辑又长又容易错，跳表只要几百行代码就能写对。

第二，范围查询方便。ZSET 需要支持 ZRANGE（按排名取区间）、ZRANGEBYSCORE（按分数取区间）。跳表的第 0 层是一条完整的有序链表，从头开始顺序走就能拿到“排名连续的一段”，天然支持双向范围遍历；平衡树要反复做中序后继查找，代码繁琐。

第三，调试容易。跳表的结构可以直接用文本打印出来检查，而红黑树的“红黑性质”检查需要额外的遍历代码。

第四，概率带来的灵活度。通过调整 p 值就能在内存和速度之间滑动，这是红黑树做不到的。

Redis 的 ZSET 实际是“哈希表 + 跳表”的组合拳：哈希表存“成员 → 分数”的映射，保证 O(1) 地按成员查分数；跳表存“（分数，成员）”的有序序列，支持按分数和排名操作。两个结构共享同一批数据，各管一摊。

注意 Redis 的跳表节点里分数允许重复，重复时按成员字典序排序；score 和 member 同时作为比较键。这也是“重复键处理”一节里说的策略二在生产中的真实案例。

9.2 LevelDB / RocksDB / SkipDB：写缓冲的骨架

LevelDB 的 MemTable（内存写缓冲）用的就是跳表。为什么？

数据库引擎的写路径要求：写入要快，而且内存中的数据必须随时保持有序，以便刷盘时按序输出、或者合并到下一层 SSTable。跳表的插入不需要像平衡树那样做旋转，而且写路径是单线程的，跳表实现起来最省心。LevelDB 的作者 Jeff Dean 在设计时明确说过，MemTable 用跳表的主要理由是“实现简单且足够快”。

RocksDB 继承了这一设计，它的 MemTable 默认也是跳表，还提供“前缀相同键合并”的扩展。SkipDB 则更进一步，把整个数据库做成“基于跳表的键值存储”，利用跳表天然的有序性做范围扫描。

还有一个容易混淆的点：LevelDB 的磁盘部分（SSTable）用的并不是跳表，而是有序不可变文件加索引块。跳表只活在内存写缓冲里，因为跳表在磁盘上的缓存局部性很差——这也是它没有成为磁盘主索引的原因之一。

9.3 Java 并发容器：ConcurrentSkipListMap 与 ConcurrentSkipListSet

Java 里有一对著名的并发有序容器：ConcurrentSkipListMap 和 ConcurrentSkipListSet，它们是并发版的 TreeMap/TreeSet。为什么不用并发的红黑树？因为给红黑树做无锁化太难了：旋转涉及多个节点的多个指针，很难用单个 CAS 原子地完成。

ConcurrentSkipListMap 的实现采用无锁读 + 有限锁写（早期版本）或完全无锁 CAS（后来的版本）：

读操作完全不加锁，因为高层指针只会被“原子地替换”，不会出现半更新状态； 写操作通过 CAS 在每层独立地插入节点，失败就重试； 删除用“标记节点”技术做逻辑删除，再清理物理节点。

在实际工程里，ConcurrentSkipListMap 常被用于：定时任务调度器（按键排序、支持范围取出到期任务）、分布式系统里的活跃会话表（并发更新 + 有序遍历）、以及一切“既要并发又要有序”的缓存层。

9.4 为什么 MySQL 不用跳表

经常有人问：MySQL 索引用 B+ 树，那跳表是不是也能做数据库索引？答案是可以，但不划算。

数据库索引存在于磁盘上，最贵的操作是磁盘 I/O。B+ 树的每个节点是一个磁盘页（通常 4KB 或 16KB），一次 I/O 能读入几百个键，树高只有三四层，三次 I/O 就能定位任意记录。跳表的高层指针指向的内存地址在磁盘上完全没有空间局部性，每一次高层跳跃都可能触发一次随机磁盘 I/O——log n 层就是 log n 次随机读，比 B+ 树的三四次固定 I/O 差一个数量级。

所以工程界的共识很清晰：内存里的有序并发结构，优先考虑跳表；磁盘上的索引，优先考虑 B+ 树。Redis 和 MemTable 都在内存，用跳表；MySQL、PostgreSQL 的索引在磁盘，用 B+ 树。

9.5 其他身影：HBase、内存数据库与自研索引

跳表在工程界的应用比很多人想象的更广。

HBase 的 MemStore（写缓冲）内部就是一个 ConcurrentSkipListMap：多个 Region 的写入先落进内存里的跳表，按行键有序组织，刷盘时直接顺序遍历输出，天然满足 LSM 树对“内存有序结构”的要求。因为 MemStore 会被多个写线程并发访问，跳表的无锁读和细粒度写优势在这里发挥得淋漓尽致。

内存数据库和缓存系统也常常在“排序索引”的位置上放跳表：当数据量在千万级以内、完全常驻内存时，跳表的实现成本和维护成本都低于平衡树，而范围查询和并发更新又优于普通树。一些自研的时序数据库用跳表按时间戳组织最近的数据块，配合 TTL 过期删除，跳表的“局部删除”特性让清理逻辑非常干净。

还可以把跳表和其他数据结构“混搭”。比如在跳表节点上挂一个哈希表，实现“按键定位 + 按序扫描”双能力；或者在跳表的第 0 层挂双向指针，让前驱后继操作变成 O(1)。Redis 的 ZSET 就是混搭的范例：哈希表负责按成员找分数，跳表负责按分数找排名，各取所长。这种“组合拳”思想，比任何单一结构都更贴近真实系统的需求。

如果有一天你要自研索引，建议把跳表放在“内存有序并发容器”这个档位去比较，而不是和磁盘索引比较。选型时先回答三个问题：数据在内存还是磁盘？是否需要严格最坏时间保证？并发更新是常态还是偶尔？三个答案落到“内存、不需要严格、并发常态”时，跳表几乎总是最优解。

10. 最终对比：跳表 vs 红黑树 vs B+ 树（内存场景）

到这里，我们把树系列里最重要的三个“有序结构”放在一起做一次最终对比。

10.1 一张表看清三种选择

维度	跳表	红黑树	B+ 树（内存版）
平衡方式	随机（概率）	红黑性质 + 旋转	节点分裂/合并
查找复杂度	期望 O(log n)	最坏 O(log n)	最坏 O(log n)
插入复杂度	期望 O(log n)，无旋转	最坏 O(log n)，最多 3 次旋转	最坏 O(log n)，可能分裂
删除复杂度	期望 O(log n)	最坏 O(log n)，最多 3 次旋转	最坏 O(log n)，可能合并
最坏情况	O(n)，概率极小	严格 O(log n)	严格 O(log n)
实现难度	低（约百行）	中高（旋转+染色）	高（分裂/合并/父指针）
范围查询	极好（底层链表顺序走）	一般（中序后继）	极好（叶链顺序走）
空间	平均 1.33~2 指针/节点	3 指针 + 颜色位/节点	多键 + 子指针，页利用率 2/3
缓存局部性	差（指针跳跃远）	中	好（节点连续、可预取）
并发友好度	高（局部指针 + CAS）	低（旋转破坏局部性）	中（页锁）
典型用途	Redis ZSET、MemTable、并发容器	TreeMap、Linux 内核调度	数据库/文件系统索引

10.2 怎么选：一张决策图

10.3 三种结构其实是同一个问题的三个答案

第 13 篇我们说过，B 树解决的是“磁盘上怎么减少 I/O”；第 11、12 篇我们说过，红黑树解决的是“内存里怎么严格保证 O(log n)”；这一篇的跳表回答的是第三个问题：“内存里怎么用最简单的代码、最好的并发特性拿到 O(log n)”。

它们共享的底层思想贯穿整个树系列：有序 + 分层 + 可控的高度 = 高效查找。红黑树用颜色保证高度，B+ 树用大扇出压缩高度，跳表用概率把高度“期望”出来。三种方案殊途同归，都是把“比较次数”从线性压到对数。

10.4 一个具体的数字感受：一百万条记录

抽象的复杂度结论很容易被忽略，不妨把数字摆出来。

假设有一百万条有序记录，普通链表的查找平均要走五十万步；跳表在 p = 1/2 时，最大层数的期望是 log₂(10⁶) ≈ 20 层，一次查找的期望步数大约在三十到五十次指针移动；红黑树的高度不超过 2 × log₂(n+1) ≈ 40，最坏比较四十次；内存版 B+ 树如果每页放 100 个键，树高只有 3 层，但每一层都要在一个节点内部做几十次比较，总比较次数也在几十的量级。

换句话说，一百万这个量级上，四种结构的“次数”其实都在同一个数量级，真正拉开差距的是常数：缓存命中率、比较器开销、内存分配次数、锁竞争。跳表插入时需要为节点分配一块大小可变的指针数组，分配次数比红黑树多但比数组搬移少；范围扫描时跳表只需要顺着底层链表走，而红黑树要反复走“中序后继”，后者在跳转上的缓存代价更高。

如果数据量涨到十亿，log₂(10⁹) ≈ 30 层，跳表依然只需要几十次指针移动；而普通链表要平均走五亿步，早就不可用了。这组数字解释了为什么跳表在“百万到十亿级内存数据”的区间里特别有竞争力：它的常数虽然不完美，但它的增长曲线足够平缓，而且实现简单到可以放心交给团队长期维护。

最后补充一个反直觉的观察：跳表的“期望”并不仅仅体现在单次操作上，更体现在长期运行的行为上。假设你在一个空的跳表里连续执行一百万个随机插入，再执行一百万个随机查找，整个过程里你几乎不会观察到任何一次“明显变慢”的操作。原因前面已经讲过——退化需要连续大量节点共享同一个低层数，而这样的“坏区段”出现概率随区段长度指数下降。用一句工程黑话总结：跳表的延迟分布非常“稳定”，尾部极短，这对追求可预测性的系统是宝贵的性质。

深水区：跳表的变体与亲戚

跳表家族不止一种形态，理解几个常见变体能帮你建立完整的知识地图。

第一个变体是确定性跳表。普通跳表靠随机层数保证平衡，确定性跳表则用一组固定规则维持结构：比如“1-2-3 跳表”规定同一层中连续节点之间，下层节点的数量只能是 1、2 或 3，插入时通过局部的提升和旋转保持这个约束。它放弃了随机性，换来了严格 O(log n) 的最坏保证，代价是实现复杂度上升——这恰好印证了跳表“简单”的红利来自概率。

第二个亲戚是Treap（树堆）。Treap 给每个节点随机分配一个优先级，然后既按键值满足二叉搜索树性质、又按优先级满足堆性质，通过旋转保持两种性质同时成立。Treap 和跳表共享同一个核心思想：“用随机优先级代替复杂的平衡规则”，只是载体从多层链表换成了二叉树。如果你已经理解跳表的“抛硬币”，Treap 的“随机优先级”几乎不用学就会。

第三个亲戚是概率数据结构家族，比如布隆过滤器、计数型布隆过滤器、Count-Min Sketch。它们也用随机化和“大概率正确”换取空间与时间，但和跳表不同：布隆过滤器允许小概率的误报（说“存在”其实不存在），而跳表从不返回错误结果——随机化只影响它的速度，不影响它的正确性。这个区别非常重要：跳表是“随机化的数据结构”，不是“概率性的数据结构”。

第四个值得知道的方向是跳表与 LSM 树的组合。LSM 树（日志结构合并树）把写入先放在内存跳表里，满了之后冻结、刷盘、合并。这里跳表的“有序”和“可并发”直接服务于整个存储引擎的写放大控制。理解了这一层，你会明白为什么跳表常被称作“数据库写路径的隐形功臣”。

常见误解与辨析

最后，把学习跳表时最容易产生的五个误解一次性澄清。

误解一：跳表不是树，和树系列无关。跳表确实没有“节点-孩子”的父子关系，但它和树一样用“分层”压缩搜索路径，每一层对应树的一层截面，层数对应树高。把它放在树系列里，恰恰是为了让你看到：树的本质是“分层 + 有序”，而不是“必须有左右孩子”。

误解二：随机 = 不可预测 = 不可靠。跳表的随机只影响“哪一层有哪些节点”，不影响“查找结果是否正确”。正确性由“第 0 层包含全部节点”这一条保证，与随机无关；随机只决定性能，而性能在期望意义和高概率意义下都有严格证明。

误解三：跳表一定比红黑树费内存。在 p = 1/2 时，跳表平均每节点 2 个指针，比红黑树的 3 个指针（左、右、父）还少；在 p = 1/4 时约 1.33 个指针，空间优势更明显。说“跳表费内存”是把“指针分散、缓存不友好”误当成了“占用更多字节”。

误解四：最坏 O(n) 意味着跳表不能用于生产。绝大多数生产系统追求的是平均吞吐和工程可靠性，而不是数学上的最坏上界。Redis、LevelDB、HBase、Java 并发容器都用跳表，恰恰说明“期望 O(log n) + 极小的退化概率”在工程上是完全可接受的。

误解五：Redis 的 ZSET 就是用跳表实现的，和哈希表无关。实际上 ZSET 是“dict + zskiplist”双结构：哈希表提供按成员 O(1) 定位，跳表提供按分数有序遍历。只看到跳表而忽略哈希表，会漏掉 Redis 设计中最精彩的部分——让两个结构各管一摊。

动手实验：从零写一个最小跳表

读到这里，你已经掌握了全部原理。如果不用编辑器亲手写一遍，这些知识很快就会变成“看懂了但不会写”。下面给你一个 15 分钟的最小实验方案，建议照着做一遍。

第一步，定义节点。一个节点保存键、值，以及一个长度等于“层数”的指针列表。用你熟悉的语言写一个类，字段就三个：key、value、forward（数组）。先不用管内存优化，怎么直观怎么写。

第二步，写查找。严格按第 4 节的两条规则：从最高层开始，内层循环向右，外层循环向下。写完先用几个小例子验证：空表返回不存在；单节点命中；目标小于最小键；目标大于最大键。这四种情况各写一个测试，比你写 100 行代码更能保证正确。

第三步，写随机层数。用一个简单的循环生成几何分布：层数从 1 开始，只要随机数小于 0.5 就加一，超过上限就停。这一步验证的重点是分布：插入一万个节点后，统计“层数为 1、2、3、4……”的节点数量，应该大致是 5000、2500、1250、625……如果偏差很大，先检查随机数用法，再检查循环边界。

第四步，写插入。查找时顺便填充 update 数组，然后生成层数，最后从第 0 层到新层数逐层链接。写完立刻用“顺序插入一万个有序键”做压力测试：如果代码正确，查找任意键都应该在几十步内完成；如果你把 update 数组写错了，顺序插入后查找会退化成几百步——这是最容易暴露问题的测试。

第五步，写删除，然后做“插入一万个、删除五千个、再查找全部”的随机对拍测试：把结果和标准库的 SortedSet 对比，任何不一致都是 bug。如果全部通过，恭喜你，你已经拥有一个可用的跳表实现。

最后留一个思考题：如果你的键是字符串，比较成本高于整数，跳表的“比较次数”会比红黑树多还是少？为什么？想清楚这个问题，你就真正理解了为什么工程选型永远要结合数据特征，而不是只看大 O。

11. 速查表

主题	一句话结论
结构	多层有序链表，第 0 层包含全部节点，高层是低层的稀疏子集
哨兵头	每层链表的统一起点，键视为负无穷，消除边界特判
查找	从最高层开始，向右直到下一个键 ≥ 目标，然后下降一层，重复至第 0 层
插入	查找定位并记录每层前驱 update[]，抛硬币定层数，逐层链接
删除	定位后从底层到最高层逐层摘除，可选地收缩空层
层数分布	P(层数 ≥ k) = p^k，几何分布，期望层数 = 1/(1−p)
最大层数	期望约 log_{1/p} n，工程上常用固定上限（如 32）
复杂度	查找/插入/删除期望 O(log n)，最坏 O(n)（概率极小）
空间	p=1/2 时约 2n 个指针；p=1/4 时约 4n/3 个指针
重复键	可拒绝、可允许多值（Redis 按分数+成员）、可覆盖值（Map）
并发	读无锁、写局部 CAS，比平衡树容易并发化
最佳场景	内存中有序结构、范围查询、并发容器；不适合磁盘索引

12. 自测题

13. 下一篇预告

跳表用“层”换速度，那么反过来，“堆”这种完全不同的结构又是怎么工作的？下一篇文章《树系列第 16 篇：堆与优先队列》我们会看到：一棵被强行压扁成数组的完全二叉树，怎么用 O(1) 取出最大/最小元素、用 O(log n) 完成插入和删除，以及 Dijkstra 算法、任务调度器为什么离不开它。跳表的“概率”和堆的“偏序”，将共同补全我们对“树的形态决定性能”的最后一课。

结语

跳表是数据结构里少有的“用概率换简单”的杰作。它告诉我们，平衡不一定非要靠精确的规则来维持，一枚硬币、一条几何分布，也能让结构在大概率下保持高效。下次你在 Redis 里敲 ZADD、在 LevelDB 里写一条日志、在 Java 里 new 一个 ConcurrentSkipListMap 时，可以想起这篇文章里的那些金字塔、硬币和 update 数组——它们正在默默地把你的数据整理得井井有条。

如果你只想记住一句话，那就记住这句：跳表把“平衡”从一项必须维护的职责，变成了一种自然而然发生的结果。它没有旋转时的惊心动魄，也没有染色时的细致入微，它只是安静地抛硬币，然后让概率替你完成剩下的所有工作。这或许是整个树系列里最“佛系”的一个结构，但也是最值得放进工具箱的一个结构。