跳表是一种以有序链表为底层、通过多级索引加速查找的概率型数据结构。它用随机层数替代平衡树中的旋转与着色,在期望意义下取得与平衡树相同的对数级查找代价,同时把插入与删除的影响限制在常数个指针上。本文讨论跳表的结构原理与实现要点,其在 Redis 有序集合中的落地方式见 Redis 核心与数据结构 第 2.2 节,工程用法见 Redis 缓存实践与常见问题。复杂度记号与期望、摊还、最坏情况的分析口径见 复杂度与算法分析;与有序链表同为线性结构的栈与队列见 栈与队列。
一、起源:有序链表查找的瓶颈
1.1 链式存储无法二分
有序数组支持二分查找,代价为 O(log n),原因是数组元素连续存放,可以通过下标在常数时间内访问任意位置。链式存储不具备这个能力:节点在堆上离散分配,每个节点只保存后继节点的引用,要访问第 k 个元素必须从头部逐个跳转 k 次。
因此有序链表上的查找只能顺序扫描:
- 沿
next引用逐节点比较,命中即返回,未命中则走到末尾。 - 平均比较次数为 n/2,最坏为 n 次。查找代价与元素数量成正比。
三种有序结构的查找与更新代价对照如下。
| 结构 | 按值查找 | 插入 | 删除 | 有序遍历 |
|---|---|---|---|---|
| 有序数组 | 二分 O(log n) | 搬移元素 O(n) | 搬移元素 O(n) | O(n),顺序访问 |
| 有序链表 | 顺序扫描 O(n) | 已定位后 O(1) | 已定位后 O(1) | O(n),顺序访问 |
| 平衡二叉树 | O(log n) | O(log n) | O(log n) | O(n),中序 |
有序数组与有序链表各自优势正好互补:前者查找快而更新慢,后者更新快而查找慢。"更新快"这一项还有隐含前提——位置已经确定;若插入前需要先查找,插入的整体代价仍然是 O(n)。有序链表的问题因此可以概括为:它已经具备了 O(1) 的本地更新能力,缺的只是一条能快速定位的通道。
1.2 加索引的朴素想法
给链表"加索引"是解决定位问题的直接思路。以每两个元素抽取一个作为上一层节点为例,抽出的节点保存到下层节点的引用,形成一条新的链表。查找时先在索引层前进,越过目标后再下降到底层继续。
层 1 head ──► 2 ────► 4 ────► 6 ────► 8 ────► NULL 每 2 个元素抽取 1 个
层 0 head ──► 1 ──► 2 ──► 3 ──► 4 ──► 5 ──► 6 ──► 7 ──► 8 ──► NULL
(第 1 层的每个节点向下指向第 0 层的同名节点)
索引层使查找的比较范围被压缩。朴素做法的量化结果是:
- 只有底层时,比较次数为 n。
- 加一级索引后,先在约 n/2 个索引节点中定位,再在对应的两个底层节点之间比较,比较次数约为 n/2 + 1。
- 索引层自身可以继续抽取,得到二级、三级索引。第 k 级索引的节点数约为 n/2^k,比较次数约为 n/2^k + k。
把索引层数增加到 k = log₂n 时,最高层只剩少量节点,比较次数降到 log₂n 量级。
| 索引级数 k | 每级索引节点数 | 索引节点累计 | n = 10⁶ 时的比较次数 |
|---|---|---|---|
| 0 | — | 0 | 10⁶ |
| 1 | 5×10⁵ | 5×10⁵ | 5×10⁵ |
| 2 | 2.5×10⁵ | 7.5×10⁵ | 2.5×10⁵ |
| 10 | 约 10³ | 约 10⁶ | 约 990 |
| 20 | 1 | 约 10⁶ | 约 21 |
代价是空间:索引节点累计约 n/2 + n/4 + n/8 + … < n,即索引本身的节点数与元素数同阶。这是"空间换时间"的典型形态,与数据库用索引页换取更少的磁盘读取、哈希表用桶数组换取常数级定位是同一类取舍(对照见 mysql: 索引与执行计划 第 1.3 节)。
朴素索引的困难在更新上。上述索引之所以有效,依赖"每两个元素抽取一个"这一严格比例。插入或删除一个元素后,比例被破坏,要么接受索引逐渐稀疏、效果退化,要么按比例重建索引,代价为 O(n)。重建的触发频率与更新量成正比,使这一结构只适用于静态数据。
1.3 用概率替代严格平衡
跳表放弃严格比例,改用随机决定每个节点的高度:新节点插入时,以概率 p 决定是否再向上"晋升"一层,直到不再晋升或达到层数上限。
这一改动带来三个结果:
- 期望上的比例关系仍然成立。每个节点进入第 i 层的概率为 p^i,因此第 i 层的节点数期望为 n·p^i,仍然按比例递减,只是具体某个元素是否出现在某层不再确定。
- 插入不再需要维护比例。插入只改动每层相邻的两个指针,不触发任何重建;删除同理。更新代价回到链表的局部修改量级。
- 保证从"确定"变为"期望"。跳表的查找代价是 O(log n) 的期望值,最坏情况仍是 O(n)(所有节点都只有一个高度层,退化为有序链表)。这一退化的概率随元素数指数下降,因此在实际运行中不会出现。
这是一种结构上的交换:用"任何输入下都成立的最坏上界"换取"输入无关的期望性能与更简单的更新逻辑"。平衡树通过旋转与着色在确定性上取得最坏 O(log n);跳表通过随机数在期望上取得同阶结论,代价是最坏情况不再有保证,收益是更新逻辑被极大地简化,并且不再存在"能构造出退化输入的键序列"这一问题——层数的分布由随机数决定,与键的取值和插入顺序无关。
关于最坏情况与期望情况的区分、分布假设对结论的影响,见 复杂度与算法分析 第 2.3 节。
二、原理
2.1 从有序链表到多级索引
2.1.1 结构形态
跳表由若干条有序链表纵向叠放组成,每层是一条完整的有序链表,上层节点是下层节点的子集,且每个节点保存指向其正下方节点的引用(或把"各层后继"放在同一个节点的层数组中,两种表示等价)。
层 3 head ───────────────────────────────────────────► 30 ──────────► NULL
层 2 head ───────────────────────► 10 ───────────────► 30 ──────────► NULL
层 1 head ───────────────────────► 10 ──────► 20 ────► 30 ──► 40 ───► NULL
层 0 head ──► 5 ──────────────────► 10 ──────► 20 ────► 30 ──► 40 ───► NULL
几个约定:
- 层号从 0 开始,第 0 层包含全部元素,是唯一保证完整的链表。
- 每个节点参与的层数称为它的高度。第 0 层节点的高度至少为 1,出现在第 i 层(i 从 0 计)意味着高度至少为 i + 1。
- 多数实现只提供"向右(同层后继)"与"向下(下一层的同名节点)"两个方向的引用,不提供向上的引用;逆序访问由第 0 层的单独前驱引用承担(见 3.1 节)。查找与范围查询只用到向右与向下两个方向。
2.1.2 查找路径
查找从当前最高层的头节点开始,反复执行两个动作:
- 向右:若当前节点的后继存在且其键小于目标键,则移动到该后继;
- 向下:若后继为空或后继的键不小于目标键,则下降到下一层。
到达第 0 层后,若后继的键等于目标键则命中,否则目标不存在。以在 6 个元素的表中查找 25 为例:
层 3 head ─────────────────────────────────► 30 ─► NULL 后继 30 ≥ 25,不移动,下降
层 2 head ─────────────► 10 ───────────────► 30 ─► NULL 后继 10 < 25 右移到 10;后继 30 ≥ 25,下降
层 1 head ─────────────► 10 ─────► 20 ─────► 30 ─► NULL 后继 20 < 25 右移到 20;后继 30 ≥ 25,下降
层 0 head ─► 5 ────────► 10 ─────► 20 ─────► 30 ─► NULL 停在 20,后继 30 ≥ 25,未命中,前驱为 20
上例的元素数很少,层数与元素的比值看起来不成比例,这是为了让移动模式可见;元素数达到百万级时,层次结构才会体现出优势(见 2.2.3 的量化)。
查找的关键性质是:在任意一层向右移动时,都不会跳过目标所在的位置。因为移动条件是"后继的键严格小于目标键",所以每次移动后目标仍然位于当前节点的右侧或就是当前节点的后继。这保证了下降到底层后不会漏掉目标。
2.1.3 空间换时间的量化
设晋升概率为 p,则节点出现在第 i 层的概率为 p^i,第 i 层的节点数期望为 n·p^i。
- 索引节点的总数期望为 n·p + n·p² + n·p³ + … = n·p/(1 − p)。
- p = 1/2 时约等于 n,即额外付出与元素数同阶的索引节点;
- p = 1/4 时约等于 n/3。
每个索引节点至少要多保存一个"下层引用"(或在其层数组中多一个槽位),因此额外的指针数与该值同阶。加上第 0 层每个元素本身的后继引用,整个结构的总指针数约为 n·(1 + p/(1 − p)):p = 1/2 时约 2n,p = 1/4 时约 1.33n。
这笔空间换来的是查找比较次数从 O(n) 降到 O(log n)。作为对照,哈希表用桶数组把查找降到期望 O(1),代价是失去有序性与范围查询能力;B+ 树用页内扇出把树高压在 3 至 4 层,代价是页分裂与合并带来的维护开销(见 mysql: 索引与执行计划 第 2.1 节)。
2.2 随机化策略
2.2.1 层数生成
层数在插入时生成,与键的取值无关。标准的生成方式是反复抛硬币:
randomLevel():
level = 1
while random() < p and level < MAX_LEVEL:
level += 1
return level
生成的层数服从参数为 p 的几何分布:高度恰为 k 的概率为 p^(k−1)·(1 − p)。
| p 取值 | 节点高度期望 | 高度为 1 的概率 | 高度不小于 3 的概率 | 索引指针期望数 |
|---|---|---|---|---|
| 1/2 | 2 | 0.5 | 0.25 | n |
| 1/4 | 4/3 ≈ 1.33 | 0.75 | 0.0625 | n/3 |
需要区分两个"层数"概念:
- 单个节点的高度期望为 1/(1 − p),p = 1/2 时是 2,p = 1/4 时约 1.33。这是节点内存开销的直接来源。
- 整表的最大层数期望由元素数决定。n 个节点中最大的高度约为 log_{1/p} n(求解 n·p^k ≈ 1 得到),p = 1/2 时约为 log₂n,p = 1/4 时约为 log₄n = 0.5·log₂n。
2.2.2 最大层数上限
随机生成的层数必须有上限,否则会出现两种情况:单个节点占用远超预期的内存;层数过高使最高层的节点数为 0,查找的起点层没有意义。
上限 MAX_LEVEL 的取值依据是"在期望的层数之上再留出若干层",而不是当前的实际层数:
| p 取值 | MAX_LEVEL = 32 时支持的元素规模 | 依据 |
|---|---|---|
| 1/2 | 约 2³²(十亿级) | (1/p)^MAX_LEVEL |
| 1/4 | 约 4³² = 2⁶⁴ | 同上 |
超过上限的截断是无害的:截断只使极少数节点的层数低于其随机结果,而这一点对期望复杂度的影响可以忽略。
2.2.3 为什么随机能给出期望 O(log n)
推导分两步,自顶向下看。
第一步,每层的水平步数。 第 i 层有约 n·p^i 个节点,它们在第 0 层的位置上大致均匀分布,因此第 i 层相邻两个节点之间的底层间隔期望为 1/p 个元素。在查找过程中,若在第 i 层向右移动,则移动的步数不会超过该层相邻节点之间的间隔期望,即每层的水平步数期望不超过 1/p。
第二步,层数与总步数。 表的最大层数约为 log_{1/p} n。每下降一层,最多付出 1/p 次水平比较,因此总比较次数的期望为:
(1/p) · log_{1/p} n
代入具体取值:
p = 1/2 2 · log₂ n = 2 · ln n / ln 2 ≈ 2.885 · ln n
p = 1/4 4 · log₄ n = 4 · ln n / ln 4 ≈ 2.885 · ln n
p = 1/e e · ln n ≈ 2.718 · ln n
三个取值给出的量级相同,都为 O(log n)。上式对 p 求导可得极小值点 p = 1/e ≈ 0.37,但该点与 p = 1/2、p = 1/4 的差距只有约 6%;而索引指针的期望数 p/(1 − p) 在 p = 1/2 与 p = 1/4 之间相差三倍。因此 p 的取值主要由空间预算决定,p = 1/4 是"查找步数几乎不变、索引空间降到三分之一"的选择,这也是 Redis 有序集合采用 1/4 的原因(见 3.4 节)。
2.2.4 随机性带来的稳定性
随机层数最重要的性质是结论与输入无关,这一点由三处概率界保证。
- 不会出现输入导致的退化。平衡树的最坏情况由插入序列决定,攻击者可以构造出使树退化的序列,或利用哈希碰撞使哈希表退化为链表(见 Java 集合框架实现原理 第 3.4 节);跳表的层数与键值无关,构造不出这类输入。
- 超过期望层数越多的概率越小,且与元素数无关。某节点高度不小于 k 的概率为 p^(k−1),因此 n 个节点中至少有一个高度不小于 k 的概率不超过 n·p^(k−1)。取 k = log_{1/p} n + c,概率上界为 p^c,与 n 无关——元素数增长一百倍,超过期望层数 c 层的可能性的上界不变。
- 退化为有序链表的概率随元素数指数下降。全部节点高度都为 1 的概率为 (1 − p)^n。p = 1/2、n = 1000 时约为 2^(−1000),实际不可能发生。
结论的表述方式因此需要保持准确:跳表的查找、插入、删除都是期望 O(log n)、最坏 O(n),而平衡树是最坏 O(log n)。在延迟上界有硬要求(例如超时时间必须严格可推导)的场景中,这一差别需要被显式评估;在绝大多数应用中,(1 − p)^n 量级的退化概率已经远低于硬件故障概率。
2.3 查找过程
查找是插入与删除的基础,因此先给出统一的形式:在向右移动的过程中记录每一层停下的节点,这些节点就是插入与删除所需的"待更新前驱"。
search(key):
x = header
for i = level - 1 downto 0:
while x.next[i] != NULL and x.next[i].key < key:
x = x.next[i]
update[i] = x # 第 i 层最后一个键小于 key 的节点,即该层的前驱
return x.next[0] # 第 0 层的后继:命中则为目标本身,否则为目标之后的第一个节点
| 指标 | 期望 | 最坏 |
|---|---|---|
| 比较次数 | (1/p)·log_{1/p} n | n |
| 层数 | 约 log_{1/p} n | MAX_LEVEL |
| 额外空间 | O(1)(仅 update 数组,长度为 MAX_LEVEL) | O(MAX_LEVEL) |
几点需要明确:
- 比较次序是"同一层内多次比较,然后下降",而二叉树的查找是"每次比较下降一层"。同样是 O(log n) 次比较,跳表的水平移动在内存上是沿链表的跳跃,二叉树的下降是沿指针的随机跳转,两者的缓存行为不同,实测中的常数因子也不同(见 3.3 节)。
- 比较次数取决于 p 与层数,而不是元素数本身;元素数只通过层数进入结论,因此规模翻倍只多出常数级别的比较。
- 查找结束时停留的位置本身携带信息:
x是目标在底层的前驱,x.next[0]是目标或其后继。这一性质使前驱、后继、向下取整、向上取整查询可以直接复用查找过程,而不需要额外的遍历。
2.4 插入与删除
2.4.1 插入
插入分三步,其中第一步与查找完全相同。
- 定位并记录前驱。沿各层向右移动,把每一层停下的节点写入
update[]数组。数组长度取MAX_LEVEL,未使用的槽位填头节点。 - 生成层数。调用随机函数得到新节点的高度
level。若level大于当前表的最大层数,则把新增层的update项填为头节点,并更新表的层数字段。 - 逐层挂接。从第 0 层到
level − 1层,把新节点的后继指向update[i].next[i],再把update[i].next[i]指向新节点。
insert(key, value):
update[] = locate(key) # 同查找,记录每层前驱
if update[0].next[0] != NULL and update[0].next[0].key == key:
update[0].next[0].value = value # 键已存在:更新载荷,结构不变
return
level = randomLevel()
for i = currentLevel to level - 1: # 新出现的层:前驱是头节点
update[i] = header
header.span[i] = length
node = new Node(key, value, level)
for i = 0 to level - 1:
node.next[i] = update[i].next[i]
update[i].next[i] = node
length += 1
为什么只需要记录前驱。 插入改变的是每层中相邻两个节点的连接关系,因此所需的全部上下文就是"新节点在各层的前驱"。update[] 数组把这个上下文从查找过程中带出来,避免插入时在每层重新查找。数组长度是固定的 MAX_LEVEL,与元素数无关,因此空间开销是 O(1)(严格说是 O(MAX_LEVEL))。
键不可变。 插入的前提是键参与比较且不发生变化。若允许修改已插入元素的键(或有序集合中已插入成员的分值),会破坏链表的有序性,此后所有查找都不再可靠。更新键的正确做法是"先按旧键删除、再按键的新值重新插入",也就是把一次更新拆成一次删除加一次插入。Redis 在有序集合成员分值变化时正是这样处理。
2.4.2 删除
删除同样先定位并记录前驱,然后逐层摘除。
delete(key):
update[] = locate(key)
target = update[0].next[0]
if target == NULL or target.key != key:
return false # 键不存在
for i = 0 to level - 1:
if update[i].next[i] == target:
update[i].next[i] = target.next[i]
# 若 update[i].next[i] != target,说明 target 没有出现在第 i 层,无需处理
while level > 1 and header.next[level - 1] == NULL:
level -= 1 # 最高层已空,收缩层数
length -= 1
return true
三处容易出错的细节:
- 需要判断
update[i].next[i]是否就是目标节点。目标节点的高度可能小于表的当前层数,此时在高层的update[i].next[i]并不是目标,该层的指针不需要改写。若不加判断直接改写,会破坏高层的链表。若实现中维护 span,则该层仍需要把update[i]的跨距减 1(底层少了一个元素),只是不修改指针(见 3.1.4 节)。 - 层数收缩只能从最高层开始。收缩条件是"最高层的头节点之后没有任何节点",且必须逐个检查,不能因为某一层为空就把所有更高层一次性清除。
- 删除后节点对象不应再被任何引用指向。指向目标节点的引用包括各层前驱的
next[i],以及(若实现了第 0 层前驱引用)其第 0 层后继的前驱引用;逐层摘除后这些引用都已改写,节点可以被回收。若实现中额外持有尾部指针或迭代器,需要同步维护。
2.4.3 并发场景下的实现思路
跳表在并发场景中有天然优势:一次插入或删除只修改每层两侧的指针,不改变其他节点的结构,也不需要像平衡树那样通过旋转扩散到整棵子树。三种实现层次如下。
| 方案 | 做法 | 代价 |
|---|---|---|
| 全局锁 | 所有操作在同一个锁内串行执行 | 实现最简单,读写完全串行,扩展性最差 |
| 细粒度锁 | 每节点或每层加锁,按固定顺序获取 | 需要严格的加锁顺序以避免死锁;读操作通常也要加锁 |
| 无锁(CAS) | 用原子比较交换更新指针,删除分两步 | 实现复杂,但读操作完全无锁,写操作之间只在相邻指针上有冲突 |
无锁实现的两个要点:
- 删除分为逻辑删除与物理删除。先在被删除节点的后继指针上打标记(标记该节点已失效),使并发查找在遇到它时能够跳过或协助完成摘除;再从各层改写指针把它摘出。若把摘除与标记合成一步,会出现在某一层摘除后、其他层仍指向该节点的不一致状态。
- 允许索引层与第 0 层短暂不一致。成员是否存在于表中以第 0 层为准;索引层缺失的索引项不会影响正确性,只会使当次查找多走几步水平比较,可以由后续操作顺带补充,因此失败的 CAS 不需要回滚已完成的改动。
平衡树的无锁化困难正来自旋转:一次旋转要同时改变多个节点的父子关系,难以用有限条 CAS 原子地完成。Java 的 ConcurrentSkipListMap 是标准库中少数提供无锁有序映射的实现,其并发容器对照见 Java 集合框架实现原理 中"与并发的配合"一节的集合线程安全性表,无锁与内存可见性的基础机制见 Java 并发编程。
2.5 高级能力
2.5.1 范围查询
范围查询由两次动作组成:先定位区间的起点,再沿第 0 层向前推进。
range(lo, hi):
x = locate_first_ge(lo) # 定位第一个键不小于 lo 的节点,O(log n)
while x != NULL and x.key < hi: # 沿第 0 层推进
emit(x)
x = x.next[0]
代价为 O(log n + M),M 为结果数量。第 0 层是一条完整的有序链表,这是范围查询能够顺序推进的前提;相反,若在第 0 层每取一个元素都重新查找下一个,代价会退化为 O(M·log n)。
在实际实现中,定位起点时若只支持从头部开始,则无法表达"跳过前 k 个结果"的偏移语义;此时需要结合排名查询(见 2.5.2)或改用按值定位的游标方式。Redis 的有序集合同时提供 ZRANGE(按下标区间)与 ZRANGEBYSCORE(按分值区间)两种入口,深分页推荐改用后者,理由见 3.4 节。
2.5.2 按排名查询与 span 字段
范围查询之外,有序结构还常被要求回答两类问题:给定元素求其名次,给定名次求其元素。跳表通过在每个节点的每一层上附加一个 span(跨距)字段来支持这两类查询。
span 的语义定义为:从当前节点沿该层前进到其后继所跨过的第 0 层元素个数,不含当前节点、含后继节点。等价地,若把第 0 层的元素从 1 开始编号,则
span[i] = rank(next[i]) − rank(self) 仅在后继存在时有定义
由此可以直接得到三条推论:
- 后继存在时,第 0 层每个节点的 span 均为 1(相邻元素的编号相差 1)。
- 头节点在第 i 层的 span 等于该层后继的编号。由于头节点的编号为 0,沿某一层从头节点出发、逐个累加各节点的 span 直到该层最后一个节点,累加结果恰好等于最后一个节点的编号。这是一条可以在运行期直接校验的不变式。
- 从最高层向第 0 层前进时,每次向右移动都把当前节点在该层的 span 累加进计数器,累加值始终等于当前节点的编号。
后继为空时 span 不被使用。 位于某一层末尾的节点,其 span 没有对应的后继可比,因此该字段不会被任何查询读取。实现中的两种常见处理是把它置为 0,或让它保留更新公式算出的任意值(在特定插入顺序下可能是负数)。两种做法都不影响正确性,条件是所有读取 span 的地方都以"后继存在"为前提;rank 查询与按排名查询的循环条件天然满足这一点。
求给定元素的排名:按普通查找的方式移动,移动时累加 span;由于移动条件放宽为"后继键小于或等于目标",查找过程会直接停在目标节点上,此时累加值即目标的排名。
rank(key):
x = header
rank = 0
for i = level - 1 downto 0:
while x.next[i] != NULL and x.next[i].key <= key:
rank += x.span[i]
x = x.next[i]
if x != header and x.key == key:
return rank
return 0
求指定排名的元素:把移动条件改为"移动后的编号不超过目标排名",在第 0 层停下时的节点即目标。
byRank(target):
x = header
rank = 0
for i = level - 1 downto 0:
while x.next[i] != NULL and rank + x.span[i] <= target:
rank += x.span[i]
x = x.next[i]
if rank == target and x != header:
return x
return NULL
两者都是 O(log n) 的期望代价。作为对照:有序数组按下标访问是 O(1)、按值查找是 O(log n),但插入为 O(n);红黑树两种查询都是 O(log n),但默认不携带排名信息,需要额外维护每个节点的子树规模字段(并在旋转时同步修正),这是 TreeMap 没有排名接口的原因(见 Java 集合框架实现原理 第 5.1 节)。
span 的维护方法与插入、删除中的更新顺序见 3.1.4 节。span 未同步更新是排名查询出错的唯一来源,且症状隐蔽——查找与范围查询仍然正确,只有排名结果偏移。
2.5.3 前驱与后继查询
由于查找结束时停留在目标在底层的前驱上,以下查询都可以直接复用查找过程:
| 查询 | 语义 | 实现 |
|---|---|---|
| 前驱 | 小于目标的最后一个元素 | 查找结束后 update[0] 即前驱 |
| 后继 | 大于目标的第一个元素 | 查找结束后,若 update[0].next[0] 的键不等于目标,则该节点即后继;否则取它的后继 |
| 向下取整 | 不大于目标的最后一个元素 | 键等于目标时即目标自身,否则为前驱 |
| 向上取整 | 不小于目标的第一个元素 | 键等于目标时即目标自身,否则为后继 |
跳表的这几类查询不需要额外的结构支持,也不需要像二叉搜索树那样回溯到祖先节点。这是"查找路径自带上下文"带来的便利:路径上的每一层都留下了前驱引用。
2.6 与平衡树的对比
跳表与平衡树在内存中的核心操作的量级相同,差异集中在实现成本、结构维护方式与硬件行为上。
| 维度 | 跳表 | 平衡二叉树(红黑树、AVL) | B+ 树 |
|---|---|---|---|
| 平衡方式 | 随机层数,期望平衡 | 旋转与重新着色,确定性平衡 | 节点分裂与合并,按页平衡 |
| 最坏复杂度 | 查找、插入、删除均为 O(n) | 均为 O(log n) | 均为 O(log n) |
| 期望复杂度 | O(log n) | 不适用(结论是确定的) | 不适用 |
| 单次更新的改动范围 | 每层至多两个指针,涉及常数个节点 | 可能触发沿路径回溯的旋转与着色 | 可能触发页分裂并向上传播 |
| 范围查询 | 定位起点后沿第 0 层顺序推进 | 中序遍历需要显式栈或维护迭代状态 | 叶节点以双向链表串联,顺序扫描对磁盘友好 |
| 排名查询 | span 字段直接支持 | 需要额外维护子树规模并在旋转时修正 | 需要额外维护计数或按页统计 |
| 并发实现 | 局部指针 CAS,已有成熟的无锁实现 | 旋转影响的结构范围大,无锁实现困难 | 页粒度加锁,面向磁盘场景 |
| 单元素结构开销 | 期望 p/(1 − p) 个后继指针;按实际层数分配时 p = 1/4 约为 0.33 个 | 三个指针(左右子与父)加颜色位,约 48 字节 | 节点按页组织,页内扇出大,指针的相对开销小 |
| 键的比较成本 | 每层可能多次比较同一批键 | 每次比较下降一层,比较次数等于树高 | 页内二分,比较次数少但每次都可能触发页访问 |
| 缓存局部性 | 第 0 层顺序推进局部性好,层间下降为随机访问 | 沿指针自根向下跳转,节点分散在堆中 | 页内连续,页间按需读取 |
| 磁盘索引适用性 | 不适用(层间跳转对应随机 IO) | 不适用(树高随行数增长,比较次数对应页访问) | 默认结构 |
针对四个关键维度的结论:
实现复杂度。 红黑树的插入需要处理三种失衡情形,删除需要处理四种,且都要在旋转后回溯检查性质是否被破坏;判定的依据是五条性质(节点非红即黑、根为黑、叶子为黑、不存在连续红节点、任一路径上黑节点数相同),任何一条被破坏都需要修复。跳表的插入与删除只做指针改写,唯一的"决策"是随机层数,代码量与出错点都明显更少(红黑树性质的完整列表与 TreeMap 的复杂度见 Java 集合框架实现原理 第 5.1 节)。
范围查询。 跳表在第 0 层上是一条普通的单向链表,范围推进就是顺序读取后继;平衡树的中序遍历需要额外的栈或线索化处理。B+ 树把全部数据放在叶节点并用双线链表串联,顺序扫描的磁盘行为最好,这也是它成为磁盘索引默认结构的主要原因(见 mysql: 索引与执行计划 第 2.1.1 节的四种索引结构对照)。
并发友好性。 跳表的更新量集中在相邻指针上,适合用 CAS 实现无锁算法;平衡树的旋转会改变多个节点的父子关系,难以原子化。这一差别直接决定了标准库的选择:Java 提供了无锁的 ConcurrentSkipListMap,却没有提供无锁的并发红黑树。
内存与缓存。 平衡树每个节点需要三个指针加一个颜色位,结构固定;跳表的开销取决于 p 与实现方式——按实际层数分配时开销可以低于平衡树,但若为每个节点预留 MAX_LEVEL 个槽位,开销会高出数量级(见 3.1.2 节)。缓存行为上,跳表在第 0 层的顺序推进比树的向下跳转更友好,但层间的下降仍是随机访问,两者的整体差距需要实测确定。
最后一点需要强调:量级相同不等于性能相同。跳表与红黑树都是 O(log n),实际取舍落在常数因子、缓存局部性与并发需求上,属于必须实测才能给出结论的情形(见 复杂度与算法分析 第 2.7 节)。
三、实现
3.1 结构定义
3.1.1 节点的两种表示
跳表节点有两种等价的表示方式。
表示一:多链表加向下指针。 每个节点只保存一个后继引用,另用一条独立的"索引链表"保存到下层节点的引用。这种表示把"数据"与"索引"分开,节点数量更多但每个节点更小。
表示二:层数组。 每个节点持有一个按层索引的后继数组(以及可选的跨距数组),数组长度等于该节点的高度。这种表示在教科书与 Redis 中都很常见,实现更紧凑。
final class Node<K, V> {
final K key;
V value;
final Node<K, V>[] next; // next[i]:第 i 层的后继节点;数组长度等于本节点的高度
final int[] span; // span[i]:第 i 层到后继的跨距,用于排名查询
@SuppressWarnings("unchecked")
Node(K key, V value, int height, int maxLevel, boolean withSpan) {
this.key = key;
this.value = value;
this.next = (Node<K, V>[]) new Node[height];
this.span = withSpan ? new int[height] : null;
}
}
关键点是数组长度等于节点自身的高度,而不是 MAX_LEVEL。用固定长度数组实现的写法更简单,但会让每个节点都付出 MAX_LEVEL 个指针的代价(见 3.1.2 的量化)。
Redis 的实现属于第二种表示,并额外保存一个第 0 层的前驱引用,用于支持逆序遍历:
typedef struct zskiplistNode {
sds ele; /* 成员 */
double score; /* 分值,参与比较 */
struct zskiplistNode *backward; /* 第 0 层的前驱,用于逆序 */
struct zskiplistLevel {
struct zskiplistNode *forward; /* 该层的后继 */
unsigned long span; /* 该层的跨距 */
} level[]; /* 柔性数组,长度等于该节点的层数 */
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length; /* 元素个数,用于头节点的新增层跨距 */
int level; /* 当前的最大层数,查找的起点层 */
} zskiplist;
forward 与 span 放在同一个结构体里按层组织,使每一层的两个字段在同一缓存行附近,这是"层数组"表示相对于"独立索引链表"的一个额外收益。
3.1.2 头节点的特殊处理
头节点不参与数据存储与比较,只作为查找的起点,因此需要单独处理三处。
- 键为占位值。头节点的键取
null或一个小于所有键的哨兵值。比较逻辑中必须保证头节点不会与目标键相等,否则查找会在头节点上提前停止。 - 高度等于
MAX_LEVEL。头节点的高度取最大值,使最高层始终有一个合法的起点。而表的实际层数单独用一个整数字段维护,查找的起点层取该字段而非MAX_LEVEL,否则新插入的高层节点之上会多出若干空层,每次查找都要先下降若干次。 - span 的初值。头节点在第 i 层的 span 应等于该层后继的编号。表为空时所有层的 span 均为 0;插入第一个进入第 i 层的节点时,头节点在该层的 span 需要先按"跨到空指针"设置,再由插入公式改写为新节点的编号(见 3.1.4 节与 3.2 节的实现)。
内存开销的量化。 若采用"每个节点固定 MAX_LEVEL 个后继槽位"的写法,以 64 位 JVM 开启压缩指针为例:对象头 12 字节,每个引用 4 字节,对象按 8 字节对齐。MAX_LEVEL = 32 时,后继数组为 32 × 4 = 128 字节,加上数组头 16 字节与对象的键值字段,单个节点的结构开销在 160 字节以上。p = 1/4 时节点高度的期望为 4/3,按实际高度分配只需约 2 个槽位,即 8 字节加数组头。两者的差距:
| 实现方式 | 单节点结构开销 | 100 万元素的结构占用 |
|---|---|---|
固定 MAX_LEVEL = 32 的数组 | 约 160 字节以上 | 约 160 MB 以上 |
| 按实际高度分配(p = 1/4) | 约 20 至 30 字节 | 约 20 至 30 MB |
对照:TreeMap 的单元素结构开销 | 约 48 字节 | 约 48 MB |
TreeMap 的数值口径与 JVM 对象开销的计算方式见 Java 集合框架实现原理 的内存占用估算一节。若同时维护 span 数组,跳表的每元素开销约翻倍;只支持范围查询而不需要排名的实现可以省略 span。
3.1.3 层数上限与随机函数
private static final int MAX_LEVEL = 32;
private static final double P = 0.25;
private int randomLevel() {
int level = 1;
while (level < MAX_LEVEL && ThreadLocalRandom.current().nextInt(4) == 0) {
level++;
}
return level;
}
要点:
- 使用按位比较而非浮点乘法。
nextInt(4) == 0等价于以 1/4 的概率晋升,避免浮点运算与浮点比较的额外开销。Redis 的写法是用 16 位掩码:while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF)) level++;。 - 随机源必须与插入顺序和键值无关。使用固定种子的伪随机数、把键的哈希值当作随机结果、或直接用计数器取模,都会使层数分布失真(见 3.5 节)。
- 上限判断放在循环条件中,不能靠事后截断:事后截断会让生成过程在极端情况下退化为长循环。
- 随机函数不需要线程安全,多线程环境下应使用线程本地的随机源(如上例的
ThreadLocalRandom),共享Random实例会成为写热点的竞争源。
3.1.4 span 字段的维护方式
span 的维护原则是在改写指针的同时修正两端节点的跨距,因为 span 的定义本身依赖节点在第 0 层的编号。
插入时(记号:rank0 为第 0 层前驱的编号,rank[i] 为第 i 层前驱的编号,prev = update[i]):
node.span[i] = prev.span[i] − (rank0 − rank[i]) # 新节点到原后继的跨距
prev.span[i] = (rank0 − rank[i]) + 1 # 前驱到新节点的跨距
删除时(target 为被删除节点):
prev.span[i] = prev.span[i] + target.span[i] − 1 # 前驱直接跨过 target
此外还有两处容易遗漏的修正:
- 新出现的层。当插入节点的层数超过表的当前最大层数时,这些层的头节点在插入前还没有后继,其 span 表示"头节点跨到空指针"的距离,即当前元素总数。代码中先把这个值写入头节点的对应槽位,再由它减去新节点之前的元素数,得到新节点在这些层的跨距;插入完成后该槽位被改写为新节点的编号。新节点在这些层的后继为空,其跨距不会被查询使用,但仍按同一公式赋值,以免出现负值导致不变式校验失败。
- 未出现在被删除节点高度范围内的层。删除时,若某层的前驱后继不是目标节点,说明目标没有出现在该层,此时该层的前驱 span 需要减 1,因为底层少了一个元素,跨距相应缩短。
span 只在需要排名查询时才有必要维护。若实现只提供查找与范围查询,可以完全省略该数组,代价是之后无法在不改动结构定义的前提下补上排名能力。
3.2 核心操作实现
以下给出一个完整的 Python 参考实现,覆盖查找、插入、删除、范围查询、按排名查询与前驱后继查询,并维护 span 字段以支持排名。约定:key 为排序键,value 为载荷;键在插入后不可修改。
import random
MAX_LEVEL = 32
P = 0.25
class Node:
__slots__ = ("key", "value", "next", "span")
def __init__(self, key, value, height):
self.key = key
self.value = value
self.next = [None] * height # next[i]:第 i 层的后继
self.span = [0] * height # span[i]:第 i 层到后继的跨距
class SkipList:
def __init__(self):
self.header = Node(None, None, MAX_LEVEL) # 头节点高度固定为 MAX_LEVEL
self.level = 1 # 表的当前最大层数,查找的起点层
self.length = 0 # 元素个数,用于头节点新增层的 span
def _random_level(self):
level = 1
while level < MAX_LEVEL and random.random() < P:
level += 1
return level
定位与前驱记录。 查找、插入、删除、排名查询都建立在同一次定位上,因此把它抽成一个内部方法,返回目标节点与每层前驱及其编号。
def _locate(self, key):
"""返回 (目标或其后的第一个节点, 按层索引的前驱与编号列表)。"""
update = [(self.header, 0)] * self.level # update[i] 对应第 i 层,下标与层号一致
x = self.header
rank = 0 # 当前节点在第 0 层的编号,头节点为 0
for i in range(self.level - 1, -1, -1):
while x.next[i] is not None and x.next[i].key < key:
rank += x.span[i] # 向右移动时累加跨距,rank 始终等于 x 的编号
x = x.next[i]
update[i] = (x, rank) # 第 i 层最后一个键小于 key 的节点
return x.next[0], update
查找。
def get(self, key):
node, _ = self._locate(key)
if node is not None and node.key == key:
return node.value
return None
插入。
def put(self, key, value):
node, update = self._locate(key)
if node is not None and node.key == key:
node.value = value # 键已存在:只更新载荷,结构不变
return False
height = self._random_level()
if height > self.level:
for i in range(self.level, height):
# 新增层的头节点直接跨到空指针,跨距为当前元素总数
update.append((self.header, 0))
self.header.span[i] = self.length
self.level = height
rank0 = update[0][1] # 第 0 层前驱的编号
new_node = Node(key, value, height)
for i in range(height):
prev, prev_rank = update[i]
new_node.next[i] = prev.next[i]
prev.next[i] = new_node
new_node.span[i] = prev.span[i] - (rank0 - prev_rank)
prev.span[i] = (rank0 - prev_rank) + 1
for i in range(height, self.level):
update[i][0].span[i] += 1 # 该层未插入新节点,但底层多了一个元素
self.length += 1
return True
删除。
def remove(self, key):
target, update = self._locate(key)
if target is None or target.key != key:
return False
for i in range(self.level):
prev = update[i][0]
if prev.next[i] is target:
prev.span[i] += target.span[i] - 1 # 前驱直接跨过目标
prev.next[i] = target.next[i]
else:
prev.span[i] -= 1 # 目标未出现在该层,只需缩短跨距
while self.level > 1 and self.header.next[self.level - 1] is None:
self.level -= 1 # 最高层已空,收缩层数
self.length -= 1
return True
范围查询。 先定位区间的起点,再沿第 0 层推进。offset 用于支持"跳过前若干个结果"的分页语义,其实现依赖编号,因此也借助 span。
def range(self, lo, hi, offset=0, limit=None):
"""返回键落在 [lo, hi) 内的条目,按键升序。"""
x = self.header
for i in range(self.level - 1, -1, -1):
while x.next[i] is not None and x.next[i].key < lo:
x = x.next[i]
x = x.next[0] # 第一个键不小于 lo 的节点
out = []
skipped = 0
while x is not None and x.key < hi:
if skipped < offset:
skipped += 1
else:
out.append((x.key, x.value))
if limit is not None and len(out) >= limit:
break
x = x.next[0]
return out
按排名查询与反向查询。
def rank(self, key):
"""返回键的名次(从 1 开始),不存在返回 0。"""
x = self.header
rank = 0
for i in range(self.level - 1, -1, -1):
while x.next[i] is not None and x.next[i].key <= key:
rank += x.span[i]
x = x.next[i]
if x is not self.header and x.key == key:
return rank
return 0
def by_rank(self, target):
"""返回名次为 target(从 1 开始)的节点。"""
x = self.header
rank = 0
for i in range(self.level - 1, -1, -1):
while x.next[i] is not None and rank + x.span[i] <= target:
rank += x.span[i]
x = x.next[i]
if rank == target and x is not self.header:
return x.key, x.value
return None
def predecessor(self, key):
"""小于 key 的最后一个条目。"""
node, update = self._locate(key)
prev = update[0][0]
return None if prev is self.header else (prev.key, prev.value)
def successor(self, key):
"""大于 key 的第一个条目。"""
node, update = self._locate(key)
if node is not None and node.key == key:
node = node.next[0]
return None if node is None else (node.key, node.value)
按分值查询。 在有序集合的语义中,排序键是分值、载荷是成员,因此"按分值范围查询"就是把上述 range 应用到分值上。需要注意区间端点的开闭:Redis 用前缀 ( 表示开区间、-inf 与 +inf 表示无界,而记录相同分值的成员按成员的字典序排列,因此排序键实际是"分值加成员"的二元组。把分值作为唯一排序键时,同分成员的顺序不确定,需要稳定顺序时应把次级键编码进分值(见 3.4 节)。
def range_by_score(self, min_score, max_score, offset=0, limit=None):
"""min_score 与 max_score 均为闭区间端点。"""
return self.range(min_score, max_score + 1e-12, offset, limit)
实现中的三处要点:
_locate一次完成两件事。它同时给出目标节点与每层前驱及其编号,避免了"先查找再逐层重新定位前驱"的重复遍历。插入与删除共用它,是update[]数组的价值所在。- 编号在移动过程中累加。
rank只在向右移动时增加(增加的是离开的节点在该层的跨距),下降时不改变。这一约定使编号的计算不依赖层级,与 2.5.2 节的定义一致。 by_rank的移动条件用"移动后的编号不超过目标"。因为条件是"结果不超过",所以会一直移动到最接近目标的位置;若改成"移动后的编号小于目标",会在最后一个节点前提前停止。- 末尾节点的 span 由同一公式产生,不需要单独处理。上述代码中
span始终按同一公式赋值,位于某层末尾的节点会得到一个不参与计算的值(第 0 层上即 0)。所有累加 span 的位置都以"后继存在"为循环条件,因此这些值不会被读取。若出于调试或校验需要,也可以在插入与删除后统一把末尾节点的 span 规整为 0。
3.3 复杂度与实测
3.3.1 期望复杂度
| 操作 | 期望复杂度 | 最坏复杂度 | 说明 |
|---|---|---|---|
| 查找 | O(log n) | O(n) | 期望步数为 (1/p)·log_{1/p} n |
| 插入 | O(log n) | O(n) | 定位 O(log n),逐层挂接 O(height) 期望为 O(1) |
| 删除 | O(log n) | O(n) | 同插入 |
| 按排名查询 | O(log n) | O(n) | 需要维护 span |
| 范围查询(结果 M 个) | O(log n + M) | O(n + M) | 定位起点后顺序推进 |
| 前驱、后继、向上向下取整 | O(log n) | O(n) | 复用查找过程 |
| 空间 | O(n) | O(n·MAX_LEVEL) | 期望指针数为 n·(1 + p/(1 − p)) |
最坏情况的实际意义有限:退化为 O(n) 的概率为 (1 − p)^n,但结论的表述仍应区分期望与最坏,因为"期望 O(log n)"与"最坏 O(log n)"在延迟上界、超时设置与容量规划的语境中不等价(见 复杂度与算法分析 第 2.3 节)。
3.3.2 实际内存开销估算
按 3.1.2 的 JVM 对象开销口径(对象头 12 字节、引用 4 字节、按 8 字节对齐),跳表节点的结构开销由三部分组成:
| 组成 | 说明 |
|---|---|
| 固定部分 | 对象头、键引用、载荷引用、第 0 层的前驱引用(若需要逆序) |
| 层数组 | 每个槽位一个后继引用(4 字节),数组对象另有 16 字节头 |
| span 数组 | 每个槽位一个 4 字节整数,可省略 |
以 p = 1/4、节点高度期望 4/3 计算,层数组的槽位期望约为 1.33 个,加上数组头,落在 20 至 30 字节区间。这一数值仅统计结构本身,不含键与载荷对象——若键是长度较长的字符串,键对象本身的开销会超过结构开销,这与 HashMap、TreeMap 的情形一致。
估算时的两个注意点:
- 节点的层数分布不是均匀的。约 75% 的节点高度为 1(p = 1/4 时),它们的层数组只有 1 个槽位但同样带 16 字节的数组头,因此"平均槽位数"会低估实际开销。改用定长数组按需分配、或把第 0 层的后继引用做成节点内的独立字段(避免为高度为 1 的节点单独分配数组),都能减少这部分浪费。
- span 数组使开销近似翻倍。若只需要范围查询而不需要排名,应省略该数组;反之,需要排名时这笔开销无法回避,对比"红黑树加子树规模字段"的开销是同一量级。
3.3.3 与其他有序结构的实测对比方法
跳表、红黑树、有序数组、B 树在内存中的查找都是 O(log n) 或更好,量级相同意味着必须实测才能给出取舍结论。设计对比基准时需要注意以下事项,方法层面的细节见 JMH 微基准测试。
| 维度 | 设计要点 |
|---|---|
| 规模参数化 | 至少覆盖 10³、10⁵、10⁷ 三个点,观察耗时随规模变化的曲线形态,而不是比较单点数值 |
| 操作混合 | 分别测纯查找、查找与插入各半、含删除的更新流;范围查询单独测并参数化结果数量 M |
| 数据分布 | 随机键与递增键分别测量;跳表的结论与输入分布无关,其他结构不是,因此有序输入下的对比才反映真实差异 |
| 键的类型 | 整数键与字符串键分别测;键的比较代价可能主导整体耗时,抵消结构差异 |
| 结果消费 | 用黑洞消费返回值,避免查找被即时编译整体消除 |
| 预热与隔离 | 分叉进程隔离、固定预热轮次、固定堆与 GC 参数;未预热时测到的是解释执行的耗时 |
| 同时记录分配量 | 时间之外还要记录每次操作的分配字节数,内存开销差异往往是选型的决定性因素 |
结论的表述必须带条件:规模、数据分布、JDK 版本、堆参数。跨条件外推(例如用 10³ 规模的测量结果推断百万级的表现)与无条件的最优性表述都不可用。
3.4 工程应用
3.4.1 Redis 有序集合
Redis 的有序集合(zset)在元素较多或成员较长时使用 skiplist 加 hashtable 的组合编码:skiplist 提供按分值的有序性与范围查询,hashtable 提供从成员到分值的 O(1) 定位。两者共享同一份成员对象,不复制数据。
编码的切换条件是:
| 编码 | 触发条件 | 提供的操作 |
|---|---|---|
| listpack | 元素数不超过 zset-max-listpack-entries(默认 128)且成员长度不超过 zset-max-listpack-value(默认 64) | 紧凑存储,查找与范围查询退化为线性扫描,但常数因子小 |
| skiplist 加 hashtable | 上述任一条件不满足 | 按分值 O(log N) 定位与范围查询,按成员 O(1) 取分值 |
切换是单向的:一旦转为 skiplist 加 hashtable,即使后续元素被删除也不会退回 listpack。元素数恰好越过阈值的那次写入会明显慢于其他命令,是慢日志的常见来源。完整的编码转换表与阈值配置见 Redis 核心与数据结构 第 2.2.3 节。
Redis 选择跳表而不是平衡树的理由可以逐条对应到本文的对比结论:
- 范围查询的实现直接。
ZRANGEBYSCORE只需定位起点后沿第 0 层推进,不需要中序遍历所需的栈或线索化。 - 排名查询有原生支持。span 字段使
ZRANK、ZREVRANK成为 O(log N) 操作;用平衡树实现则需要额外维护子树规模。 - 更新逻辑简单。插入与删除只改局部指针,没有旋转与着色,代码量与调试成本都更低。
- 内存可调。晋升概率与层数上限都是编译期常量,可以按内存预算在"指针数量"与"查找步数"之间调整。
- 并发不是理由。Redis 的命令由单线程串行执行,跳表的并发优势在此不适用;选择跳表的依据是前四条。
需要补充的是,ZRANGE 的偏移量语义使深分页成为问题:偏移量随元素数增大而变慢。排行榜的落地方式、深分页的游标替代方案、同分排序的编码方法、榜外数据的裁剪方式见 Redis 缓存实践与常见问题 第 2.5 节;以分值作为到期时间戳的延时队列方案、取出与删除的原子性要求以及与 Stream 消费者组的对比见同一文档第 2.6 节。跳表提供的正是这两类用法依赖的三项能力:按分值的范围查询、按成员的常数级定位、按排名的随机访问。
3.4.2 其他系统中的实现
| 系统或库 | 用途 | 选择跳表的依据 |
|---|---|---|
Java ConcurrentSkipListMap / ConcurrentSkipListSet | 并发有序映射与集合,支持范围与邻近查询 | 无锁实现可行,读操作基本无同步;标准库未提供无锁的并发平衡树 |
| LevelDB、RocksDB 的内存表(MemTable) | 写入缓冲,按用户键有序存放 | 写入只改局部指针,无需再平衡带来的额外同步;读取并发无需锁 |
| Lucene 的倒排表跳读结构 | 加速多个词项倒排表的合并与跳读 | 在有序的文档号列表上构造跳转层次,跳过不可能命中的区间 |
| Redis 有序集合 | 排行榜、延时队列、滑动窗口限流 | 有序性、范围查询与排名查询的组合 |
Java 侧的使用边界见 Java 集合框架实现原理 中"与并发的配合"一节:ConcurrentSkipListMap 保证单个方法的原子性,不保证复合操作(判断后写入)的原子性,后者仍需使用 computeIfAbsent、merge 等原子方法。
与其他有序结构的取舍可以概括为一句话:磁盘索引优先 B+ 树(页对齐与扇出带来更少的 IO 次数),内存中的并发有序结构优先跳表(更新局部化使无锁实现可行),内存中的单线程有序结构在跳表与平衡树之间按实现成本与实测结果选择。
3.5 常见问题与排查
| 现象 | 可能原因 | 验证与处置 |
|---|---|---|
| 查找耗时随元素数线性增长,即使元素量很大 | 随机层数分布失真,绝大多数节点高度为 1,结构退化为有序链表 | 统计各层节点数:第 i 层的节点数应约为 n·p^i;检查随机函数是否使用了固定种子、与键相关的值或恒定返回值 |
| 层数集中在少数几个取值上 | 随机函数把键的哈希值或插入序号当作随机结果,或对随机结果做了取模等变换 | 用独立于键的随机源(如线程本地伪随机);对小样本做分布检验,确认高度为 k 的频率接近 p^(k−1)·(1 − p) |
| 内存占用显著高于估算 | 每个节点固定分配了 MAX_LEVEL 个后继槽位;或层数上限设置过高 | 按节点实际高度分配层数组;核对 MAX_LEVEL 是否远大于 log_{1/p} n 的期望值 |
ZRANK 或按排名查询的结果偏移 | span 字段未同步维护:新增层时头节点跨距的中间值未设置,删除时未出现在目标高度的层未递减 | 校验不变式:沿任意一层从头节点逐个累加各节点的 span,得到的编号应与沿第 0 层逐节点计数得到的编号一致;第 0 层上非末尾节点的 span 应为 1 |
| 并发环境下查找偶发失败或丢失元素 | 无锁实现的插入未完成所有层,或删除只做了物理摘除而未标记 | 确认插入的层间一致性与删除的两阶段顺序;以第 0 层为成员关系的判定依据 |
| 范围查询的耗时与结果数量不成比例 | 在范围推进中每取一个元素都重新执行一次查找,代价退化为 O(M·log n) | 定位起点后沿第 0 层顺序推进;检查封装层是否把范围迭代实现成了逐次查找 |
| 更新某元素后查找不到或顺序错乱 | 修改了参与比较的键(有序集合中修改了成员的分值),破坏了有序性 | 把更新实现为"按旧键删除加按键的新值插入";禁止原地修改排序键 |
| 插入或删除后高层链表断裂 | 删除时未判断某层的前驱后继是否就是目标节点,直接改写了该层的指针 | 删除逐层判断 prev.next[i] == target;插入时按层数组长度而非表的层数循环 |
| 最高层长期只有一个节点,查找步数偏多 | 层数收缩只在删除时进行,插入时新增层的条件判断有误,或层数上限过小 | 核对插入时"层数超过当前最大层数则更新表头节点"的分支;确认 MAX_LEVEL 大于期望层数 |
排查这类问题的通用手段是打印层数与跨距的分布:各层节点数、节点高度的直方图、头节点在各层的 span、元素总数。跳表的缺陷大多表现为分布偏离期望,而分布是可以在运行期直接统计出来的,比构造特定用例更直接。
3.6 选型判断
3.6.1 与相邻结构的取舍
| 需求 | 建议结构 | 理由 |
|---|---|---|
| 只需等值查找,不要求顺序 | 哈希表 | 期望 O(1),常数更小,实现更简单 |
| 需要有序遍历与范围查询,单线程 | 跳表或平衡树 | 量级相同,差异在实现成本、排名支持与常数因子,应实测 |
| 需要并发有序访问 | 跳表(如 ConcurrentSkipListMap) | 更新局部化,无锁实现成熟;平衡树无锁化困难 |
| 需要按排名访问 | 跳表(维护 span) | 排名可随查找路径累加得到;平衡树需额外维护子树规模 |
| 数据静态、只需查找与范围 | 有序数组加二分 | 空间更紧凑,缓存局部性最好,无指针开销 |
| 需要频繁取最值 | 二叉堆 | 取最值为 O(1),插入为 O(log n),比有序结构更省 |
| 磁盘索引、大范围顺序扫描 | B+ 树 | 页内扇出把树高压在很小的常数范围内,叶节点链表支持顺序 IO |
| 元素数很少(如百以内) | 有序数组或紧凑编码 | 线性扫描的常数因子小于层次结构的维护成本,Redis 的 listpack 阈值就是这一判断的体现 |
上表中的结构都实现同一个抽象数据类型——有序映射(按键定位、顺序遍历、范围查询),接口相同而代价不同。抽象数据类型与具体存储结构的区分、以及"映射"这一类 ADT 的常见实现对照见 抽象数据类型(ADT)。
3.6.2 选择跳表时的检查项
结构性判断:
- 访问模式是否以有序遍历、范围查询、排名查询或前驱后继查询为主;若以等值查找为主,哈希表更合适。
- 是否需要并发有序访问;若需要,跳表是内存结构中的默认选择。
- 是否存在严格的延迟上界要求;若有,需要评估"期望 O(log n)、最坏 O(n)"是否可接受。
实现层面的检查:
- 节点按实际高度分配还是按
MAX_LEVEL固定分配;后者的内存代价在元素数大时不可接受。 - 随机源是否独立于键值与插入顺序,
MAX_LEVEL是否与预期元素规模匹配。 - 是否需要排名查询;若需要,span 字段的维护是否覆盖了新增层与删除时的全部情形。
- 更新操作是否实现为"删除加插入",排序键是否被禁止原地修改。
- 范围查询是否沿第 0 层顺序推进,而不是逐次重新查找。
- 若为无锁实现,删除是否分为标记与摘除两步,成员关系的判定是否以第 0 层为准。
四、总结
问题与解法。 链式存储无法随机访问,因此有序链表的查找只能顺序扫描,代价为 O(n);"加索引"通过抽取上层节点把比较范围逐层压缩,把代价降到 O(log n),代价是索引本身占用与元素数同阶的空间,并且严格比例在更新后被破坏、需要重建。跳表的做法是放弃严格比例,用概率决定节点高度,使期望上的比例关系仍然成立,同时把更新变成纯局部操作。
结构与概率分析。 晋升概率 p 使第 i 层的节点数期望为 n·p^i,索引指针数的期望为 n·p/(1 − p)(p = 1/2 时约 n,p = 1/4 时约 n/3),最大层数约为 log_{1/p} n。每层的水平步数期望不超过 1/p,层数为 log_{1/p} n,两者相乘得到期望查找步数 (1/p)·log_{1/p} n。该式在 p = 1/e 处取极小值,但 p = 1/2 与 p = 1/4 与之相差约 6%,而索引空间相差三倍,因此 p 的取值主要由空间预算决定,1/4 是常见选择。
稳定性的来源。 层数与键值无关,因此不存在能构造出退化输入的键序列;n 个节点中出现高度超过期望值 c 层的概率上界为 p^c,与元素数无关;全部节点高度为 1 的退化概率为 (1 − p)^n,随元素数指数下降。结论的准确表述是"期望 O(log n)、最坏 O(n)",与平衡树的确定性最坏 O(log n) 不是同一个保证。
插入与删除。 两者共用同一次定位:查找过程中把每一层停下的前驱节点写入 update[] 数组,插入与删除据此在常数个指针上完成改写。删除需要逐层判断前驱的后继是否就是目标节点(目标的高度可能小于表的层数),并在最高层变空时收缩层数。并发实现的关键是让更新局部化:无锁方案把删除分为标记与摘除两步,并允许索引层与第 0 层短暂不一致。
范围查询与排名。 范围查询定位起点后沿第 0 层顺序推进,代价为 O(log n + M);若在推进中逐次重新查找,会退化为 O(M·log n)。排名查询依赖 span 字段(定义为到同层后继所跨越的第 0 层元素个数),向右移动时累加 span 即得到编号,因此求排名与按排名取元素都是 O(log n)。span 未同步更新是排名出错的唯一来源,且只在排名结果上体现。
与平衡树的对比。 两者的核心操作量级相同,差异在四处:跳表的更新只改局部指针,实现简单且可以无锁化;平衡树的旋转影响范围大,无锁实现困难;跳表用 span 直接支持排名,平衡树需要额外维护子树规模;内存与缓存行为取决于实现方式与 p 的取值,需要实测确定。与 B+ 树的对比则取决于存储介质:内存中跳表因更新局部化与实现简单被广泛采用,磁盘上 B+ 树因页内扇出与叶节点链表带来的 IO 优势而占优。
工程落点。 Redis 有序集合在元素较多或较长时使用 skiplist 加 hashtable 的组合,skiplist 提供按分值的有序性与范围查询以及基于 span 的排名能力,hashtable 提供按成员的常数级定位;切换阈值由 zset-max-listpack-entries 与 zset-max-listpack-value 控制,且切换是单向的。跳表支撑的典型用法是排行榜与延时队列,前者依赖范围查询与排名,后者依赖以到期时间戳为分值的范围查询。其他实现出现在并发有序映射、存储引擎的内存表与倒排索引的跳读结构中。
实现与排查。 节点应按实际高度而非 MAX_LEVEL 分配层数组,否则单元素开销会高出数量级;随机源必须独立于键值与插入顺序,MAX_LEVEL 需与预期元素规模匹配;排序键不可原地修改,更新应实现为删除加插入。排查的切入点是分布——各层节点数、节点高度的直方图、头节点各层的 span 与元素总数,这些量在运行期可以直接统计,比构造特定用例更容易定位问题。
跳表的价值不在于结构本身的复杂度,而在于它把"有序结构的平衡"这一确定性问题转化为概率问题,从而用更少的实现约束换来同阶的期望性能。理解了随机层数如何替代旋转,也就理解了这一结构在内存中的并发场景与有序容器中被反复选用的原因。