probabilistic index / ordered structure

Skip List 跳表

P(H ≥ k)=p^k 节点能站到第 k 层的概率按指数衰减。
E[n_k]=n·p^k 第 k 层的期望节点数自然变稀疏。
update[i] 插入和删除只改搜索路径附近的前驱指针。
LIVE STRUCTURE
ready
expected height log₂ n 高度由连续抛硬币决定。
search path 0 hops 横向跳跃 + 向下收窄。

跳表把一个有序链表升级成多层“快速通道”：底层保存全部元素，上层用随机抽样留下稀疏索引。 它用很少的局部指针维护，换来接近平衡树的 O(log n) 搜索、插入和删除。

01

目的：用概率给有序链表加索引

跳表不是用旋转保持平衡，而是用概率把索引层做成“越来越稀疏的高速路”。

底层是完整有序链表

L0 保存所有 key，节点从小到大连接。任何查找最终都落到底层，因此跳表首先是一个有序集合或有序映射。

上层是随机索引

新节点插入时不断以概率 p “晋升”。若 p=0.5，约一半节点有 L1，四分之一有 L2，八分之一有 L3。

搜索像下楼梯

从最高层 head 出发，能向右就向右，下一步会越过目标时向下。路径单调前进，不会回头。

节点内存布局：一座塔就是一个 forward 数组

42
forward[3]
forward[2]
forward[1]
forward[0]

节点高度不是全局数组，而是节点自己的指针数组长度。高节点更少，所以总指针数期望为 n / (1-p)。

随机晋升：连续成功才继续升层

L0
L1
L2
L3
L4

若 p=0.5，能到 L4 的节点大约只有 1/16。跳表靠这种几何分布形成“少数高塔，多数矮塔”。

Invariant 1

每一层都是按 key 递增的链表，且高层链表是低层链表的子序列。

Invariant 2

head 拥有最大层数，作为所有层的哨兵，避免边界分支散落在代码里。

Invariant 3

搜索指针只向右或向下移动，因此访问过的位置不会再次访问。

Invariant 4

更新只依赖每层前驱 update[i]，不会触碰与搜索路径无关的节点。

02

搜索、插入、删除

三种操作共享同一个关键动作：记录每一层最后一个小于目标值的前驱节点。

S

Search：横向跳跃，纵向收窄

在当前层检查 next。如果 next.key 小于目标，移动到 next；否则下降一层。到 L0 后检查 next.key 是否等于目标。

I

Insert：先找前驱，再局部接线

搜索过程中把每层前驱保存到 update[level]。随机生成新节点高度后，只需要在这些前驱后面改指针。

D

Delete：复用前驱数组，拆掉塔

若 L0 的候选节点就是目标，在它出现的每一层执行 update[i].forward[i] = target.forward[i]。

范围扫描：先定位左边界，再沿 L0 线性输出

跳表的随机索引只用于快速找到 start。找到第一个 key ≥ start 的节点后，后续 [start, end] 区间直接沿 L0 next 指针顺序走，天然保持排序。

L0 是真正的数据平面

23→ 31→ 37→ 42→ 48→ 55

这也是 Redis ZSet、LSM memtable 这类场景喜欢跳表的原因：点查像树，顺序扫描像链表。

03

实现方式

工程实现通常把每个节点设计为一个 forward 指针数组，数组长度就是节点塔高。

04

复杂度直觉

概率层高让每层节点数量近似按 p 衰减，搜索路径的期望长度因此接近对数级。

E[level k] ≈ n · p^k

p 越大，高层节点越多，索引更密但空间更高；p 越小，高层更稀疏，空间省但横向跳跃可能变多。

常用 p=0.5 或 p=0.25。p=0.5 直观、实现简单；p=0.25 指针更少，常见于内存敏感场景。

期望复杂度：search / insert / delete 都是 O(log n)，空间是 O(n)。极端随机序列会退化，但概率很低。

为什么不是 O(n)

在第 k 层，节点密度约为 p^k。搜索先在稀疏层跨大段区间，再逐层细化；每层期望横向移动是常数级。

高度上界怎么选

工程里通常令 maxLevel ≈ log1/p(N)。例如 N 约 2^32 且 p=0.25 时，32 层已经非常宽裕。

随机数的工程含义

随机高度不要求密码学安全，但要避免低位质量太差。生产实现常用快速 PRNG，并把层高生成写成可测试函数。

05

设计哲学

跳表的美感不在复杂规则，而在把“平衡”从全局约束转移为局部随机。

用概率替代结构旋转

平衡树需要维护严格形状，跳表只要求随机高度分布合理。插入和删除没有旋转，代码路径更短。

用局部修改服务并发

一次更新只触碰搜索路径附近的指针。很多并发跳表能把锁或 CAS 限制在少量节点上。

保留链表的顺序友好性

范围扫描从 L0 顺序走即可，不需要树的中序遍历栈。这让跳表适合 sorted set、memtable、时间线索引。

接受小概率，换取简单性

它不是最坏情况严格 O(log n) 的结构，却把实现、维护和调试成本降得很低。许多系统愿意做这个交换。