跳表在一条有序链表上叠若干层稀疏索引，用随机化层高代替旋转与变色，换来期望 O(log n) 的查找和远低于平衡树的实现复杂度。Redis 的有序集合 ZSet 正是靠它支撑排序、排名与范围查询。

它解决什么问题

有序链表插入只要 O(1)，但查找必须从头扫到尾，O(n)。如果业务既要求数据随时有序，又要求查找、范围遍历都快，平衡树是经典答案——但红黑树的旋转与变色规则复杂到很少有人能徒手写对。跳表提出了一个概率化的替代方案：不追求严格平衡，靠随机性让索引高度在期望意义上保持在 log 级别，实现简单得多，性能却同样稳定。

核心原理

跳表的最底层是一条包含全部元素的有序链表，上面每一层都是下一层的稀疏子集，越往上节点越少。查找从最高层开始：当前层的下一个节点小于目标就向右走，否则下降一层；到底层时，最后一个走过的位置的下一个节点就是答案候选。这个过程像在路网里先上高速、再转国道、最后进街巷，每一层都把搜索范围砍掉一大块。

层高不是精心规划的，而是随机抛出来的：新节点一定占据底层，之后以概率 p 决定是否再升一层，连续成功就持续升高。以 p = 1/2 为例，第 1 层期望有 n/2 个节点，第 2 层 n/4 个，第 i 层 n/2^i 个——天然形成一座「金字塔」。

深入机制

期望 O(log n) 从哪来

两条线合起来。第一，层数期望：第 i 层非空的概率随 p^i 衰减，总层数的期望约为 log_(1/p) n，即 log 级别。第二，每层步数期望：在任意一层向右走时，走到一个「也出现在上一层」的节点就会下降，而每个节点向上升级的概率是 p，所以每层期望右走不超过 1/p 步。两层相乘，总步数期望约为 (1/p)·log_(1/p) n，即 O(log n)。空间也类似：每个节点的期望指针数是 1/(1-p)，p 取 1/2 时平均每节点 2 个指针，总空间期望 O(n)。

要强调的是「期望」二字：存在所有节点都只有一层的倒霉情况，查找退化为 O(n)，但随机数正常时其概率小到可以忽略。跳表用概率交换了实现的简单性。

插入与删除

// 查找并记录每层前驱：跳表所有操作的公共骨架
Node[] update = new Node[MAX_LEVEL];
Node x = head;
for (int level = topLevel; level >= 0; level--) {
    while (x.forward[level] != null && x.forward[level].score < target)
        x = x.forward[level];        // 能往右就往右
    update[level] = x;               // 不能往右，记下前驱，准备下降
}
// x.forward[0] 即为目标候选：命中则更新，未命中则插在 x 之后

插入：先跑一遍上面的骨架，把每层最后一个比目标小的节点记入 update；再随机出新节点的层高；最后把它逐层接进 update[level] 之后。删除是镜像操作：同样借助 update，在目标出现的每一层把前驱指针绕过它。两个操作的成本都是「一次查找 + 逐层常数次指针修改」，期望 O(log n)。任何一层都不能漏改，否则索引与底层链表会不一致。

span：从排序到排名

Redis 的跳表节点在每一层还维护一个 span 字段，记录这根指针跨越了多少个底层节点。定位某个成员时把沿途经过的 span 累加，就直接得到它的排名——ZRank、ZRevRank 由此而来，范围查询 ZRange 也是「定位起点 + 沿底层顺序输出 k 个」，复杂度 O(log n + k)。

工程实践

Redis ZSet 是跳表最著名的落地。它内部是「字典 + 跳表」双结构：字典按 member 直接查到 score（O(1)），跳表按 score 维护有序；member 不同的元素允许 score 相同，相同 score 时按 member 字典序比较。数据量小时 ZSet 用紧凑的 listpack 编码省内存，超过阈值才转成字典加跳表——面试里说「ZSet 底层是跳表」，指的是大数据量时的核心结构。跳表的最大层数 32、升级概率 0.25，是 Redis 在空间与高度之间调好的参数。

LevelDB 的 MemTable 同样选择了跳表：写入只需顺序往内存结构里插，跳表的简单性让并发控制（读无锁）容易得多。

对比与权衡

维度 跳表 红黑树 B+ 树
平衡方式 随机层高，期望平衡 旋转 + 变色，严格平衡 多叉 + 页分裂合并
查找复杂度 期望 O(log n) 最坏 O(log n) O(log n)，矮胖
范围查询 定位后沿底层顺序扫，极自然 中序遍历，指针跳跃多 叶页链表，磁盘友好
实现难度 低，百行内可写完 高，修复规则繁琐 高
适用介质 内存 内存 磁盘（页对齐 IO）
代表系统 Redis ZSet、LevelDB MemTable Java TreeMap、epoll 定时器 MySQL InnoDB 索引

Redis 为什么选跳表而不是红黑树？几个现实理由：其一，范围查询是 ZSet 的主战场，跳表定位起点后沿底层链表输出即可，红黑树要靠中序遍历逐层回溯；其二，跳表的插入删除只是局部指针修改，没有旋转和变色，代码量和心智负担小得多，也更容易做对；其三，Redis 主线程是单线程，不需要严格的最坏情况保证来防其他线程饿死，期望 O(log n) 完全够用；其四，跳表的指针开销可通过升级概率 p 调节，并不吃亏。

面试视角

跳表的 O(log n) 是怎么保证的？ 不是保证，是期望。第 i 层期望节点数 n·p^i，层高期望 log 级；每层期望右走不超过 1/p 步。相乘得期望 O(log n)。最坏 O(n) 存在但概率极低。

Redis 为什么不用红黑树？ 范围查询更顺（底层链表直接扫）、实现与维护简单（无旋转变色）、参数可调（p 控制空间与高度的平衡）、单线程模型下不需要严格最坏保证。

插入一个节点的完整流程？ 从最高层向下查找，沿途把每层前驱记入 update 数组；随机生成层高；在 0 到层高-1 的每一层把新节点接进前驱之后，并维护 span。只改底层不改索引是新手最常见的 bug。

跳表怎么支持排名？ 每层指针带 span（跨度），记录跨过的底层节点数；查找时累加沿途 span 即得排名，代价是每个节点多存几个整数。

跳表和 B+ 树都擅长范围查询，区别在哪？ 跳表是为内存设计的：指针跳转在内存里是常数成本。B+ 树为磁盘设计：一个节点占满一个页、扇出极大，把树高压到 3~4 层，减少磁盘 IO 次数。介质不同，选型不同。

小结

  • 跳表 = 有序链表 + 随机化多级索引；期望 O(log n) 来自「层高 log 级 × 每层常数步」的概率论证。
  • 插入删除共用 update 前驱数组，逐层维护指针；span 字段让排名查询顺手完成。
  • 对比红黑树赢在简单与范围遍历，对比 B+ 树输在磁盘页不友好——它是纯内存结构。
  • Redis ZSet 用「字典 + 跳表」组合：字典管按成员查分，跳表管排序、排名与范围。