跳表：给有序链表装上电梯，从原理到调优一次讲透

先说一个特别朴素的困惑：为什么有序链表在教科书里永远被当成“低效”的代表，可你跑去拆一个开源数据库的有序集合实现，看到的底层结构却总是跳表（Skip Table，也常叫 Skip List）？第一次接触跳表的人，多半会对着那一层叠一层的指针图发愣。我当时也一样，觉得这东西既不像树那么“正统”，又不像哈希表那么直观，到底凭什么把查询复杂度做到 O(log n)？后来真正把它看懂、亲手实现过一遍，才发现它其实是一个非常顺理成章的设计——本质上就是“给链表架几层电梯”。

这篇文章我想把跳表的原理、复杂度推导、代码实现、参数调优，以及我实际踩过的坑完整讲一遍。适合刚学完基础数据结构、想知道“跳表到底是什么”的读者，也适合在工程里需要做有序集合选型的朋友。不需要你预先会红黑树，只要你认识链表和二分查找，就能顺着思路把跳表整个吃透。

1. 跳表要解决的那个最原始的问题

1.1 有序链表的最大短板

假设你现在有一个有序链表，里面存了 10000 个分数。你要查某个分数是否存在，只能从头节点开始，沿着 next 指针一个一个往后走。运气好目标就在头部，运气不好就得遍历到最后，平均要走 5000 步。往链表里插入一个数倒是很简单，只要找到合适位置改两个指针就行，但问题恰恰出在“找到合适位置”这一步——它同样需要 O(n) 的比较。

你会想，那为什么不用数组？数组支持二分查找，查一次只需要 O(log n) 次比较，不比链表强多了？问题在于数组的插入和删除很痛苦：往中间插一个元素，后面所有元素都要往后挪，最坏情况是 O(n)。所以现实里我们常常面临一个二选一：要么查询快但插入慢，要么插入快但查询慢。

这种矛盾就是跳表诞生的背景。它想做的事情非常贪心：链表本身插入快、删除快，那就想办法把链表的查询速度也提上来，让三个操作都做到 O(log n)。

1.2 “加几层电梯”的思路是怎么冒出来的

先别急着看代码，我们用最朴素的方式推演一遍。假设你有一列排好序的火车车厢，每节车厢都只把手伸向下一节。你要找尾部的车厢，只能一节一节走过去，这就是普通链表。

现在换个做法：在每隔一节车厢的上方，搭一条“快速通道”，让这一层只连接原来一半的车厢。这样找尾部车厢时，你可以先在快速通道上跳着走，走到接近目标时再下到普通层慢慢找。如果车厢足够多，你还可以搭第三层、第四层，每层都只保留上一层约一半的节点。这就是跳表的核心直觉。

用术语说，这叫做“空间换时间”。为了加速查找，你需要额外维护若干层索引指针；每一层都是原链表的一个稀疏子序列。最高层节点最少，往下逐层加密，最底层才是包含所有节点的完整有序链表。查找时从最高层开始，优先大步跳跃，走不动了就降一层继续走。因为有概率保证每层节点数近似减半，所以从顶层一路降到底层的总步数大约就是 O(log n)。

理解了这一层，后面所有实现细节都顺理成章了，跳表不过就是“随机化版本的稀疏索引”。

2. 跳表的结构定义与复杂度理论

2.1 节点结构和层级指针

跳表的节点和普通链表节点最大的区别是：它不再只有一个 next 指针，而是持有一个“指针数组”，每个元素对应一层的下一个节点。

用 Python 描述，节点结构大概是这样的：

import random class Node: def __init__(self, score, value=None, level=1): self.score = score # 排序关键字 self.value = value # 存储的附属数据 self.forward = [None] * level # forward[i] 指向第 i 层的下一个节点

这里的forward[0]就是普通链表里的 next 指针，forward[1]指向第二层索引中的下一个节点，以此类推。一个节点被创建时，它的层数是随机决定的：最低一层，最高不超过某个上限MaxLevel。

整个跳表还有一个固定的头节点header，它不存真实数据，只充当所有层链表共同的起点。它的forward数组长度直接开满MaxLevel，保证从哪一层出发都能找到入口。尾部则用None表示。

从结构上可以看出，跳表本质上是一组“叠在一起的有序链表”。第 0 层包含全部节点，第 1 层只包含一部分节点，第 2 层包含更少的一部分。这也是为什么它叫“层”，不叫“树”——它们之间没有父子关系，只有同一条链表上的稀疏关系。

2.2 为什么期望复杂度是 O(log n)

跳表的复杂度推导是它理论中最有意思的部分，因为它不是一个确定性的数据结构，而是一个随机化数据结构。你需要先接受一个概率模型。

假设每一层节点晋升到上一层的概率是p。那么对于一个包含 n 个节点的跳表，第 0 层有 n 个节点，第 1 层的期望节点数是n * p，第 2 层是n * p^2，第 i 层就是n * p^i。

如果我们把最高层设计成大约只有 1 个节点，那么层数 L 应满足：

n * p^(L-1) ≈ 1

两边取对数可以得到：

L ≈ log_(1/p)(n) + 1

所以当 p = 0.5 时，层数大约是log2(n) + 1。n = 100 万时，最高层大约只有 21 层左右。这从直觉上解释了为什么跳表查询快：你只需要沿着二十几层索引往下走，而不是在一百万个节点里平推。

接下来看一次查找到底要走多少步。查找过程从最高层开始，每一层我们会沿着当前层向右移动，直到下一个节点的 score 大于目标值为止，然后降一层。在某一层上，连续经过的节点数不会太多：因为每个节点能晋升到上一层的概率是 p，如果这一层连续走了 k 个节点都没碰到可以晋升的节点，概率就是(1-p)^k，随着 k 增大迅速衰减。所以每一层期望只走大约1/p步。把层数 L 乘进去，总期望步数就是：

O(L * (1/p)) = O((1/p) * log_(1/p)(n))

p 是常数，所以最终就是 O(log n)。

这里必须强调“期望”两个字。跳表不保证每次查询都是 O(log n)，极端情况下，如果随机层数全部生成成 1，整个跳表就会退化成一个普通链表，查询变成 O(n)。但这种极端情况发生的概率极低，而且我们可以通过控制 p 和 MaxLevel 把风险限制在可接受范围内。这是它和平衡树本质上的区别：平衡树靠旋转强制平衡，跳表靠概率让结构“大概率平衡”。

插入和删除的复杂度也同样是 O(log n)。插入时，你需要先做一次查找，记录每层最后一个小于目标值的前驱节点；删除时同理，先找到目标，再把各层指向它的指针跳过它。瓶颈都在查找这一步，所以整体的期望代价和查询是一致的。

3. 手写一个跳表：核心操作完整实现

3.1 查找：从最高层开始

查找是理解跳表操作的第一步。核心逻辑只有一句话：从最高层开始，只要下一个节点不越界且它的 score 小于目标值，就向前跳；否则降一层继续。

def find(self, target_score): cur = self.header # 从当前实际最高层开始，逐层向下 for i in range(self.level - 1, -1, -1): while cur.forward[i] is not None and cur.forward[i].score < target_score: cur = cur.forward[i] # 此时 cur 是第 0 层中最后一个 score < target_score 的节点 nxt = cur.forward[0] if nxt is not None and nxt.score == target_score: return nxt.value return None

注意这里查找的终止条件是cur.forward[i].score < target_score，不是<=。也就是说，我们总是停在“严格小于目标值”的最后一个节点上，这样下一步再往前走一个节点，要么正好命中目标，要么说明目标不存在。这个细节很重要，后面插入和删除都要依赖同样的位置定义。

为什么必须从最高层开始，而不是从第 0 层开始？因为跳表索引的意义就是“跨大步”。如果你从第 0 层开始，你只会一个节点一个节点地走，那 O(log n) 的优势就完全不存在了。最高层的节点数最少，但每跳一次跨越的实际距离最大，这正好用上了“随机晋升”带来的概率结构。

3.2 插入：update 数组是灵魂

插入要比查找多一个关键步骤：记录每层的前驱节点。因为你最终要把新节点挂到每一层链表上，而每一层挂的位置可能不同，所以必须知道每一层里“最后一个小于新 score 的节点”是谁。

我用一个update数组来保存这组节点：

def insert(self, score, value): cur = self.header update = [None] * self.max_level # 第一步：查找，同时记录每层前驱 for i in range(self.level - 1, -1, -1): while cur.forward[i] is not None and cur.forward[i].score < score: cur = cur.forward[i] update[i] = cur # 第二步：目标已存在则更新值 nxt = cur.forward[0] if nxt is not None and nxt.score == score: nxt.value = value return # 第三步：生成新节点层数 new_level = self.random_level() if new_level > self.level: # 更高层的 update 直接指向 header for i in range(self.level, new_level): update[i] = self.header self.level = new_level new_node = Node(score, value, new_level) # 第四步：逐层拼接指针 for i in range(new_level): new_node.forward[i] = update[i].forward[i] update[i].forward[i] = new_node

第一次写跳表的人最容易漏掉第三步里的“提升实际层高”。当随机出来的新节点层数比当前跳表的最高层还高时，你需要补齐update数组里那些新增的高层位置。这一层之前根本没有节点，所以前驱只能是header。如果你漏掉这一步，update[i]会是一个空引用或垃圾值，代码会在拼接指针时直接崩溃。

还有一个容易踩的细节：如果目标 score 已经存在，我们是只更新 value，而不做插入的。这个判断必须在修改结构之前完成，否则你会把同一个 score 的节点插入两次，破坏有序性。

3.3 删除：逐层拆桥

删除逻辑几乎是插入的镜像，核心同样是先找到每层前驱：

def remove(self, score): cur = self.header update = [None] * self.max_level for i in range(self.level - 1, -1, -1): while cur.forward[i] is not None and cur.forward[i].score < score: cur = cur.forward[i] update[i] = cur target = cur.forward[0] if target is None or target.score != score: return False # 从每一层摘除 target for i in range(self.level): if update[i].forward[i] is target: update[i].forward[i] = target.forward[i] # 如果最上层只剩 header 的空指针，可以降低跳表层数 while self.level > 1 and self.header.forward[self.level - 1] is None: self.level -= 1 return True

删除里有一个很多人会忽略的问题：当你把节点从所有层摘除之后，最上面的几层可能已经没有任何实际节点了，只剩下header指向None的空指针。这种情况下如果不降层，查找每次都会从很高的空层开始，白白浪费一次循环。所以主动“压缩层高”是必要的。

还要注意，target可能是一个高层节点，但它不一定出现在当前所有层。比如它只有 3 层，而跳表当前有 5 层，那么在 3 层以上的update[i].forward[i]一定不等于target，if判断会自然跳过，不会误改指针。

4. 随机化参数与调优心得

4.1 p 到底选 0.5 还是 0.25

跳表的随机层数生成通常是这样实现的：

def random_level(self): lvl = 1 while random.random() < self.p and lvl < self.max_level: lvl += 1 return lvl

每向上晋升一层，概率是 p。p 越大，索引越密集，查找时跨越的步数越少，但代价是内存占用增大；p 越小，索引越稀疏，省内存但查找时要多走几步。常用值是 0.5 和 0.25，它们各有取舍，我整理了一个粗略对照：

为什么 p = 0.25 在很多工程实现里很流行？因为空间省得很明显。从期望角度算，每个节点的平均层数是1 / (1-p)。p = 0.5 时平均层数是 2，p = 0.25 时平均层数是 1.33。也就是说 p = 0.25 时，每个节点平均只多出大约三分之一的开销。而查询代价只从2 * log2(n)左右变成4 * log4(n)左右，实际绝对步数差别并不大。

我个人的习惯是：如果节点数据量在百万以内，直接用 p = 0.25；如果内存比较紧张而且数据量上亿，可以考虑 p = 0.125，前提是你能接受查询时间的上升。做工程选型不要迷信“默认值”，要拿真实数据去压测。

4.2 MaxLevel 怎么定

跳表需要一个最大层数上限，防止极端情况下随机数一直晋升到非常离谱的层数。MaxLevel 的经典取值可以这样计算：

MaxLevel = ceil(log_(1/p)(N)) + 1

其中 N 是你要存储的最大节点数期望值。如果 N = 2^32，p = 0.25，那么log4(2^32) = 16，再加 1，取 32 层左右足够了。很多开源实现干脆直接固定用 32 或 64，因为指针数组本身开销不大，留一点余量可以避免边界问题。

这里想提醒一个容易犯的错误：MaxLevel 设得太大并不会让跳表变快，反而会让每次操作都要循环更多空层；设得太小又会在插入时频繁触发“提升层高但被截断”的情况，破坏跳表本来的概率分布。一个合理的检查标准是：随机生成出来的层数分布应该大致符合几何分布，最高层数只在数据量真的接近上限时才偶尔触顶。

4.3 内存占用、随机数质量与可复现性

跳表的内存开销可以精确算出来。每个节点除了数据本身，还要存一个forward数组。数组长度等于随机层数，期望层数为1 / (1-p)。所以 n 个节点的跳表，额外指针数约为n / (1-p)。这个开销比 AVL 树或者红黑树里每个节点固定存两个子节点指针要略多一点，但差距不大。

随机数的质量对跳表性能影响非常大。如果你用的随机数生成器有缺陷，或者每次都重新 new 一个生成器，可能会导致层数分布不均，进而让大量节点集中在一层，跳表退化成链表。我之前用过一次线程局部随机数没有正确初始化种子的实现，结果前 1000 个插入节点的层数全部是 1，查询慢到没法忍。后来我在随机层数生成外面加了一层统计，才定位到是随机数种子的问题。

另外，如果你希望每次运行都能复现同样的层数分布，方便调试，可以给随机数生成器固定一个种子。这在定位“为什么这步操作指针变了”的时候尤其有用。

5. 跳表和经典数据结构的横向对比

5.1 跳表 vs 平衡树

最常见的对比问题就是：跳表和红黑树、AVL 树比，到底赢在哪？

平衡树实现有序集合有一个非常烦人的地方：每次插入和删除都可能打破平衡，你需要通过旋转操作或变色规则来重新调整。AVL 有四种旋转情况，红黑树有一堆 case 要记。写起来不算难，但写对并长期维护是需要细心和经验的。跳表则完全没有旋转的概念，插入和删除只是纯指针修改，任何层只涉及“前驱节点”那一个指针，逻辑非常直白。

从并发角度看，跳表比平衡树友好得多。树的结构牵一发动全身，旋转会涉及多个节点之间的父子关系；跳表每一层的指针相对独立，锁的粒度可以做得更细，甚至可以用无锁方式做读操作。很多需要高并发读写的内存数据结构选跳表，看中的正是这一点。

从最坏情况看，平衡树是强保证，跳表是概率保证。虽然跳表退化成链表的概率极低，但严格的实时系统可能仍然会抗拒这样的不确定性。对这种系统，平衡树可能更合适。

5.2 跳表 vs 二分数组、B 树与哈希

这几种结构各有优势，通常不是谁能完全替代谁的问题：

哈希表在单纯等值查询上无敌，但完全无法做有序遍历和范围统计。数组二分查询块，但插入删除是硬伤。B 树把节点设计成适合磁盘页读取的块结构，在磁盘场景下比跳表更合适，但是 B 树实现复杂度比跳表高出不少。

所以在内存场景里，当你有“按分数排序”“取 TopN”“区间求和”这类需求时，跳表几乎是性价比最高的方案。它比数组灵活，比平衡树好写，比 B 树轻量。

5.3 工程场景里你会真正用到跳表的地方

我自己在实际工程里遇到跳表的典型场景有两个。

第一个是排名/排行榜服务。数据不断插入、更新、删除，还要频繁“获取前 100 名”或者“获取某个人当前排名”。跳表天然支持按序索引，找排名就是通过 score 查找并统计前序节点数，利用每一层的跨越能力能很快定位。用数组二分没办法应对高频插入，用哈希表又不支持范围查询。

第二个是日志结构合并存储（LSM）的写缓冲。内存里需要一个能高效插入、同时能按序输出给磁盘合并的有序结构。跳表比平衡树更适合这种频繁插入的场景，因为不需要做旋转，而且实现相对简单，便于后续改成并发版本。实际上一眼看去，这类存储引擎的内存表选跳表的频率远高于红黑树。

如果你只是在做一个一次性构建、之后只读的有序列表，那用数组二分就够了，没必要上跳表。选型要贴合实际读写比例，这是我反复强调的一点。

6. 写跳表时最容易踩的坑与排查实录

6.1 从错误代码讲起的三个经典 Bug

先说第一个坑：更新前驱时只更新了第 0 层。如果你插入节点时只记录update[0]，那么在高层索引里新节点就不会被链入，之后查询高层时会直接绕过它。结果就是：节点明明在第 0 层能被找到，但高层索引永远指不到它，导致查找步数偶尔剧增。这种 bug 不崩溃，但性能会断崖式下跌，非常隐蔽。

第二个坑：删除节点后没有压缩层高。表面上看每个操作还是“实现了”，但删除大量节点后，最高层可能已经空了，查找却依然从高位空层开始。比如原来有 32 层，删到只剩 100 个节点，可能实际最高层只有 5 层，但你每次查找还会从 32 层开始循环，白白浪费 20 多次遍历。数据量小的时候看不出来，数据量大的时候会白白损失性能。

第三个坑：随机层数生成的上限处理。如果你在random_level里写的是while random.random() < p:而没有限制lvl < max_level，在极端情况下层数会无限制增长。虽然概率极低，但一旦发生，要么内存暴涨，要么header的forward数组越界。一定要加边界判断。

三个问题我都会用一个简单的检查方法验证：插入 10000 个节点后，统计每一层的节点数量，打印成表格。如果第 i 层节点数大约等于第 i-1 层的 p 倍，说明结构正常；如果某一层突然多出一大堆节点，那大概率是前驱更新漏了。

6.2 问题排查速查表

我把自己实操中遇到过的症状和原因整理成一个表，方便你对照排查：

6.3 我的验证与基准测试心得

写完一个跳表实现，我建议做的第一件事不是压测，而是正确性验证。用一个小脚本把所有 key 插入到一个列表和跳表里，然后随机删除一半，再查询所有 key，对比跳表结果和列表结果是否完全一致。这个步骤能快速暴露指针更新遗漏之类的问题。

正确性验证通过后，我会用一个构造出来的测试数据做基准：比如插入 20 万个随机 score，然后做 20 万次查询，分别看跳表、二分数组、二叉树写法的耗时。我通常会得到这样的结果：跳表和平衡树在查询上几乎同一个量级，但跳表的代码实现量要小得多。落实到具体数字上，单次查询大约都在微秒级别，对业务接口来说完全可以忽略。

有一次我压测时发现插入性能不如预期，查了很久最后发现是随机数生成器调用太频繁，成了瓶颈。后来我改成每线程一个独立的随机数生成器，插入吞吐直接上来了。这个经验说明：跳表的理论复杂度是一回事，工程优化的细节才是真正拉开差距的地方。

7. 最后，关于跳表我一直保留的几个习惯

跳表是我在实际项目中用得比较多的数据结构之一，几次踩坑之后，我给自己定了几条规矩。

第一，所有涉及层数的代码，一律从“当前实际层高”开始循环，不要从MaxLevel开始。MaxLevel是上限，不是当前高度。从上限开始会白白遍历空层，而且容易让不存在的层参与指针更新。

第二，调试阶段固定随机种子，并打印层数分布。跳表是随机化结构，不打印层数分布，你很难判断性能问题到底是随机数的问题、还是逻辑的问题。我在代码里加一个debug_stats()方法，统计每层节点数，这个习惯帮我省了很多排查时间。

第三，不要盲目崇拜 O(log n)。跳表的常数因子受 p 影响很大，同样一个排序集合，p 取 0.25 和取 0.5 的内存和查询速度可能相差将近一倍。如果你不确定怎么选，就把两种配置都压测一下，用数据说话。

跳表是个特别“顺理成章”的数据结构：想要链表查询快，就加索引；索引还不够快，就再加一层；层多了怕结构乱，就用随机数来保持概率平衡。整个设计从头到尾没有炫技，每一步都是朴素的需求驱动。看懂它之后，你会觉得那些硬背红黑树旋转规则的日子，其实可以有另一种更轻松的解法。