第 18 章

跳表——1989年，一位计算机科学家为什么决定用抛硬币代替平衡树的旋转？

正在加载交互实验…

第一季 · 人类如何驯服数据

历史主线：1962—2026年 · AVL树、随机化算法、William Pugh、Skip List 与 Redis1989年，一位美国计算机科学家正在研究一个困扰程序员多年的问题。他需要维护一个始终有序、又经常发生插入和删除的数据集合。如果使用普通链表，插入和删除节点很方便，但是寻找某个值可能很慢。如果使用二叉搜索树，查找比较快，但树可能因为连续插入有序数据而退化。如果使用 AVL 树或红黑树，则必须实现一套精心设计的平衡维护规则。插入之后要不要旋转？是左旋还是右旋？如果出现双重失衡，又应该怎样调整？这位研究者开始思考：我们真的需要在每次插入时，都严格修正数据结构的形状吗？如果不强制保证完美平衡，而是允许节点通过随机方式决定自己拥有多少层索引，会发生什么？例如，每次插入一个新节点，都抛一次硬币。正面，它升高一层。再抛一次。还是正面，继续升高。遇到反面，就停止。最终，有些节点只有一层，有些节点有两层，极少数节点能达到五六层。这听起来简直像在赌博。然而，这位研究者证明：只要随机规则设计合理，这种结构的搜索、插入和删除，都可以获得期望 $O(\log n)$ 的性能。他的名字叫作：William Pugh。他发明的数据结构，就是：Skip List，跳表。

第一幕：为什么1989年还需要另一种有序数据结构？

这段故事要从我们第五章讲过的 AVL 树说起。1962年，Georgy Adelson-Velsky 和 Evgenii Landis 发表了后来被称为 AVL 树的自平衡二叉搜索树算法。它解决了一个非常重要的问题：普通二叉搜索树在特定插入顺序下可能退化成链表。例如依次插入：10、20、30、40、50普通二叉搜索树可能长成：

此时搜索50必须连续经过五个节点。对于规模为

n

的数据，最坏时间复杂度会退化到：

O(n)

AVL 树通过维护节点高度差和旋转操作，保证树始终近似平衡。1978年，Leonidas Guibas 和 Robert Sedgewick 又发表了红黑树的经典研究。红黑树通过节点颜色和旋转维护较宽松的平衡条件。这让有序集合拥有了可靠的对数级最坏查找时间。但工程师仍然面临一个问题：能否得到接近平衡树的查找性能，却不必实现那些复杂的平衡规则？

Pugh 的选择：不追求严格保证，而追求高概率

William Pugh 的重要论文于1989年在 WADS 会议发表，并在1990年6月以更广为人知的形式刊登于 Communications of the ACM：Skip Lists: A Probabilistic Alternative to Balanced Trees《跳表：平衡树的一种概率性替代方案》。原论文开头就明确提出：跳表使用概率平衡，而不是严格维持平衡；因此插入和删除算法可以比许多平衡树算法更简单。^{[Sciweavers][CiNii Research]}

1990年历史原始文献

Skip Lists: A Probabilistic Alternative to Balanced TreesWilliam Pugh，Communications of the ACM，33(6)，668—676，1990年6月。阅读完整原始论文 PDF

这里有一个值得注意的历史细节。我们能够确认论文的公开发表时间和研究动机，但并没有可靠证据证明 Pugh 是在某一天真的拿起硬币、连续抛掷之后才想到这种数据结构。所谓“抛硬币”，是帮助理解其随机层数生成机制的一种数学比喻。我们不需要为算法发明过程编造一个不存在的戏剧性瞬间。真正令人惊讶的，已经是这套算法本身。

第二幕：从一条普通链表开始

假设你现在拥有八个已经排序的数值：10、20、30、40、50、60、70、80我们把它们保存为一个单向链表：

普通有序链表

如果要寻找80：先比较10。再比较20。再比较30。……直到80。对于

n

个节点，平均和最坏搜索都可能需要线性次数的检查。这显然不是理想的有序索引。

如果我们增加一条快速通道呢？

假设允许节点20、40、60、80拥有一层额外索引。现在从高级索引出发：20 → 40 → 60 → 80就不用检查底层全部节点了。搜索成本减少了不少。但 Pugh 还想到：为什么不再增加第三层？让40和80出现在更高层。于是，我们得到：

分层索引：越高的层，节点越稀疏

查看 SVG 配图原件

18-002.svg · 点击查看大图

这是一张结构示意图。底层包含全部节点，高层只包含部分节点；实际跳表还包含头节点与从高层向低层的搜索过程。

仔细看。最高层只有少量节点。第二层略多。第三层更多。最底层则保存全部元素。搜索时：从最高层出发。只要向右移动不会越过目标，就继续向右。如果下一步会超过目标，就下降一层。重复这个过程。直到在底层找到目标，或者确认它不存在。这就是跳表。它用多个稀疏的链表层，代替二叉搜索树中逐层分叉的查找路径。但现在你也许发现了一个新问题。如果每隔两个节点就必须增加高级索引，那么插入新节点之后，如何维持这种严格间隔？这可能又需要大规模调整。我们好不容易绕开树旋转，难道又要引入另一套复杂维护规则吗？Pugh 的突破正在这里。

第三幕：1989年，Pugh 的核心发明——让随机数替代平衡规则

现在我们来到整章最重要的一刻。Pugh 没有要求：每隔两个节点，就必须有一个二级索引。每隔四个节点，就必须有一个三级索引。相反，他规定：每次插入一个新节点，通过独立的随机试验决定它的高度。假设每次抛硬币，出现正面的概率为：

p=\frac12

新节点默认拥有第一层。然后不断抛硬币。如果正面，就继续向上增加一层。如果反面，就停止。例如：

抛硬币结果	节点最终层数
反面	1
正、反	2
正、正、反	3
正、正、正、反	4

因此：

P(L=1)=\frac12

P(L=2)=\frac14

P(L=3)=\frac18

一般地：

\boxed{P(L=\ell)=(1-p)p^{\ell-1}}

这里采用没有达到最大层数上限时的几何分布。而一个节点至少拥有第

\ell

层的概率是：

\boxed{P(L\geq\ell)=p^{\ell-1}}

这意味着：第一层，所有节点都有。第二层，平均约一半节点拥有。第三层，平均约四分之一节点拥有。第四层，平均约八分之一节点拥有。越高的层，节点越稀疏。这不就接近我们刚才手工设计的索引结构了吗？区别在于：我们不再严格规定哪些节点升高，而是让随机过程自动形成具有相似统计特征的结构。Pugh 在原论文中明确描述了这一步推导：如果把原来每隔固定数量设置一层索引的方式，替换为具有相同统计比例的随机层数，就可以避免频繁维护严格索引间隔。^{[g-trees.github.io]}

实验一：你来给新节点抛硬币

随机层数生成器

随机化算法的第一次实验

当前层数 1

晋升概率 p

第6层

第5层

第4层

第3层

第2层

第1层

新节点

已投掷结果

尚未投掷

出现正面继续升一层；出现反面就停止。

你可以连续生成几次节点高度。通常会发现：高度1或2的节点很多。高度4以上的节点比较少。偶尔也会遇到连续多次正面，产生一个很高的节点。但这并不违反算法的预期。跳表从来没有承诺每次构造出的层数分布都恰好等于数学期望。它承诺的是：在独立随机选择的假设下，整体结构通常能够维持良好的搜索性能。这就是概率平衡。

第四幕：从最高层开始查找，为什么会更快？

假设我们构造出一张跳表。底层：10 → 20 → 30 → 40 → 50 → 60 → 70 → 80较高层：20 → 40 → 60 → 80更高层：40 → 80我们要查找70。从最高层出发。先尝试向40移动。40小于70，可以前进。接下来，高层的80超过目标70。不能继续。于是下降一层。从40出发，发现60小于70。移动到60。下一步高层是80，仍然超过70。继续下降到底层。从60前进到70。找到目标。你有没有发现？搜索过程并不是在每一层都重新从头开始，而是保留当前位置，向右走或向下走。这就是跳表的搜索路径。

实验二：一步步搜索70

Skip List 单步搜索器

1/7

选择要查找的数值

从最高层头节点开始。

这个实验可以帮助你理解跳表的搜索规则。不过，它只使用八个节点，所以性能差异不会特别明显。当数据量增长到几十万、几百万时，高层索引的价值才更加突出。

第五幕：为什么随机跳表的期望搜索时间是 $O(\log n)$ ？

这一幕我们开始推导数学。假设每个节点晋升到下一层的概率是：

p=\frac12

那么，拥有至少第二层的节点，期望占总数一半。拥有至少第三层的节点，期望占四分之一。拥有至少第四层的节点，期望占八分之一。对于

n

个节点，层级达到

\ell

的期望节点数约为：

n\left(\frac12\right)^{\ell-1}

最高层大概在什么时候只剩下少量节点？我们令：

n\left(\frac12\right)^{\ell-1}\approx1

得到：

2^{\ell-1}\approx n

因此：

\boxed{\ell\approx\log_2 n+1}

这就解释了：为什么跳表的高度通常只有对数级。但仅仅说明高度是

O(\log n)

，还不够。因为我们还必须计算每一层向右移动多少次。在随机层数分布下，搜索路径从低层向高层反向分析时，平均只需要有限次数的水平移动便能遇到更高层节点。对于固定晋升概率

p

，每层水平移动的期望是常数量级。而层数是对数级。因此，搜索的期望时间为：

\boxed{E[T(n)]=O(\log n)}

插入和删除也需要先执行相似的定位过程，然后修改节点的局部指针，因此同样可以获得期望

O(\log n)

的性能。

但为什么不是最坏 $O(\log n)$ ？

因为随机结构确实可能产生极端情况。例如：所有节点都只有第一层。那么跳表就退化成普通链表。搜索末尾元素需要：

O(n)

时间。这并非数学上不可能。只是对于合理的随机晋升机制，当

n

很大时，发生严重失衡的概率通常非常低。Pugh 的1990年论文不只是计算了期望复杂度，还讨论了搜索时间与空间使用的概率界限。他给出了一个具体例子：对于超过250个节点的字典，搜索成本超过期望值三倍的概率，在其分析模型下低于百万分之一。^{[g-trees.github.io]}所以，跳表不是“保证永远平衡”。而是：允许极小概率的坏结构，换取简单、无需旋转的更新规则。

第六幕：跳表为什么不需要像 AVL 树那样旋转？

现在，我们尝试插入一个新节点：35已有底层：10 → 20 → 30 → 40 → 50插入后：10 → 20 → 30 → 35 → 40 → 50对于普通链表，只要定位到30和40之间，就可以修改指针。对于跳表，也采用类似的方法。只是需要处理多层索引。

假设35随机获得三层

我们先从最高层寻找插入位置。与此同时，记住每一层中，位于35之前的最后一个节点。例如：

第3层：HEAD → 40
第2层：HEAD → 20 → 40
第1层：HEAD → 10 → 20 → 30 → 40 → 50

找到的前驱节点是：第3层：HEAD。第2层：20。第1层：30。然后，把35插入这三层。

插入35之后

查看 SVG 配图原件

18-003.svg · 点击查看大图

新节点35的随机高度为3，因此只在底部三层更新前后指针；其他节点的随机高度保持不变。

这里的关键，是我们在搜索时保存了每一层的前驱。Pugh 的原始算法把这些前驱保存在一个 update[] 数组中。在真正插入时，只需要重新连接新节点所拥有的各层指针。不必像 AVL 树那样寻找失衡祖先、执行单旋或双旋。这正是跳表插入逻辑简洁的重要原因。^{[rtheunissen.github.io]}

删除也类似

假设删除35。沿搜索路径找到它。在它出现的每一层，把前驱节点的指针改成35原本指向的后继节点。然后释放35。不需要对其他节点重新抽取高度。也不需要整体重排索引结构。因此：随机平衡把维护复杂性的重点，从严格保持整棵结构的形状，转移到了插入时独立决定新节点高度。

第七幕：内存会不会因为多层指针而爆炸？

这其实是跳表设计中一个非常自然的疑问。如果每个节点都能拥有多个指针，存储成本会不会很高？假设所有节点都只有一个前向指针，普通单链表每个节点保存一个 next 指针。跳表中：第一层所有节点都有指针。第二层约有

np

个指针。第三层约有

np^2

个。依此类推。因此预期总指针数大致为：

n+np+np^2+\cdots

这是一个几何级数：

n(1+p+p^2+\cdots)

在没有最高层截断的理想模型下：

\boxed{E[\text{指针数}]=\frac n{1-p}}

如果：

p=\frac12

那么：

E[\text{指针数}]=2n

平均每个节点约有两个前向指针。如果：

p=\frac14

那么：

E[\text{指针数}]=\frac43n

平均每个节点约有1.33个前向指针。

晋升概率	平均每节点前向指针数	主要特点
1/2	2.00	较多高层索引
1/4	1.33	节省指针存储
1/8	1.14	更少索引、可能需要更多水平搜索

当然，这还不包括节点本身、内存分配器开销、指针数组头部、额外的排名信息等。因此不能简单地说“跳表比平衡树一定省内存”。具体效果取决于实现细节。Pugh 在论文中研究了不同晋升概率对性能与空间的影响，而不是把1/2视为唯一正确的选择。^{[g-trees.github.io]}

一个有趣的优化思路

如果内存非常紧张，减少晋升概率可以降低平均索引指针数量。但索引变稀疏后，搜索时可能需要沿着每一层走更远。于是又回到了我们熟悉的算法权衡：使用更多空间加速查询，还是节省空间、接受更多比较？这与第四章哈希表的负载因子、第十七章布隆过滤器的 bit/元素预算，都体现了同一种工程思想。

第八幕：1990年，Pugh 又发现跳表不只能查找

1989年的跳表研究主要让人们看到：它是一种可以替代平衡二叉搜索树的动态有序结构。但有序数据结构还要解决很多其他问题。例如：寻找第1000个元素。查询某个元素的排名。合并两张有序表。拆分一个范围。从某个已知节点开始，继续寻找附近的另一个节点。Pugh 很快又写出一份重要技术报告：A Skip List Cookbook（《跳表食谱》）。报告初稿标注为1989年7月，1990年6月进行了修订。其中讨论了搜索指针（Search Fingers）、排名操作、合并、拆分和连接等扩展算法。^{[webdiis.unizar.es]}

为什么“排名”很有价值？

假设跳表中保存：10、20、30、40、50、60、70你需要找到：“第5个元素是什么？”普通跳表如果只保存向前指针，可能还是要沿底层数。但我们可以为每条高级索引增加一个跨度（Span）。例如：从20直接跳到60。这条指针可以记录：中间跨越了多少个底层节点。那么查询排名时，不仅能够跳过大量元素，还能累计跳过的数量。这就可以支持按名次定位。这里又出现了一种经典的数据结构设计方法：在原有索引上添加少量辅助信息，让它支持更多查询类型。并不是所有跳表都需要跨度。但如果要实现排行榜、按排名分页和范围检索，它就可能非常有价值。

第九幕：Redis 为什么选择跳表管理有序集合？

现在，我们终于来到一个很多后端开发者都熟悉的系统。Redis。Redis 有一种重要的数据类型：Sorted Set，有序集合，通常简称 ZSET。它保存一组不重复的成员。每个成员对应一个数值分数（score）。例如，我们可以用它保存游戏排行榜。

玩家 Alice：950
玩家 Bob：1230
玩家 Carol：880
玩家 David：1510

现在用户提出几种请求：查询 Bob 的分数。修改 Alice 的分数。找出排名前十的玩家。查找分数在900到1500之间的玩家。这些请求包含两种不同的访问模式。按成员查找，以及按分数排序和范围查询。哈希表非常擅长前者。跳表则适合后者。这也是 Redis 的经典 ZSET 实现同时使用哈希表与跳表的原因。Redis 官方源码 src/t_zset.c 的说明明确写道：有序集合中的元素同时保存在哈希表和跳表中，一个结构负责成员到分数的定位，另一个负责按照分数维护有序视图。^[GitHub]

Redis ZSET 的双索引结构

同一组元素，两种访问方式

查看 SVG 配图原件

18-005.svg · 点击查看大图

但这里必须补充一个很重要的现实细节。Redis 并不是每一个 ZSET 都无条件采用跳表。为了节省内存，现代 Redis 对较小的有序集合可以采用紧凑的 listpack 编码。当集合变大或元素长度超出相应限制时，才会转换为常规的跳表加哈希表编码。Redis 官方 OBJECT ENCODING 文档明确区分了 skiplist 与 listpack 两种有序集合内部编码。^[Docs]因此，如果你在 Redis 中创建一个只有几条数据的排行榜，然后检查其内部结构，很可能发现它根本没有使用跳表。这不是课程讲错了，而是工业软件会根据规模切换不同的数据结构。

实际 Redis 命令

ZADD leaderboard 950 Alice
ZADD leaderboard 1230 Bob
ZADD leaderboard 880 Carol
ZADD leaderboard 1510 David

查询排行榜：

ZREVRANGE leaderboard 0 2 WITHSCORES

结果按分数从高到低排列。查询分数：

ZSCORE leaderboard Bob

修改分数：

ZINCRBY leaderboard 100 Alice

这意味着 Alice 的位置可能发生变化。常规跳表实现需要删除旧的有序位置，再插入新的有序位置。而哈希表中的成员分数映射，也必须保持对应更新。你会发现：Redis 不是因为跳表“比红黑树先进”才选择它，而是因为跳表能以相对直观的结构支持有序插入、删除、排名和范围访问。

第十幕：跳表与 AVL、红黑树、B+树究竟应该怎样选择？

到了这里，我们已经学过好几种有序数据结构。似乎它们都在解决同一件事：维护一个可以快速查找和更新的有序集合。为什么没有一种结构彻底取代其他结构？因为不同系统要求不同。

数据结构	查找复杂度	更新复杂度	核心特点
普通有序链表	$O(n)$	定位后局部修改 $O(1)$	结构简单
AVL 树	最坏 $O(\log n)$	最坏 $O(\log n)$	严格高度平衡
红黑树	最坏 $O(\log n)$	最坏 $O(\log n)$	较宽松的平衡约束
跳表	期望 $O(\log n)$	期望 $O(\log n)$	随机层数、局部指针更新
B+树	$O(\log_B n)$ 级节点访问	$O(\log_B n)$ 级节点访问	适合页式索引与范围扫描

这里的

B

可理解为节点的典型分支规模，具体 I/O 复杂度还取决于存储模型。

如果我需要最坏情况的确定性保证

AVL、红黑树等平衡树非常有吸引力。它们不依赖随机抽样得到较好树高。

如果我希望代码结构相对简单、支持有序操作

跳表可能是一个很好的选择。尤其在一些需要并发访问的场景中，跳表的局部指针结构为不同的并发实现策略提供了研究空间。但这并不意味着实现并发跳表天然容易或没有竞争条件。Pugh 在后续研究中专门讨论了并发维护跳表的正确性与同步问题。^{[drum.lib.umd.edu]}

如果数据存储在磁盘上，按页读取

B+树通常更加适合。因为每个内部节点可以容纳大量键和子节点引用，从而降低需要访问的页数。单纯采用指针式跳表，未必具备良好的磁盘访问局部性。所以：数据结构的选择，不只是比较渐近复杂度，还要考虑存储介质、缓存局部性、更新模式、并发控制及实现成本。

第十一幕：自己写一个跳表

现在我们实现一个完整的基础版本。它支持插入、查找和删除。为清晰起见，使用整数键、不存储重复键，并限制最大层数。

import random


class SkipNode:
    def __init__(self, key, level):
        self.key = key
        self.forward = [None] * level


class SkipList:
    def __init__(self, p=0.5, max_level=16):
        self.p = p
        self.max_level = max_level

        self.level = 1
        self.head = SkipNode(None, max_level)

    def random_level(self):
        level = 1

        while (
            level < self.max_level
            and random.random() < self.p
        ):
            level += 1

        return level

    def search(self, key):
        current = self.head

        for i in range(self.level - 1, -1, -1):
            while (
                current.forward[i] is not None
                and current.forward[i].key < key
            ):
                current = current.forward[i]

        current = current.forward[0]

        return (
            current is not None
            and current.key == key
        )

    def insert(self, key):
        update = [None] * self.max_level
        current = self.head

        # 找到各层的前驱节点
        for i in range(self.level - 1, -1, -1):
            while (
                current.forward[i] is not None
                and current.forward[i].key < key
            ):
                current = current.forward[i]

            update[i] = current

        current = current.forward[0]

        # 不插入重复键
        if current is not None and current.key == key:
            return False

        new_level = self.random_level()

        if new_level > self.level:
            for i in range(self.level, new_level):
                update[i] = self.head

            self.level = new_level

        node = SkipNode(key, new_level)

        # 在每一层插入新节点
        for i in range(new_level):
            node.forward[i] = update[i].forward[i]
            update[i].forward[i] = node

        return True

    def delete(self, key):
        update = [None] * self.max_level
        current = self.head

        for i in range(self.level - 1, -1, -1):
            while (
                current.forward[i] is not None
                and current.forward[i].key < key
            ):
                current = current.forward[i]

            update[i] = current

        current = current.forward[0]

        if current is None or current.key != key:
            return False

        for i in range(self.level):
            if update[i].forward[i] is current:
                update[i].forward[i] = current.forward[i]

        # 去掉已经空置的最高层
        while (
            self.level > 1
            and self.head.forward[self.level - 1] is None
        ):
            self.level -= 1

        return True

使用：

skip = SkipList()

for value in [50, 10, 30, 20, 40]:
    skip.insert(value)

print(skip.search(30))  # True
print(skip.search(35))  # False

skip.delete(30)

print(skip.search(30))  # False

这段程序的关键并不在 random_level()，而是在 update[]。update[i] 保存了第 i 层中新节点插入位置之前的最后一个节点。因此，我们只需要修改：

node.forward[i] = update[i].forward[i]
update[i].forward[i] = node

就能完成该层插入。这两句代码，其实就是我们第一章讲过的链表插入操作。只不过在多个索引层重复执行。

终章挑战：连续插入有序数据，会发生什么？

假设你需要依次插入：10、20、30、40、50、60、70、80普通二叉搜索树，如果没有平衡策略，可能退化成单链结构。那跳表呢？

哪一种说法最准确？

跳表一定退化，因为插入顺序已经排好跳表一定生成完美平衡结构跳表的层数独立随机生成，仍有期望对数级性能，但最坏可能退化跳表每次查找都只需一次比较

这个问题揭示了跳表最重要的发明思想。随机化并不是胡乱选择。它是一种可以通过概率理论分析的设计方法。算法有意放弃严格形状约束，用独立随机选择换取实现简单和良好的期望性能。

尾声：一位研究者发现，平衡也可以交给概率

1989年，William Pugh 在 WADS 发表跳表研究。1990年，他在 Communications of the ACM 进一步介绍这种数据结构。随后，跳表被应用于有序索引、并发数据结构和各种内存存储系统。在 Redis 的有序集合中，它与哈希表组合，一种结构负责按成员快速定位，另一种负责按分数维护顺序。但它最值得记住的价值，并不是“Redis 使用了它”。而是它改变了我们对平衡数据结构的理解：为了得到期望良好的结构，不一定要在每次操作后强制修复所有不平衡。有时候，采用一个数学上经过分析的随机过程，也能让系统以很高概率保持足够好的形状。回顾我们整个系列，会发现这种思想并不孤立。快速排序可以通过随机选择 Pivot，降低固定输入反复触发坏分区的风险。布隆过滤器利用概率模型，换取极少的存储空间。而跳表则利用随机化，把有序数据结构的维护规则变得更加简洁。它们共同告诉我们：确定性的最坏情况保证、概率性的期望性能、代码复杂度和实际运行成本，是不同的设计维度。不存在适用于所有系统的唯一答案。

第十八章知识总结

概念	核心思想
Skip List	多层有序链表索引
Random Level	插入时随机决定节点层数
Promotion Probability	控制节点进入更高层的概率
Expected Complexity	搜索、插入、删除期望 $O(\log n)$
Worst Case	极端情况下可能退化到 $O(n)$
`update[]`	保存各层的插入或删除前驱
Span	记录跳过的底层节点数量，支持排名
Redis ZSET	经典常规编码结合哈希表与跳表
Probabilistic Balancing	通过随机化而非严格旋转维护索引

本章原始与工程资料

Pugh 1989年 WADS 会议发表记录 Pugh 1990年：《Skip Lists: A Probabilistic Alternative to Balanced Trees》完整论文 Pugh：《A Skip List Cookbook》原始技术报告 Pugh：《Concurrent Maintenance of Skip Lists》Redis 源码：t_zset.c，跳表与哈希表的实现 Redis 官方文档：Sorted Set 的 listpack 与 skiplist 编码

下一章预告

第十九章：缓存算法的战争——1966年，为什么“最近用过的数据”不一定值得保留？

1960年代，计算机内存仍然十分宝贵。当一台计算机只有有限数量的内存页面，却需要运行远远超过内存容量的程序时，就必须不断决定：哪些页面留在内存里？哪些页面应该被替换出去？一种直观想法是：最久没有使用的页面，也许未来最不可能再使用。这就是 LRU（Least Recently Used，最近最少使用）策略的核心。但1966年，研究人员 László Bélády、Robert Nelson 和 Gerald Shedler 发现了一个极为奇怪的现象：对于某些页面替换算法，增加内存页面数量，反而会让缺页次数变多。这后来被称作 Bélády's Anomaly（贝拉迪异常）。下一章，我们将研究 FIFO、LRU、OPT、Clock，以及后来 ARC 等缓存替换算法的真实发展历史，并通过交互实验回答一个特别反直觉的问题：为什么给程序更多内存，某些情况下却可能让它运行得更慢？

第一幕：为什么1989年还需要另一种有序数据结构？

Pugh 的选择：不追求严格保证，而追求高概率

第二幕：从一条普通链表开始

如果我们增加一条快速通道呢？

第三幕：1989年，Pugh 的核心发明——让随机数替代平衡规则

实验一：你来给新节点抛硬币

随机层数生成器

第四幕：从最高层开始查找，为什么会更快？

实验二：一步步搜索70

Skip List 单步搜索器

第五幕：为什么随机跳表的期望搜索时间是 O(log⁡n)O(\log n)O(logn)？

但为什么不是最坏 O(log⁡n)O(\log n)O(logn)？

第六幕：跳表为什么不需要像 AVL 树那样旋转？

假设35随机获得三层

删除也类似

第七幕：内存会不会因为多层指针而爆炸？

一个有趣的优化思路

第八幕：1990年，Pugh 又发现跳表不只能查找

为什么“排名”很有价值？

第九幕：Redis 为什么选择跳表管理有序集合？

Redis ZSET 的双索引结构

实际 Redis 命令

第十幕：跳表与 AVL、红黑树、B+树究竟应该怎样选择？

如果我需要最坏情况的确定性保证

如果我希望代码结构相对简单、支持有序操作

如果数据存储在磁盘上，按页读取

第十一幕：自己写一个跳表

终章挑战：连续插入有序数据，会发生什么？

尾声：一位研究者发现，平衡也可以交给概率

第十八章知识总结

本章原始与工程资料

第十九章：缓存算法的战争——1966年，为什么“最近用过的数据”不一定值得保留？

第五幕：为什么随机跳表的期望搜索时间是 $O(\log n)$ ？

但为什么不是最坏 $O(\log n)$ ？