跳表详解：从原理到实战，Redis与LevelDB为何都选它？

跳表这东西我在读 Redis 源码的时候才真正意识到它有多巧妙。之前一直觉得“有序链表查找不就是一个个往后摸吗”直到看到 ZSET 底层用了跳表而不是红黑树才明白一个看着像玩具的数据结构居然能在工程里扛住千万级 QPS。后来自己在做 KV 存储、日志索引的时候也动手写过跳表算是把它的脾气摸了个七七八八。这篇把跳表的思想、优劣、应用场景一次讲透适合正在学数据结构、准备面试、或者想搞明白 Redis/LevelDB 底层原理的朋友。1. 跳表的核心思想——为什么用“多一层”换“快一步”1.1 先从有序链表的痛点说起有序链表大家都很熟插入、删除都是 O(1)——前提是已经知道插在哪、删哪个。问题就出在“找”这个动作上。想在一个有序链表里找某个值只能从头节点一个个往后遍历最坏情况是 O(n)。你说数据量小无所谓但一旦链表里有百万、千万个节点一次查找就要扫上百万次指针跳转这在服务端场景下根本扛不住。有人可能会说那用数组加二分查找不就行了数组确实支持 O(log n) 的随机访问但数组的插入删除是 O(n) 的因为要搬移元素。而且动态数组扩容也会带来额外开销。如果既要保持有序又要动态插入删除还要查找快单靠链表或者单靠数组都不行。我当时学到这里的第一反应是能不能给链表也搞一个“二分查找”跳表就是冲着这个问题去的。它的做法说白了很直白链表之所以慢是因为“一步只能走一个节点”那多搞几层“快速通道”让查找的时候能一次跨过一截不就行了吗这就是跳表最核心的思想——用“层”来换“步长”。1.2 跳表的设计给链表加“电梯”跳表的结构用一句话概括一个有序链表 多层索引链表。最底层是一个包含所有节点的普通有序链表保证任何元素都能被遍历到。上面每一层都是下一层的“稀疏索引”节点少一些跨度大一些。查找的时候从最顶层开始往右走、往下沉一步步逼近目标。这跟我们平时在商场里找店铺很像先通过楼层索引知道在几层再通过楼层内的区域指示找到具体位置而不是一层一层挨个店逛过去。每一层到底哪些节点“升级”上去不是人为指定的而是随机的。这个随机不是乱来它有一套概率机制后面细说。正因为有这一层层的“快速通道”跳表的查找期望时间复杂度能压到 O(log n)跟平衡二叉树一个级别。我在实际写代码的时候习惯把跳表想象成“有序链表上的多层投影”。底层的投影最完整越往上越稀疏。查找的路径就是一条从左上角到目标节点的折线每一步要么往右“跨大步”要么向下“降一层”。这个可视化模型一旦建立起来后面看插入、删除的代码都会豁然开朗。1.3 “抛硬币”决定层数概率背后的数学直觉跳表里每个节点到底有几层是通过“抛硬币”决定的每往上提升一层概率为 p常见取 0.5 或 0.25如果成功了就继续抛直到失败或者达到层数上限。经典论文里 p 取 0.5工程上为了省内存Redis 取的是 0.25。你可能会想随机决定层数还能保证 O(log n) 的复杂度这就是跳表最精彩的地方。假设链表里有 n 个节点每个节点被提升到第 k 层的概率是 p^(k-1)所以第 k 层大约有 n * p^(k-1) 个节点。当 p0.5 时你可以简单地理解为每一层的节点数是上一层的一半。这跟一棵满二叉树的层次结构是一模一样的树高大约就是 log2(n)。查找过程本质上就是在这样一棵“隐式的树”上做搜索自然也就是 O(log n)。更严格一点说跳表的期望查找时间是 O(log n)这是概率意义上的期望值不是最坏保证。理论上存在“所有节点层数都是 1”的极端情况到时候跳表就退化成普通链表查找变成 O(n)。不过这种概率低到可以忽略工程上没人真的担心这个。我自己推导过一遍如果 p0.5每个节点的期望层数是 1/(1-p)2总指针数期望是 2n。也就是说索引层的额外内存大约跟底层节点数相当整体内存开销是 O(n)。这个量级是可以接受的——大概是用“额外一倍指针”换来了“查找从 O(n) 降到 O(log n)”这笔账在大多数场景下都划算。2. 跳表的完整操作流程——查找、插入、删除怎么落地2.1 查找从上到下、从粗到细查找是跳表最核心的操作插入和删除都依赖它。流程不复杂记住一句话能往右就往右不能往右就往下。具体步骤从最高层的头节点开始。在当前层向右遍历如果下一个节点的 key 小于目标 key就继续往前。如果下一个节点的 key 大于等于目标 key 或到达当前层末尾就下移一层。重复直到第 0 层然后向右一格检查是否命中。用代码表示大概是这样的我用 C 风格写方便对应底层实现Node *skip_list_search(SkipList *list, int key) { Node *cur list-header; for (int i list-level - 1; i 0; i--) { while (cur-forward[i] cur-forward[i]-key key) { cur cur-forward[i]; } } cur cur-forward[0]; if (cur cur-key key) { return cur; } return NULL; }注意最后落到底层后需要再往右走一格判断。因为循环结束时 cur 是“最后一个 key 小于目标”的节点目标如果存在一定在 cur 的右边一格。查找的平均比较次数大概是 log2(n) 级别。实测过百万节点的跳表一次查找大概只需要 20 次左右的指针跳转相比链表逐个遍历动辄几十万次差距完全是数量级的。2.2 插入先找位置再掷硬币定层数插入分三步查找插入位置同时记录每一层最后经过的节点一般用一个update数组保存。用随机函数决定新节点的层数。从第 0 层到最高层依次把新节点链入update[i]的后面。关键点是第一步里那个update数组。它保存的是新节点插入后每一层“前一个节点”是谁。如果没有这个数组插入之后你再想逐层调整指针关系就得重新找一遍白白浪费 O(log n) 的查找时间。插入代码核心部分void skip_list_insert(SkipList *list, int key, void *value) { Node *update[MAX_LEVEL]; Node *cur list-header; for (int i list-level - 1; i 0; i--) { while (cur-forward[i] cur-forward[i]-key key) { cur cur-forward[i]; } update[i] cur; } // 如果 key 已存在直接更新 value cur cur-forward[0]; if (cur cur-key key) { cur-value value; return; } int new_level random_level(); if (new_level list-level) { // 超出当前最高层时把超出的层从 header 开始接 for (int i list-level; i new_level; i) { update[i] list-header; } list-level new_level; } Node *new_node create_node(key, value, new_level); for (int i 0; i new_level; i) { new_node-forward[i] update[i]-forward[i]; update[i]-forward[i] new_node; } }这里有个很多人第一次写会忽略的细节如果新节点的层数比当前跳表最高层还高那么超出的那些层update[i]应该指向 header而不是 null。否则新节点就跟上面的层断开了连接查找时会出现“明明在这个范围却找不到”的诡异问题。随机层数函数通常这么写int random_level() { int level 1; while ((rand() % 100) 25 level MAX_LEVEL) { level; } return level; }这里是 p0.25 的版本有 25% 的概率继续升层。取 100 的模是为了方便调整概率。工程上要注意rand()的周期和质量后面我在实操细节里专门讲。2.3 删除逆向操作的细节删除和插入的骨架几乎一样也是先找位置记录update数组然后逐层把节点「摘」下来。不过除了摘节点还要处理一个额外问题如果被删除的节点是最高层的唯一节点删除后跳表的level应该下降保持最高层不为空。删除的关键代码void skip_list_delete(SkipList *list, int key) { Node *update[MAX_LEVEL]; Node *cur list-header; for (int i list-level - 1; i 0; i--) { while (cur-forward[i] cur-forward[i]-key key) { cur cur-forward[i]; } update[i] cur; } cur cur-forward[0]; if (cur cur-key key) { for (int i 0; i list-level; i) { if (update[i]-forward[i] cur) { update[i]-forward[i] cur-forward[i]; } } free(cur); // 降低跳表层数 while (list-level 1 list-header-forward[list-level - 1] NULL) { list-level--; } } }注意降层那个 while 循环。如果不降层header 上层的空指针会越来越多查找的时候白白多了好多次“下移”虽然没有正确性问题但性能上会有不必要的损耗。删除时还要记得把每层指针都处理好别只删第 0 层——这个错误我见过不少新手犯结果就是出现“幽灵节点”底下一层没了上面索引层还指着它。2.4 区间查询跳表最顺手的场景跳表有一个经常被低估的优势区间查询。在跳表里要查某个范围内的所有 key只需要先 O(log n) 找到左边界然后沿着第 0 层链表往右走一直走到右边界为止。因为底层是有序链表这段遍历就是顺序的、连续的非常天然。这在平衡树里反而麻烦。红黑树找单个节点是 O(log n)但找区间的话你得做中序遍历还要维护前驱/后继关系代码复杂度明显更高。B树之所以在数据库里流行就是因为它把叶子节点串成了链表区间查询特别好做。跳表其实也在走同样的思路——最底层天然就是一条完整的有序链表。Redis 的ZRANGEBYSCORE就是典型的区间查询操作跳表配合一个分数到成员的映射就能高效地返回某个分数段内的所有成员。这个能力在后面应用场景部分还会展开。3. 优劣分析——跳表到底好在哪又栽在哪3.1 跳表的四大核心优势第一实现简单可维护性强。这是跳表对比平衡树最大的优势。红黑树的左旋右旋、变色、插入修复、删除修复逻辑分支多稍不留神就写错一个指针。跳表的核心就是“多层的链表”每一层操作逻辑一模一样无非是多套了一层循环。我自己写过红黑树也写过跳表红黑树花了两三天调试还是战战兢兢跳表一个下午就能跑通全部功能。这在工程上意味着什么意味着出 bug 的概率低、review 成本低、后续维护的人不用抱着《算法导论》翻半天。第二性能稳定且对数据集大小不敏感。这里说的稳定不是“保证 O(log n)”——那是不现实的跳表毕竟是概率型结构。稳定指的是它在绝大多数情况下都能跑出接近 O(log n) 的表现不会像某些哈希表那样有恶意的退化场景。哈希表在冲突严重时可能退化成 O(n)跳表不会因为它的随机性是分散在层级别上的没有一个“全局哈希函数”可以被恶意数据打穿。第三范围查询实在是太顺手了。这个前面提过跳表最底层就是有序链表天然支持顺序遍历。在需要“找出所有 score 在 [a, b] 之间的记录”这种场景跳表写起来几乎不用动脑子。第四并发控制比平衡树温和。注意我用的是“温和”不是说跳表自动解决了并发问题。而是说跳表的并发加锁粒度可以做得比较细不同的层、不同的节点段可以用不同的锁甚至可以用无锁 CAS 来实现部分操作。Redis 是单线程所以不需要考虑这些但 LevelDB、RocksDB 这类多线程写入的引擎里跳表可以做到只锁局部区间不太容易成为瓶颈。红黑树如果并发写通常需要一个全局锁因为树结构的旋转会牵扯到很多节点。3.2 不能忽视的短板先说内存。跳表每个节点平均要维护 1/(1-p) 个 forward 指针。p0.5 时约 2 个指针/节点p0.25 时约 1.33 个指针/节点。对比红黑树每个节点只有 2 个孩子指针加 1 个颜色位跳表在指针上的开销是偏高的。当然这个多出来的开销能不能接受取决于你存的是什么。如果 value 本身是几百字节的字符串多几根指针根本无所谓如果 value 是一个 8 字节整数那跳表的内存开销可能比数据本身还大。其次是缓存不友好。链表本身就是“跳着访问内存”节点在堆里不一定连续跳表的索引层更是到处分散。这跟数组或 B树那种“顺序扫一页内存”的方式没法比。在数据量大到超过 CPU 缓存时跳表的实际性能可能不如理论值好看因为指针跳转会频繁触发 cache miss。这个坑在压测时最容易暴露——小数据集跑得飞快大数据集突然变慢。再次是“最坏情况不受控”。虽然概率上几乎不可能但你没法像平衡树那样拍着胸脯说“我保证最坏 O(log n)”。如果随机数质量差或者随机种子设置不当索引层分布很可能偏斜查找性能会崩。对极端追求确定性的系统这点可能会让人犹豫。最后是调试难度被低估了。虽然代码写起来简单但跳表的结构本身就是层层嵌套的指针关系出了 bug 靠肉眼看很难找到问题。好的调试辅助是第一位的后面我给出一个简单的 dump 技巧。3.3 和平衡树、B树的横向对比维度跳表红黑树B 树查找复杂度O(log n) 期望O(log n) 最坏O(log n) 最坏插入/删除复杂度O(log n) 期望O(log n) 最坏O(log n)可能触发分裂合并实现难度低高中高内存占用较高多层指针中2 指针 色位中节点内多个 key/指针范围查询好底层有序链表一般中序遍历极好叶子链表并发友好度较好局部更新较差全局旋转较好锁叶子/分裂合并缓存局部性差链表节点分散差极好节点内连续存储工程代表Redis ZSET、LevelDB MemTableJava TreeMap、Linux 内核MySQL InnoDB、PostgreSQL从这个表能看出一个规律跳表不是在所有维度上都赢而是赢在“实现简单 范围查询友好 并发可控”的组合上。这三个特性凑在一起特别适合做内存数据结构的索引层。4. 典型应用场景——从 Redis 到 KV 存储的实战4.1 Redis ZSET为什么偏偏选跳表Redis 的有序集合 ZSET 底层是跳表 哈希表的组合哈希表负责 O(1) 的成员查找跳表负责按分数排序和范围查询。很多人问过一个问题为什么 Redis 不用红黑树实现 ZSET官方给出的理由很实在跳表实现起来更简单调试起来更方便而且 ZSET 需要大量的范围查询操作跳表的底层链表遍历比红黑树的中序遍历舒服得多。另外跳表的层数可以通过概率参数调节在内存和性能之间做权衡红黑树没有这个旋钮。在 Redis 源码里zset结构用了一个zskiplist每个节点保存成员和分数。每个跳表节点的层高是运行时随机生成的ZADD操作会先更新哈希表再在跳表里插入或更新分数。ZRANGEBYSCORE则直接利用跳表按分数查到左边界然后顺序遍历到右边界整个过程不需要遍历所有成员。作为用过 Redis 的人你应该注意到了ZRANGE的两个端点参数一个起点一个终点。这在跳表上就是从某个位置开始沿链表走一段效率非常可观。如果是红黑树要实现ZRANGEBYSCORE还需要在节点里额外维护子树大小或者做中序遍历代码量会翻倍。Redis 作者选择跳表确实是在工程实现和性能之间做了一个非常合理的取舍。4.2 LevelDB / RocksDB 的 MemTable为什么跳表能扛住高并发写LevelDB 和 RocksDB 的 MemTable 默认实现就是跳表。这里有一个关键背景MemTable 是一个内存中的有序结构所有写入要先写到这里然后定期刷盘成 SSTable。而写入方往往是多线程的对有序结构的要求是插入要快、查询要快、而且并发插入不能互相阻塞太久。如果 MemTable 用红黑树多线程插入时会涉及频繁的旋转和变色冲突区域可能很大用跳表的话每个插入操作影响到的只是前后几个节点的指针容易做到细粒度加锁。RocksDB 的跳表实现里甚至做了无锁并发插入——通过原子指针操作允许不同线程同时在不同位置插入只需要在 header 和新节点的层指针更新处做同步。这个其实是跳表结构特性的胜利。我之前拿 LevelDB 的 MemTable 做过简单的压测百万级写入跳表的写入吞吐明显优于一般的有序数组实现。而且因为跳表按 key 有序刷盘时直接顺序遍历就能生成有序的 SSTable 数据省去了额外的排序步骤。这种“天然有序 并发友好”的组合是它在这个场景胜出的根本原因。4.3 Kafka 等日志/消息系统的索引Kafka 的 TimeIndex 和 OffsetIndex 使用的是更像是“稀疏数组 二分”的方案但跳表在一些日志系统里依然有位置。凡是需要在内存中维护“按时间或偏移量有序”的索引结构跳表都是一个非常顺手的候选——写日志是顺序追加但查找某条记录可能按时间区间来查跳表的底层链表让顺序扫描非常舒服上层的索引又让随机跳转足够快。不只是 Kafka很多自研的时序数据库、监控系统在缓存最近一段时间的指标时也有人在用跳表做 TTL 过期和按时间范围查询。因为跳表不仅能快速定位某个时间点还能沿着链表把某个时间段内的所有数据都捞出来这个能力在某些场景下比 B 树还顺手。4.4 什么场景不要用跳表跳表不是银弹。我的经验是以下三类场景要谨慎嵌入式和极低内存设备。跳表节点指针数量多如果 value 本身很小内存浪费比例很高。这时候一个紧凑的 B树或者平衡树往往更合适。严格性能上限的场景。跳表的最坏情况是 O(n)虽然概率低但如果你的系统必须对每一次查询提供硬实时保证跳表不满足这个要求。理论上应该选最坏复杂度有保证的红黑树、B树或者其他结构。大量随机写且中间节点经常更新。跳表支持删除和插入都很方便但如果你会高频修改已有节点的排序 key那就意味着频繁的“删除 重新插入”每一轮都要走两遍 O(log n) 路径。这时候不如考虑一个天然的“可更新 key”的结构甚至直接上哈希表。5. 实操细节——把跳表用好的最后一公里5.1 参数选择MAX_LEVEL 和 p 值的经验值跳表有两个全局参数需要定层数上限MAX_LEVEL和提升概率p。经典论文里 p 取 0.5也就是“每层节点数约为上层的一半”数学上最优。但工程上 p0.5 意味着每节点平均 2 个指针内存开销偏大。Redis 的实现里 p 取 0.25、ZSKIPLIST_MAXLEVEL取 32。p0.25 时每节点平均指针数约 1.33内存开销小很多而查找复杂度仍然在 O(log n) 的量级——常数会大一点点但大多数时候根本感觉不到。如果你做的是读多写少的内存服务可以试试 p0.5如果内存紧张p0.25 是稳妥的选择。MAX_LEVEL的取值要跟数据规模匹配。一个经验公式是MAX_LEVEL log(1/p)(n_max)。比如 p0.25期望最高层大约在 log4(n) 层n1000000 时大概 10 层32 层已经非常宽裕。设太小会增大“封顶”后继续提升的浪费设太大又浪费内存。我在实际项目里一般设 32极少有需要 64 的场景。5.2 几个我踩过的坑随机数质量太差导致层数分布不均。第一次写跳表时直接用rand() % 100小数据跑着没事数据量一上来发现查找时间忽高忽低。排查后发现rand()的周期只有 2^31而且低位的随机性并不好。建议改用xorshift或pcg这类高质量的伪随机数生成器或者至少使用(rand() 4) % 100来取高几位。Redis 用的是自定义的zslRandomLevel算法简洁且分布稳定值得参考。忘记处理“层数超过当前最高层”的情况。插入一个新节点它的层数可能比当前跳表的层数还要高。这时候必须把超出的那些层update[i]指向 header并且把list-level更新到新层数。我见过有人在插入后没有更新list-level结果下次查找从旧的顶层开始把新层完全漏掉了。并发环境的 ABA 问题。无锁跳表不是简单的 CAS 就能搞定经典的实现比如 Fomitchev 的算法会比较复杂需要处理多个层的指针同时更新的一致性。生产项目里如果没把握老老实实加锁比写出一个隐晦的并发 bug 要好得多。RocksDB 的无锁跳表代码是经过多年打磨的不要轻易自己造轮子。5.3 怎么快速调试一个跳表实现跳表调试最大的痛点是“看不见”。数组你可以打印下标链表你可以打印指针和值跳表多了一层层的结构最好的调试手段就是写一个 dump 函数把每一层的链表从头到尾打出来void skip_list_dump(SkipList *list) { for (int i list-level - 1; i 0; i--) { printf(Level %d: , i); Node *cur list-header-forward[i]; while (cur) { printf(%d , cur-key); cur cur-forward[i]; } printf(\n); } }打印出来以后你要检查三个性质底层包含所有元素第 0 层必须是有序且完整的。上层是下层的子集第 i 层出现的节点在第 i-1 层也必须出现且顺序一致。跳表层数正确最高层要么是 header 的空层要么只有一个节点或者几个分得足够开的节点不会出现高层比底层元素还多的情况。这三个检查过一遍能过滤掉九成以上的指针操作错误。剩下那成错误的几乎都出在“删除后层数没有降低”或者“update 数组用错了位置”这两个地方。最后再分享一个小技巧如果你需要在一台机器上同时维护多个有序集合而且不想写多份代码可以在节点结构里加一个span字段记录“当前节点在第 i 层到下个节点之间跨了多少个底层节点”。这个span字段是实现 O(log n) 的ZRANK计算成员排名和ZREVRANK的关键。我第一次读 Redis 源码时对span的作用困惑了很久后来自己实现了一遍才发现有了它“按排名访问”和“按成员查排名”都是顺路的事。如果只是想做一个基础版的跳表可以先不加但如果想往 Redis 那种完整功能靠拢span一定要尽早加上不然后面再改会牵一发动全身。跳表看着像一个“带索引的链表”但它背后其实是把“随机化”和“分层递进”这两个思想用在了最朴素的数据结构上。多年下来我的体会是很多性能问题的解法并不需要多高深的理论缺的往往是从“能不能多加一层”这个角度去想问题。