跳跃表这个结构我一直觉得它是数据结构里被低估的巧思。它不像红黑树那样需要一堆旋转操作和颜色标记也不像B树那样动辄牵扯磁盘页和分裂合并却能在有序数据上做到平均 O(log n) 的查找、插入和删除。更绝的是它的实现思路简单到让人怀疑就是一个链表再加几层索引仅此而已。这篇文章想聊明白两件事一是跳跃表为什么能快快在哪个环节二是真要在工程里落地它那些教科书不会明说的边界条件和取舍。无论你是在准备面试、要手写一个有序结构还是在调研某类存储引擎的索引方案这篇都应该对你有用。1. 为什么有序链表会慢而跳跃表能绕开这个瓶颈1.1 从一次朴素查找说起单向链表的天花板先做一个思想实验。假设手里有一个有序的单项链表里面存了 1 到 100 这些有序整数。现在要查找数字 66。最诚实的做法是从头节点开始一个个往后走1、2、3……走到 66 才停。如果数据量变成一千万那一次查找平均要走五百万步。链表不像数组它没有随机访问的能力只能靠指针硬着头皮顺藤摸瓜。所以它的查找复杂度是 O(n)。这个“n”在数据量上来之后是灾难级的。有人会说那我把链表换成数组用二分查找不就行了但问题来了数组的插入和删除是 O(n) 的为了维持有序性你得把后面的元素全挪一遍插入一个元素有时要搬动成千上万个位置。链表的插入倒是痛快改两个指针就完事可它又没办法二分。这看起来像是一个死局要么牺牲查询要么牺牲写操作。1.2 “抄近路”的直觉索引让我们不必每一步都走现在换个思路。想象你在一本一千页的词典里找一个词你不会从第一页逐页翻到最后一页而是会先翻到大概的章节位置再在这个范围内细找。也就是说你利用了“目录”和“章节页”的粗粒度定位能力。跳跃表的灵感就在这里在原始链表之上再建一层稀疏的链表它只指向一部分节点作为“快速通道”。查找的时候先在这条快速通道上走走到目标值所在的大致区间再降落到原始链表层在区间内做精确查找。两层还不够就把这个思路递归下去每上一层节点更稀疏通道更快捷。最终的效果是查找过程只走“稀疏层 局部密集层”而不是把整条长链走完。这个思想在工程里太常见了地图应用就是这种思路——先看省界、再看市界、最后看街道。跳跃表的本质就是在链表上人为制造多级“路标”。2. 层级、跨度与升降级机制跳跃表的结构骨架2.1 节点结构除了数据还要背着一串指针传统的链表节点只包含一个值和 next 指针。跳跃表节点不同它有一个数组或者说一组指针叫 forward长度为该节点的层高。forward[i] 指向“从当前节点出发在第 i 层上的下一个节点”。在经典的插入算法中还会给每个节点维护一个 span 值记录 forward[i] 到目标节点之间跨越了多少个节点。加上 span 后跳跃表能算出任意节点的排名这也是某些有序集合场景里做 “按排名取元素” 操作的关键。用伪代码表示一个跳跃表节点struct SkipNode { int value; int level; // 当前节点的层高 SpanForward forward; // forward[i] 和 span[i]i 从 0 到 level-1 }除了节点整个跳跃表还要维护几个全局信息头节点 header、最大层数 maxLevel、当前实际最高层数 level、以及节点总数 length。头节点是哨兵它不存具体数据但它的 forward 数组要按 maxLevel 分配因为任何一层都从它开始。2.2 查找过程从高层往低层步步逼近查找是一个自上而下、逐层缩小区间的过程。假设要查找目标值 x从 header 的最高层出发遍历当前层的 forward 指针。如果下一个节点的值小于 x就继续在当前层前进如果下一个节点的值大于等于 x则下降到下一层。在下一层重复同样的判断继续向右或向下。直到降到第 0 层也就是原始链表层此刻要么找到了 x要么停在小于 x 的最大节点上说明 x 不存在。这个过程很像我之前说的查词典先翻大章节再缩小到具体页码范围。举个例子数据为 1, 2, 5, 8, 9, 12, 15, 18, 22要查找 15。可能在第 2 层从 header 跳到 8发现 18 大于 15于是降到第 1 层在第 1 层从 8 跳到 12再想跳到 18 时发现超了于是降到第 0 层第 0 层从 12 走到 15命中。整个过程中真正“逐节点”走过的路径仅限于最后一段小区间。高层的跳跃则一步跨过大量节点这就是它快的原因。2.3 插入与删除原地调整不必移动元素插入新节点时先做一次查找记录下每一层最后经过的“待修改节点”也就是每层最后一个值小于新节点的节点然后随机生成新节点的层高从底层到新层逐层挂接指针同时更新沿途节点的 forward 和 span。删除同理先找到待删除节点在各层的前驱然后逐层摘除指针。这个过程跟链表操作一致只是多了几层指针要维护。因为数据是有序的且每次插入都严格按值大小定位所以跳跃表天然支持范围查询搜到一个起点后沿第 0 层链表顺序往下走 n 步就能拿到区间内所有元素。3. 随机层数与概率平衡跳跃表“不红黑树”也能自平衡的原因3.1 为什么需要随机层数而不是固定层数一个很自然的疑问是既然高层能加快查找为什么不干脆所有节点都建到最高层答案是层级越高节点越少才能保证跨越的步长越来越大。如果所有节点都在所有层出现那每一层的遍历长度都和原始链表一样长索引就形同虚设。所以要控制“高层节点的数量密度”。一种朴素做法是人为规定第 0 层有全部节点第 1 层只有一半第 2 层只有四分之一……这种“理想分布”看起来很美但问题在于一旦做插入和删除这个比例就很难精确维持甚至需要全局重建成本极高。跳跃表的设计者选择了另一条路不精确控制而是让每个节点在插入时掷一次“骰子”决定它出现在多少层。只要这个随机过程遵循几何分布整体结构就会以极高概率保持“近似理想化”的稀疏度。3.2 掷硬币与 p 值从几何分布到期望层数在实现时常见的做法是每插入一个节点从第 1 层开始以概率 p 升到下一层。也就是说层高为 k 的概率是 p^(k-1) * (1-p)。当 p 0.5 时这就是一枚公平硬币——抛到正面就长一层抛到反面就停。用这个规则生成的层高期望值是 1/(1-p)。p 0.5 时期望层高是 2p 0.25 时期望层高约是 1.33。但这只是期望总会有一些幸运儿层高特别高比如 20 层、30 层。没关系这些极端值出现的概率极低且在期望意义下对整体性能的影响可忽略。经典论文里推荐的 p 值在 0.25 到 0.5 之间。p 越大层越高查找越快但内存开销也越大p 越小内存更省但查找慢一些。实际生产里p 0.25 常用于对内存敏感的场景p 0.5 则更偏向追求读性能。3.3 随机化的本质用概率摊平最坏情况的攻击这里值得多说一句。很多人第一次接触跳跃表时会觉得“随机”意味着不可控、性能不稳定。但恰恰相反随机化在这里是让它获得平均 O(log n) 复杂度的核心手段。关键在于节点的层高分布是独立随机的这会让数据插入顺序本身造成的影响被抵消。比如某些红黑树实现如果插入序列恰好是逆序树可能变得左右严重失衡需要大量旋转修正。而跳跃表不管插入序列多刁钻每个节点的新层高都是重新掷骰子得到的不会因为“数据长得有规律”就让结构退化。这也是“随机平衡”和“严格平衡”之间的本质差异。红黑树、AVL树通过旋转操作维持严格的平衡条件跳跃表则通过概率分布维持统计意义上的平衡。前者在单次操作时更可控后者的期望表现几乎一样好但实现和调试成本要小一个量级。4. 为什么说“用链表实现二分查找”这句评价最精确4.1 跳跃表与红黑树、B树的性能对比把几种主流有序结构放在一起看会更容易理解跳跃表的位置。数据结构查找插入删除范围查询实现复杂度典型场景跳跃表O(log n)O(log n)O(log n)支持天然有序低内存有序集合、排行榜红黑树O(log n)O(log n)O(log n)支持需中序遍历中通用有序映射、操作系统调度B树O(log n)O(log n)O(log n)支持叶子节点成链高磁盘数据库索引、文件系统跳跃表在时间复杂度上和红黑树持平但它有两个隐形的工程优势。第一实现和调试成本低。红黑树有左旋、右旋、变色、叔叔节点判断这些繁琐分支写错一个旋转方向就够你排查半天。跳跃表的每个操作都是“从高层降到低层、边查边改指针”逻辑路径单一不易出隐蔽错误。第二范围查询更直接。红黑树要拿中序遍历才能按序输出跳跃表只需要在底层链表上顺着指针走就行没有任何递归开销。跟 B树比跳跃表没有磁盘块和页的概念它是纯内存结构不追求把数据打包到固定尺寸的页里也不考虑缓存行对齐。如果你在做纯内存服务B树的页式设计反而有点大材小用。4.2 内存占用与缓存友好性的诚实评估很多人夸跳跃表时爱说它“内存效率高”但这里得分清楚。跳跃表节点确实要额外存储 forward 数组但这个数组是“每层一个指针”比红黑树每个节点固定存两个子指针加一个颜色标记要多。p 0.5 时平均每节点约 2 个指针p 0.25 时约 1.33 个指针。这比红黑树的固定两个指针略省或持平但跳跃表节点往往还存 span 等其他字段实际开销并不算低。不过跳跃表有一个红黑树没有的优势它的所有层都是顺序指针天然按数据大小排列没有“节点分裂”“节点合并”这种局部结构剧变。所以对缓存行来说第 0 层链表上的相邻节点大概率在内存中也是邻近分配的。如果你用内存池或连续预分配的方式管理节点遍历时缓存命中率会非常好看。我之前做一个模拟项目时用 p 0.25 的配置存了 1000 万个整数节点实测内存约占了每个节点 40 字节。如果换用红黑树同样节点数反而更占一些因为颜色标记和父子指针在 64 位系统上往往会产生结构体对齐的填充空洞。4.3 边界情况空表、单节点、重复值跳跃表实现里最容易被忽略的坑都在边界上。空表和高层指针的问题header 初始化时所有层的 forward 都指向 NULL。查找时从当前 level 往下走第一层就可能会碰到 NULL必须把“下一个节点为空”当作“大于任何目标值”处理然后照常降层。单节点和层高为 1 的节点节点层高为 1 时它的 forward 数组只分配了第 0 层。修改指针时必须只操作到该节点层高为止不能越界访问 forward[1]。这小问题很容易在删除节点时引发段错误。重复值跳跃表经典实现默认处理唯一键。如果你要存重复值通常的做法是让节点携带一个链表或者引用计数而不是让多个节点共享同一个排序键。另有一种做法是把重复值再按插入时间排序但这会让查找逻辑变复杂工程上不太推荐。5. 从理论到源码真实工程里的跳跃表实现细节5.1 核心数据结构定义下面给出一段可直接参考的 C 风格实现骨架。注意这里用的是双向的“假设”因为有的实现为了反向范围遍历会给节点加一个 backward 指针。单向前进版本也可以但反向遍历需要额外的栈记录路径。#define MAX_LEVEL 32 typedef struct SkipNode { int value; int level; struct SkipNode *forward[MAX_LEVEL]; int span[MAX_LEVEL]; } SkipNode; typedef struct { SkipNode *header; int level; int length; } SkipList;MAX_LEVEL 取 32 的依据是如果数据量最多一亿log 以 2 为底约 27再留出几个余量32 足够。理论上节点的随机层高可能超过 32但概率极低直接把生成层高截断到 MAX_LEVEL 即可。5.2 查找操作的完整逻辑SkipNode* skip_search(SkipList *list, int target) { SkipNode *cur list-header; for (int i list-level - 1; i 0; i--) { while (cur-forward[i] ! NULL cur-forward[i]-value target) { cur cur-forward[i]; } } cur cur-forward[0]; if (cur ! NULL cur-value target) { return cur; } return NULL; }这段代码的巧妙之处在于一次循环同时完成“向右”和“向下”。cur 先尝试在当前层尽量向右走走不动了就降一层。因为每层都是有序的所以这个下降过程天然维护了一个“当前已确定的最大小于目标值”的边界。循环结束后cur 是第 0 层上恰好队尾小于 target 的节点它的 forward[0] 就是要找的位置。5.3 插入操作的路径记录与随机层生成SkipNode* skip_insert(SkipList *list, int value) { SkipNode *update[MAX_LEVEL]; SkipNode *cur list-header; int rank[MAX_LEVEL]; for (int i list-level - 1; i 0; i--) { if (i list-level - 1) { rank[i] 0; } else { rank[i] rank[i 1]; } while (cur-forward[i] ! NULL cur-forward[i]-value value) { rank[i] cur-span[i]; cur cur-forward[i]; } update[i] cur; } int new_level random_level(); if (new_level list-level) { for (int i list-level; i new_level; i) { update[i] list-header; update[i]-span[i] list-length; } list-level new_level; } SkipNode *new_node create_node(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; new_node-span[i] update[i]-span[i] - (rank[0] - rank[i]); update[i]-span[i] (rank[0] - rank[i]) 1; } list-length; return new_node; }这里最关键是 update 数组的作用。它记录了每一层上“最后一个小于新节点值的节点”。没有它插入时就得重新走一遍来定位每一层的前驱。rank 数组则用来精确计算跨度—— span[i] 的更新根本不用数节点而是通过路径上的排名差算出来。排名差公式新节点在第 i 层的跨度 旧前驱跨度 - (rank[0] - rank[i])。这个逻辑初看有点绕但只要记住 rank[0] 是第 0 层的累计跨度rank[i] 是第 i 层起点的累计跨度两者之差就是从第 i 层插入点到第 0 层插入点之间隔了多少个节点。这个差值刚好是旧跨度里要被“切走”的部分。5.4 随机层生成器的工程实现int random_level(void) { int level 1; while ((rand() 0xFFFF) (0xFFFF 2)) { level; } return (level MAX_LEVEL) ? level : MAX_LEVEL; }这里用 0xFFFF 2 相当于概率 p 0.25。用 rand() 0xFFFF 而不是直接用 rand() % 100是为了减少取模带来的低比特位偏差同时让概率判断更贴近几何分布。市面上不少优质实现会改用位运算或预计算的概率表核心目的都是控制随机数开销。如果你在一个多线程环境下用这里 rand() 很可能成为瓶颈因为标准库的 rand() 有全局锁或状态污染。实践中可以改成线程局部随机数生成器比如用 xorshift 这类又快又无状态依赖的方案。6. 从教科书到生产系统跳过表真正发光的地方6.1 内存数据库与有序会话管理有一个场景我印象很深。某内存数据库需要支持有序字符串的增删查还要支持按字典序范围扫描数据量在千万级。一开始团队选型时有人提议用红黑树理由是稳定性好、业界验证多。但后面细看需求才发现除了单点操作业务还频繁要求“从某个 key 开始往后遍历 200 个 keys”。红黑树拿到这个需求就得做中序遍历或者额外维护一个线索链表维护成本立刻上去了。跳跃表在这个需求下几乎是量身定做的一次查找定位起点然后在底层链表上顺着 forward[0] 一个个走每次操作都是 O(log n m)其中 m 是遍历数量。这段代码的 debug 难度比红黑树版本低得多我记得从写完到跑通只花了不到一天。6.2 LSM 树存储引擎里的有序内存表另一个典型场景是某类 LSM 风格的存储引擎里内存中的有序结构常称为 MemTable就是一个跳跃表。为什么这里选跳跃表而不是 B 树或红黑树B 树被设计成面向磁盘的页式结构内存表用它纯属浪费因为不需要“页”这个概念。红黑树呢它的有序范围遍历不够直接而 Compaction 时经常需要把整个内存表顺序扫出来刷盘。跳跃表的底层链表天然有序顺序扫描性能极佳。更关键的是LSM 引擎的写入路径是纯内存追加式跳跃表的插入只在最高层到新节点层高之间做指针修改不会像 B 树那样频繁触发页分裂也不像红黑树那样需要旋转修正。我还记得当时测试插入吞吐时p 0.25 配置下跳跃表比红黑树快了约 15%~20%主要省在插入时不需要频繁的父节点回溯和旋转判断上。6.3 延迟敏感场景里的无锁化尝试有一个方向值得提一下跳跃表是少数可以比较自然实现无锁并发读写的链表结构。因为它的层级指针都是单向的插入时只需要 CAS 修改对应层的 forward 指针不会像双向链表那样需要同时维护两个方向的引用一致性。删除操作复杂些要逐层摘除并处理并发读者但在某些读多写少的场景里用原子指针和版本号就能做出非常高吞吐的并发跳跃表。不过我得诚实地劝一句无锁跳跃表是真正的硬核项目调试难度极高。普通业务里老老实实加锁或者用分片锁可能收益更好。只有当你压测明确发现锁竞争成了瓶颈才值得往这个方向投入。7. 实现跳跃表必须避开的坑我踩过的一些教训7.1 头节点层级不足导致的高层悬空我第一次写跳跃表时犯过一个典型错误header 的 forward 数组只分配了当前 level 那么多。结果插入新节点时一旦随机层高超过了当前 level代码想访问 header-forward[new_level - 1]直接用到了未分配的空间程序当场崩溃。修复方案是 header 节点的数组从一开始就按 MAX_LEVEL 分配。这多花几十个指针的内存但彻底避免动态扩容头部的麻烦。这个问题在调试时很隐蔽因为崩溃不一定发生在插入高节点的瞬间而是可能在很多次插入之后某次删除时触发了空指针。7.2 更新 update 数组时遗漏层级插入和删除都必须从当前最高层开始查找并记录 update。如果你只记录了 update[0]删除时只改底层链表那么上层还残留着指向已删除节点的指针后面的查找会走进一个悬空引用。排查这个问题的思路是打印每一层链表的完整内容观察是否存在“某个节点的 forward[i] 指向了一个 value 明显越界”的情况。这种打印诊断法在跳跃表的早期调试里比单步调试好用得多因为问题往往不在当前步而在前面几步的指针残留。7.3 层高生成器被随机数质量拖垮之前在一个项目里我用的是系统默认的 rand()结果在并发高负载下发现跳跃表退化成接近 O(n) 的链表。排查下来发现rand() 的低位比特在短周期里会严重重复导致层级分布集中一部分节点层高全是 1一部分全是 2结构极不均匀。后来我换成了基于 xorshift 的自定义生成器并且把概率判断从rand() % 100 25改成位掩码方式层级分布立刻恢复正常查询性能也回到了预期范围。这说明随机数的质量在这种概率结构中不是小事。7.4 误以为层级越高越好忽视实际负载还有一个坑是参数调优。有一回我为了追求查询速度把 p 调到了 0.75结果单节点平均层高飙升到 4内存占用涨了近一倍而查询只快了不到百分之五。原因很简单在数据量达到千万级别以前决定性能的往往是缓存命中率和分支预测而不是极少几次的额外指针跳转。层高太高缓存行里加载的冗余指针反而拖累了访问速度。调参的正确姿势应该是先用 p 0.25 起步压测后再对比 p 0.5 的改进效果。大多数内存数据库的实测说明p 0.25 是内存和查询性能之间的一个甜点。8. 跳跃表在面试中的高频考点与思考方式8.1 考点一为什么平均复杂度是 O(log n)最坏情况呢面试官问这个重点想听你对“随机化”的理解而不是把教材公式背出来。解释思路应该说层高服从几何分布期望每层节点数是前一层的一半所以跳表整体形状趋近于一棵多叉树。查找路径从顶层到底层每一步要么向右跨过一段节点要么向下降一层。跨过的节点总数由所在层的局部节点密度决定期望上每层只访问常数个节点。层高期望为 1/(1-p)从顶层到第 0 层要下降期望次所以总代价正比于 O(log n)。最坏情况是每个节点的层高都恰好是 1那就退化成链表。但每个节点层高为 1 的概率是 (1-p)^n随 n 指数级衰减在现实中几乎不可能发生。8.2 考点二跳表、红黑树、B 树的场景取舍这个考点没有标准答案但考察的是工程判断力。我的建议是抓住两个维度一是内存还是磁盘二是单点操作多还是范围操作多。内存 范围多优先跳表内存 单点多两者皆可看团队哪个实现熟磁盘 范围多B 树是标配因为页式结构和预读机制在磁盘上优势太明显。红黑树在这个三角里的位置很微妙它的实现知识密度高能体现基础功底但在纯粹的功能层面它并不一定是最优选择。很多公司面试愿意聊它是因为通过红黑树的细节能快速筛出对指针操作不熟的人而不是因为它是什么万能银弹。这也是为什么很多候选人在这道题上栽跟头——过分表现对红黑树的崇拜却忽略了场景本身的约束。8.3 考点三如何用跳表实现一个带排名的排行榜这是一道很有区分度的扩展题。解法是先确定分数排序规则比如分数高的排前面如果分数相同则按最近更新排。然后让跳跃表节点携带 score 和 唯一用户 ID利用 span 值算出当前节点前面的总数就能实现“查询用户排名”和“按排名取用户”。插入、更新分数、删除的时间复杂度都是 O(log n)比用 SQL 全表排序或者缓存数组的 O(n) 方案都要好一个量级。这个场景里跳跃表相对红黑树的优势又体现了一次红黑树也能排但你要拿到某节点的排名必须从根节点往下递归数左子树大小还得联合维护额外的 size 字段。跳跃表直接用 span 就能在查找过程中一路累加出来。9. 后续还能怎么扩展从跳跃表通往更高阶的工程思路如果这篇文章让你对跳跃表有了兴趣我建议顺着几个方向继续深挖。一是把跳跃表改成支持区间删除和区间更新的版本。这需要在保持 rank 和 span 之外额外维护一个“区间标记”或者懒惰删除的位图。工程上做日志系统、范围定时器时非常有用。二是研究“确定性跳跃表”或“B 树化跳跃表”。这类变体会让层高不再随机而是严格遵循某些分配规则从而让最坏情况也变得确定。代价是实现复杂度上升但能消除随机化带来的微妙不确定性。对时间敏感型系统来说这一步值得研究。三是啃一下无锁跳跃表的实现思路。前文说过这个方向很硬核但它真的能让你对内存模型、CAS 失败重试、ABA 问题有极深的理解。如果你在做一个高吞吐的缓存组件或事件路由这类知识是能直接换成系统吞吐量的。以我个人经验来说学跳跃表最好的方式不是反复看博客而是真的去实现一遍。从单线程版本开始打印每一层结构然后加范围查询、排名查询最后再加并发控制。等你能把一次插入操作在纸上画出每一层指针的变化你才是真的懂了它。