Treap 与跳表：随机平衡的期望代价与生产参数

有序集合要支持查找、插入、删除、按名次取元素，红黑树和 AVL 用确定性的平衡不变量保证 \(O(\log n)\) 最坏界，代价是插删时分情况修复。Treap 和跳表换了一条路：不维护不变量，而是让结构的形状由随机数决定，于是对任意输入序列，期望代价都是 \(O(\log n)\)。这两种结构的介绍很多，常见的说法里有几处经不起核对：把 Treap 的”期望高度”写成 \(2\ln n\)（\(2\ln n\) 是平均深度的主项，高度约为 \(4.311\ln n\)）；说”跳表比平衡树快”（Pugh 自己的实验里 AVL 树查找更快，他的摘要只说插入和删除快）；说 Redis 选跳表是因为并发友好（antirez 给出的三条理由里没有并发）；说跳表第 2 层有 \(1/p\) 比例的节点（应为 \(p\)）。

本文先把对手模型说清楚，再按原始论文推导 Treap 的深度、旋转次数和 split/merge，跳表的查找路径长度和 \(p\) 的取舍，每个公式都用 reproduce/ 里的程序计数核对；然后逐一对照 Redis 7.2.5、LevelDB 1.23、RocksDB 9.7.4、JDK 21 的源码，看生产实现取了什么参数、为什么；最后讨论”跳表是否更快”和”对手看得见随机数”这两个至今仍有新论文的问题。并发跳表的无锁算法由并发跳表一文展开，这里只列各实现的并发约定。

一、问题与对手模型

期望是对谁取的

两种结构的随机性都来自算法内部：Treap 给每个节点一个随机优先级，跳表给每个节点一个随机高度。输入的键序列可以是任意的，包括升序、降序或专门构造的序列。“期望 \(O(\log n)\)”的意思是：对每一个固定的操作序列，在算法自己的随机数上取期望。

这个保证成立有一个前提：操作序列不能依赖算法抽到的随机数。Pugh 在 CACM 论文里把它写成了明确的假设：

We assume an adversarial user does not have access to the levels of nodes; otherwise, he could create situations with worst-case running times by deleting all nodes that were not level 1.

这类对手叫不自适应对手（oblivious adversary）：它可以挑最坏的输入，但必须在看到随机数之前挑好。第十节的 E6 实验会演示违反这个假设的后果：删掉所有高于第 1 层的节点，跳表的平均查找路径从 33.9 步变成 37401 步。

与历史无关

两种结构还有一个让分析变简单的性质：当前的形状只由当前的键集合和各键抽到的随机数决定，与插入删除的先后次序无关。Treap 的这一点在第三节证明；跳表的形状显然只取决于哪些键在表里、各自高度是多少。Pugh 原文写道：“The sequence of operations that produced the current skip list does not matter.” 因此分析任何一次操作，只需要分析”\(n\) 个键、随机数独立同分布”这一种静态状态。

期望、高概率与最坏情况

期望界不说明尾部。两类结构的最坏情况都是 \(\Theta(n)\)（所有优先级恰好按键排序、所有高度都是 1），只是概率极小。Pugh 用他推导的概率上界给出过具体数字：\(p = 1/2\)、\(n = 4096\) 时，查找路径超过期望长度 3 倍的概率小于两亿分之一；摘要里另一句是，元素多于 250 个时，一次查找耗时超过期望 3 倍的概率小于百万分之一。Treap 的高度分布则由随机二叉搜索树的理论刻画（第四节）。需要确定性最坏界的场景（实时系统、内核），仍然应该用红黑树，见红黑树与 AVL。

二、谱系

flowchart LR
    V["Vuillemin 1980<br/>Cartesian tree"] --> AS["Aragon & Seidel 1989<br/>FOCS: treap"]
    M["McCreight 1985<br/>priority search tree"] -.-> AS
    AS --> SA["Seidel & Aragon 1996<br/>Algorithmica"]
    SA --> MR["Martinez & Roura 1998<br/>randomized BST"]
    SA --> BR["Blelloch & Reid-Miller 1998<br/>set operations via split/join"]
    BR --> BFS["Blelloch, Ferizovic & Sun 2016<br/>just join"]
    P0["Pugh 1989 WADS<br/>skip list"] --> P1["Pugh 1990 CACM"]
    P1 --> PC["Pugh cookbook 1990<br/>span, linear list ops"]
    P1 --> PMP["Papadakis, Munro & Poblete 1992<br/>Devroye 1992, Kirschenhofer & Prodinger 1994"]
    PC --> R["Redis zset<br/>span, rank"]
    P1 --> L["LevelDB / RocksDB memtable<br/>JDK ConcurrentSkipListMap"]
    SA --> F["Fischlin, Huppert & Markelon 2025<br/>adaptive adversary"]
    P1 --> F

Treap 一支。 Vuillemin 1980 年在 CACM 发表的 “A unifying look at data structures” 定义了 Cartesian tree：对二元组 \((x, y)\)，按 \(x\) 是二叉搜索树，按 \(y\) 是堆。Aragon 和 Seidel 1989 年在 FOCS 上把 \(y\) 换成随机数，得到期望对数代价的平衡树，并起名 treap（tree + heap）；期刊版 1996 年发表于 Algorithmica，给出了完整的期望分析。期刊版脚注说明，“treap” 一词此前被 McCreight 用于另一种结构，McCreight 后来把那种结构改称 priority search tree（SIAM J. Comput. 1985）。Martínez 和 Roura 1998 年在 JACM 发表的随机二叉搜索树不存优先级，而是用子树大小决定新节点以多大概率插到根，得到同样的形状分布。Blelloch 和 Reid-Miller 1998 年用 treap 的 split/join 实现集合的并、交、差并做了并行分析；Blelloch、Ferizovic 和 Sun 2016 年进一步说明，AVL、红黑树、加权平衡树和 treap 只要各自实现一个 join，其余集合操作都可以用同一套算法写出。

跳表一支。 Pugh 1989 年在 WADS 上首次发表跳表，1990 年的 CACM 版本给出了本文第七节的逆向分析和 \(p\) 的推荐值。同年修订的技术报告 A Skip List Cookbook 给每个指针附加”跨过了多少个元素”，从而支持按位置访问，Redis 有序集合的 span 字段就是这个技术。之后 Papadakis、Munro 和 Poblete（BIT 1992）给出查找代价的精确均值，Devroye（Annals of Applied Probability 1992）给出查找代价的极限分布，Kirschenhofer 和 Prodinger（Acta Informatica 1994）分析了路径长度。

对手模型一支。 两条线在 2025 年交汇：Fischlin、Huppert 和 Markelon 在 ACM CCS 2025 上研究能观察结构的自适应对手，发现只用插入就能让跳表退化成线性，而 treap 对同一类对手天然稳健（第十二节）。

三、Treap：定义、唯一性与旋转

定义

每个节点有键 \(k\) 和优先级 \(\pi\)。Treap 同时满足：

• 按键是二叉搜索树：左子树的键都小于节点的键，右子树的键都大于节点的键；
• 按优先级是大根堆：父节点的优先级大于子节点。

本文沿用 Seidel–Aragon 的大根堆约定。也有实现用小根堆，两者把优先级取负即可互换，但同一份代码里必须统一。

唯一性：形状等于”按优先级降序插入”的 BST

命题：若键两两不同、优先级两两不同，则满足上述两条的树唯一，且等于把各键按优先级从大到小依次插入普通 BST 得到的树。

证明只需归纳：堆序要求根是优先级最大的节点；BST 序要求比根小的键全在左子树、比根大的全在右子树；两棵子树各自又是 treap，由归纳假设唯一。按优先级降序插入 BST 时，第一个插入的就是优先级最大的键，它成为根，其余键按大小分到两侧，递归结构相同。

这个命题不需要任何随机性。随机性的作用在下一步：优先级独立同分布时，“按优先级降序”是 \(n\) 个键的一个均匀随机排列，所以 treap 的形状分布与”按均匀随机顺序插入 BST”完全相同，而与实际的插入顺序无关。普通 BST 最怕的升序插入，对 treap 没有影响。

实验 E0 检验这一点：\(n = 2000\)，同一组(键, 优先级)分别用”升序 + 旋转插入”和”乱序 + split/merge 插入，并夹杂额外的插入删除”两种方式建树，200 次试验中 200 次得到逐节点相同的树。

旋转

旋转是 treap 修复堆序的唯一手段。它保持中序序列不变，只改变两个节点的父子关系，需要更新子树大小的也只有这两个节点。

插入：先按 BST 挂到叶子，再往上转

新节点先按 BST 规则挂成叶子；只要它的优先级比父节点大，就把它往上旋转一次。reproduce/treap.h 中的实现（顺带计数旋转次数）：

static inline tnode *treap_insert_rot(tnode *t, tnode *x, long *rotations, int *inserted)
{
    if (!t) { *inserted = 1; return x; }
    if (x->key == t->key) { *inserted = 0; return t; }
    if (x->key < t->key) {
        t->l = treap_insert_rot(t->l, x, rotations, inserted);
        if (t->l->prio > t->prio) { t = rotate_right(t); ++*rotations; return t; }
    } else {
        t->r = treap_insert_rot(t->r, x, rotations, inserted);
        if (t->r->prio > t->prio) { t = rotate_left(t); ++*rotations; return t; }
    }
    pull(t);
    return t;
}

删除反过来：把目标节点往优先级较大的那个孩子方向旋转下去，直到它成为叶子，再摘掉。

四、Treap 的期望代价

以下设键的名次为 \(1, \ldots, n\)，记名次为 \(\ell\) 的键为 \(x_\ell\)，调和数 \(H_m = \sum_{i=1}^{m} 1/i\)。

祖先引理

引理（Seidel–Aragon 推论 4.5）：\(x_i\) 是 \(x_j\) 的祖先（含 \(i = j\)）的概率为

\[ \Pr[x_i \text{ 是 } x_j \text{ 的祖先}] = \frac{1}{|i - j| + 1}. \]

证明：考虑名次落在 \(i\) 与 \(j\) 之间（含两端）的 \(|i-j|+1\) 个键，看其中优先级最大的那个 \(y\)。按”降序插入”的视角，\(y\) 是这段键里第一个被插入的；在它之前插入的键都在这段之外，不会把这段键分开，所以这段键在 \(y\) 之前都走同一条路径，\(y\) 是它们的公共祖先。若 \(y = x_i\)，则 \(x_i\) 是 \(x_j\) 的祖先；若 \(y\) 在两者之间，\(x_i\) 和 \(x_j\) 分别落在 \(y\) 的两侧子树，互不为祖先；若 \(y = x_j\)，则反过来。优先级独立同分布，这段键中每个都以同样概率 \(1/(|i-j|+1)\) 是最大者。

期望深度

记 \(D(x_\ell)\) 为根到 \(x_\ell\) 路径上的节点数（含自身），它等于 \(x_\ell\) 的祖先个数。对 \(i\) 求和：

\[ \mathbb{E}[D(x_\ell)] = \sum_{i=1}^{n} \frac{1}{|i-\ell|+1} = H_\ell + H_{n+1-\ell} - 1 < 1 + 2\ln n. \]

这是 Seidel–Aragon 定理 4.7(i)。再对 \(\ell\) 取平均，利用 \(\sum_{\ell=1}^{n} H_\ell = (n+1)H_n - n\)：

\[ \frac{1}{n}\sum_{\ell=1}^{n} \mathbb{E}[D(x_\ell)] = 2\left(1 + \frac{1}{n}\right)H_n - 3 \approx 2\ln n. \]

实验 E1：\(n = 1000\)，键按升序插入，20000 次试验。每个名次的实测平均深度与公式的最大偏差为 0.0874；全体节点的平均深度为 11.9805，公式为 11.9859；名次 1 为 7.5132（公式 7.4855），名次 500 为 12.5453（公式 12.5876）。深度只依赖名次、中间深两端浅，这个形状在升序插入下依然成立。

高度不是 \(2\ln n\)

\(2\ln n\) 是平均深度的主项。树的高度是最深那个节点的深度，比平均值大得多。Treap 的形状与随机 BST 同分布，所以直接适用随机 BST 的结果：Devroye（JACM 1986）证明高度 \(h_n\) 满足 \(h_n / \ln n \to \alpha\)（依概率），其中 \(\alpha \approx 4.311\) 是方程 \(\alpha\ln(2e/\alpha) = 1\) 大于 2 的根；Reed（JACM 2003）进一步得到

\[ \mathbb{E}[h_n] = \alpha\ln n - \beta\ln\ln n + O(1), \qquad \beta = \frac{3}{2\ln(\alpha/2)} \approx 1.953, \]

并证明方差有界；Drmota（JACM 2003）用解析方法独立得到方差有界的结论。

实验 E3 统计高度（以节点数计）与平均深度，高度取各次试验的中位数：

三点：平均深度与公式吻合，升序和乱序没有系统差别；中位高度约为平均深度的 2 倍，比值 \(h/\log_2 n\) 从 2.2 缓慢增大，极限是 \(\alpha\ln 2 \approx 2.99\)；渐近式在这些规模下比实测中位数高 3.4 到 4.4，这就是 \(O(1)\) 项的量级。作为对比，红黑树的最坏高度是 \(2\log_2(n+1)\)，在 \(n = 10^6\) 时约为 40；treap 的典型高度（51）已经超过红黑树的最坏高度，但决定查找代价的是平均深度（约 26），而不是高度。

旋转次数期望小于 2

插入时新节点每上旋一次，它左子树的右脊或右子树的左脊就长一节；新节点作为叶子时两条脊长度都是 0。所以一次插入的旋转次数等于新节点最终位置上”左子树右脊长 \(SL\) + 右子树左脊长 \(SR\)“；删除是插入的逆过程，旋转次数相同。Seidel–Aragon 定理 4.7(iv) 给出

\[ \mathbb{E}[SL(x_\ell)] = 1 - \frac{1}{\ell}, \qquad \mathbb{E}[SR(x_\ell)] = 1 - \frac{1}{n+1-\ell}, \]

因此每次更新的期望旋转次数小于 2；若更新的名次均匀随机，平均为 \(2 - 2H_n/n\)。

实验 E2：先建 \(n\) 个键的 treap，再做 \(n\) 对”删除一个随机键、插入一个新随机键”，统计每次操作的平均旋转次数：

\(n = 1000\) 时只有 1000 次更新，0.05 的偏差在抽样误差量级；规模增大后实测收敛到公式。与红黑树相比：红黑树插入最多 2 次旋转、删除最多 3 次，是最坏界；treap 的 2 是期望，单次可以更多，但不需要颜色修复。

优先级要多”随机”

上面的分析假设优先级完全独立。Seidel–Aragon 定理 3.3 放宽了这一要求：优先级只需 8 维独立（8-wise independent），各期望界就在常数因子内保持；5 维独立即可保证查找和更新的期望对数时间。第 7 节还讨论了不存储优先级的做法：用键的哈希值当优先级（文中记为 Sleator 的建议）、用节点地址，或像 Martínez–Roura 那样改用子树大小。哈希优先级省空间，还让结构成为键集合的确定函数，但也意味着知道哈希函数的人可以构造出退化的键集合，这回到了第一节的对手模型。

五、Split 与 Merge

两个原语

• \(\mathrm{split}(T, k)\)：把 \(T\) 拆成 \(L\)（键 \(< k\)）和 \(R\)（键 \(\ge k\)）；
• \(\mathrm{merge}(L, R)\)：前提是 \(L\) 的键全小于 \(R\) 的键，合成一棵 treap。

/* *l gets keys < key, *r gets keys >= key. */
static inline void treap_split(tnode *t, int64_t key, tnode **l, tnode **r)
{
    if (!t) { *l = *r = NULL; return; }
    if (t->key < key) {
        treap_split(t->r, key, &t->r, r);
        *l = t;
    } else {
        treap_split(t->l, key, l, &t->l);
        *r = t;
    }
    pull(t);
}

/* Precondition: every key in l is smaller than every key in r. */
static inline tnode *treap_merge(tnode *l, tnode *r)
{
    if (!l) return r;
    if (!r) return l;
    if (l->prio > r->prio) {
        l->r = treap_merge(l->r, r);
        pull(l);
        return l;
    }
    r->l = treap_merge(l, r->l);
    pull(r);
    return r;
}

split 沿查找 \(k\) 的路径走一遍，路径上每个节点根据键与 \(k\) 的大小归入左边或右边，并把它另一侧的子树整棵带走。代价等于这条路径的长度，期望 \(O(\log n)\)。堆序不会被破坏：每个节点的新孩子都来自它原来的子树。

merge 每步比较两个根的优先级，大的做根，然后把另一棵与它的内侧子树递归合并。走过的是 \(L\) 的右脊和 \(R\) 的左脊，期望长度也是 \(O(\log n)\)。

用 split/merge 做插入和删除

Seidel–Aragon 期刊版把 split 描述为”插入一个键为 \(k\)、优先级为 \(+\infty\) 的节点再摘掉根”，把 join 描述为”加一个哑根再删除它”；脚注 2 又说明，实践中 split 和 join 最好写成自顶向下的迭代过程，而插入删除可以实现为”一次访问加一次 split 或 join”。本文 treap.h 的 split/merge 风格插入删除正是这样：

• 插入：沿路径下降，直到遇到优先级比新节点小的节点 \(t\)，把 \(t\) 这棵子树按新键 split，两半挂到新节点下面；
• 删除：找到目标节点，用其左右子树的 merge 替换它。

中文竞赛资料常把这种写法叫”无旋 Treap”或”FHQ Treap”。它和旋转版维护的是同一棵树（E0 已验证两种方式得到逐节点相同的结果），差别只在代码组织。另一个常被混在一起的概念是隐式键：不存键，而是用子树大小算出节点在中序里的位置，按位置 split，于是 treap 变成支持任意位置切分、拼接的序列结构（配合懒标记还能做区间翻转）。隐式键可以配旋转版，也可以配 split/merge 版，两件事互相独立。

名次与第 \(k\) 小

每个节点维护子树大小，treap_rank 沿路径累加左子树大小得到”比 \(k\) 小的键有几个”，treap_kth 按子树大小向下走找第 \(k\) 小，都是一条路径的代价。旋转、split、merge 只改路径上的节点，子树大小在回溯时由 pull 重算。

六、跳表：结构与查找路径

结构

第 1 层是全部元素的有序链表。每个元素插入时独立抽一个高度 \(h\)：

\[ \Pr[h \ge i] = p^{\,i-1}, \qquad i = 1, 2, \ldots \]

第 \(i\) 层链表由所有 \(h \ge i\) 的元素组成，所以第 \(i\) 层期望包含 \(p^{\,i-1}\) 比例的元素：第 2 层约占 \(p\)，第 3 层约占 \(p^2\)。每个元素的前向指针数就是 \(h\)，期望为

\[ \mathbb{E}[h] = \sum_{i \ge 1} p^{\,i-1} = \frac{1}{1-p}. \]

\(p = 1/2\) 时平均 2 个指针，\(p = 1/4\) 时 \(4/3\) 个。E4 实测每节点指针数与此一致（下一节表格）。

查找

从头节点的最高层开始：下一个元素的键小于目标就向右走，否则向下一层。

reproduce/skiplist.h 中 sl_find 去掉计数器后的形式：

static slnode *sl_search(const skiplist *sl, int64_t key)
{
    const slnode *x = sl->head;
    for (int i = sl->level - 1; i >= 0; i--)
        while (x->lv[i].next && x->lv[i].next->key < key)
            x = x->lv[i].next;
    slnode *n = x->lv[0].next;
    return n && n->key == key ? n : NULL;
}

图中值得注意的一点：26 在第 3 层和第 2 层都被比较了一次。比较次数和”读了多少个不同节点”不是一回事，后者才对应缓存未命中，第七节会看到这个区别影响 \(p\) 的选择。

插入与删除

查找过程中每层最后停留的节点记入 update[i]，它们就是新节点在各层的前驱。插入时抽高度 \(h\)，在第 \(1..h\) 层把新节点接在 update[i] 之后；若 \(h\) 超过当前最高层，多出的层前驱是头节点。删除时在 update[i]->next 恰为目标的各层把它摘掉，再降低空的顶层。整个过程只改 \(h\) 个前驱的指针，没有旋转，不影响其他节点；这种局部性是跳表适合做成无锁结构的原因，细节见并发跳表。

七、跳表的期望代价与 \(p\) 的选择

逆向分析

记 \(L(n) = \log_{1/p} n\)，即期望恰有 \(1/p\) 个元素的那一层。Pugh 把查找路径倒过来看：从第 1 层的终点出发，往回走到头节点最高层。在路径上的某个位置、第 \(i\) 层时，若当前节点的高度大于 \(i\)（概率 \(p\)），路径是从上面下来的，倒着走就是向上；否则（概率 \(1-p\)）是从左边过来的，倒着走就是向左。设在无限长的表中向上爬 \(k\) 层的期望步数为 \(C(k)\)：

\[ C(0) = 0, \qquad C(k) = (1-p)\bigl(1 + C(k)\bigr) + p\bigl(1 + C(k-1)\bigr) \;\Longrightarrow\; C(k) = \frac{k}{p}. \]

爬到第 \(L(n)\) 层至多 \((L(n)-1)/p\) 步。之后的左移次数不超过高度 \(\ge L(n)\) 的元素个数，期望为 \(1/p\)；从 \(L(n)\) 再往上到最高层，由 \(\Pr[\text{最高层} > k] \le n p^k\) 可得期望至多 \(1/(1-p)\) 层。合起来：

\[ \mathbb{E}[\text{查找路径长度}] \le \frac{L(n)}{p} + \frac{1}{1-p}. \]

比较次数是路径长度加 1（路径上每个位置比较一次）。主项 \(L(n)/p = \frac{1}{p\ln(1/p)}\ln n\)，系数在 \(p = 1/e\) 时最小。

Pugh 的表 1 与实测

Pugh 表 1 给出以 \(p = 1/2\) 为基准的相对查找时间（按 \(L(n)/p\) 计）和每节点指针数：

实验 E4：\(n = 10^6\)，每个键按随机顺序成功查找一次，取 5 个独立建立的跳表的中位数。“步数”是向右加向下的移动次数，即 Pugh 的路径长度；“比较”只计与真实节点的比较，不计与表尾 NIL 的比较；“不同节点”是一次查找中读过键的不同节点个数。

\(n = 65536\) 的同一组数据保存在 reproduce/results/exp.txt，结论相同。从表中可以读出：

1. 上界在所有 \(p\) 下都成立，实测步数比上界低 8% 到 13%。以 \(p = 1/2\) 为基准，\(1/e\)、\(1/4\)、\(1/8\)、\(1/16\) 的相对步数为 0.92、0.97、1.25、1.83，与 Pugh 表 1 的 0.94、1、1.33、2 趋势一致（表 1 只计主项）。
2. 不同节点数的排序与步数不同。 \(p = 1/2\) 的步数比 \(1/4\) 多，但读过的不同节点少（28.97 对 35.02）：\(p\) 越大，相邻两层停在同一个节点上的概率越高，上一层已经比较过的节点在下一层再比较一次时已经在缓存里。按缓存未命中计，\(p = 1/2\) 反而更省；按比较次数计，\(1/e\) 到 \(1/4\) 最省。Pugh 的分析和表 1 只统计后者。
3. 空间随 \(p\) 单调下降，每节点指针数与 \(1/(1-p)\) 的差不超过 0.002。

Pugh 的推荐与层数上限

Pugh 的建议是：除非运行时间的波动是首要关注（那时用 \(1/2\)），否则取 \(p = 1/4\)；理由是减小 \(p\) 会增加波动，而部分常数开销与 \(L(n)\) 而不是 \(L(n)/p\) 成正比，取 \(1/4\) 还能略微改善常数。层数上限取 \(\mathrm{MaxLevel} = L(N)\)，\(N\) 是元素个数的上界。上限低于 \(L(N)\) 不影响正确性，只是顶层链表变长：元素数超过 \((1/p)^{\mathrm{MaxLevel}}\) 之后，顶层期望有 \(n\,p^{\mathrm{MaxLevel}-1}\) 个元素，查找代价随之线性增长。第九节会用这条规则检查各实现的取值。

八、Redis 有序集合：带跨度的跳表

数据结构

Redis 7.2.5 src/server.h：

#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^64 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

\(p = 1/4\) 时 \(L(N) = 32\) 对应 \(N = 4^{32} = 2^{64}\)，注释与 Pugh 的规则一致。zset 同时持有字典和跳表：ZSCORE 这类按成员查分数的操作走字典，按分数范围和名次的操作走跳表。元素少时不用这套结构：redis.conf 中 zset-max-listpack-entries 128、zset-max-listpack-value 64，即元素不超过 128 个且每个成员不超过 64 字节时，整个有序集合编码为一块连续的 listpack（早期版本在同一位置用 ziplist）。

src/t_zset.c 开头的注释说，这份实现”几乎是 Pugh 算法的 C 语言翻译”，改了三处：允许重复的分数；比较时先比分数、分数相同再比成员字符串；第 1 层有后向指针，便于 ZREVRANGE 从尾到头遍历。

随机层数

int zslRandomLevel(void) {
    static const int threshold = ZSKIPLIST_P*RAND_MAX;
    int level = 1;
    while (random() < threshold)
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

随机源是 libc 的 random()，每层以约 \(1/4\) 的概率继续。LevelDB 的层数才用 Park–Miller 线性同余生成器（第九节）。

span：让跳表支持按名次访问

每个前向指针附带 span：从当前节点沿这个指针走到下一个节点，在第 1 层上跨过了几个元素。这是 Pugh Cookbook 第 3.4 节”线性表操作”里的 fDistance[i] = pos(forward[i]) - pos(x)。查找时沿路径累加跨过的 span，就得到目标的名次（zslGetRank，1 起算；ZRANK 返回时再减 1）；反过来按名次向下走，就是 zslGetElementByRank。

插入时，查找阶段顺带记下每层前驱 update[i] 的名次 \(r_i\)（从头节点到它的第 1 层步数）。新节点的名次是 \(r_1 + 1\)，在它占据的第 \(i \le h\) 层上：

\[ \mathrm{span}(x, i) = \mathrm{span}_{\text{old}}(\mathrm{update}_i, i) - (r_1 - r_i), \qquad \mathrm{span}(\mathrm{update}_i, i) = (r_1 - r_i) + 1, \]

在更高的层 \(i > h\) 上，update[i] 的指针从新节点上方越过，跨度加 1。删除是逆过程。reproduce/skiplist.h 按 zslInsert/zslDeleteNode 的逻辑实现了这套维护，test.c 在随机插删过程中检查”span 等于两端名次之差”。

与 treap 对比：treap 用子树大小也能在 \(O(\log n)\) 内求名次，但每个节点要多存一个大小，旋转或 split 时要重算；跳表的 span 挂在指针上，只有被修改的那几层需要调整。

antirez 的三条理由

2010 年 3 月 6 日，antirez 在 Hacker News 回答”为什么有序集合用跳表而不用平衡树”（评论 1171934），原文列了三条：

1. 内存占用不高，而且可调：调整节点层数的概率参数，可以比 B 树更省内存；
2. 有序集合常被 ZRANGE、ZREVRANGE 访问，也就是把跳表当链表遍历，这种访问的缓存局部性至少不比其他平衡树差；
3. 实现、调试更简单；例如他收到一个补丁，用增强的跳表实现了 \(O(\log N)\) 的 ZRANK，改动很小。

三条里没有并发。同一条评论后面谈线程时，他说的是 Redis 主要受 I/O 限制，用多核的长远方案是运行多个实例。第三条里的”增强跳表”就是上面的 span。

九、LevelDB、RocksDB 与 JDK 中的跳表

LevelDB。 memtable 的跳表注释写明两条约定：写操作需要外部同步，读操作不加锁；节点在跳表销毁前永不删除。后一条来自 LSM-tree 的写法：删除写的是一条墓碑记录，本身也是一次插入；memtable 写满后整体变成只读、刷盘，内存随 arena 一起释放（LSM-tree 的整体代价见上一篇）。不删除节点，无锁读者就不会读到被释放的内存。读者的正确性靠内存序保证：Next 用 acquire 读，SetNext 用 release 写，新节点先把自己的指针填好，再发布到前驱上。

层数上限 12 是否够。 \(4^{12} \approx 1.68 \times 10^7\)。LevelDB 1.23 默认 write_buffer_size 为 4 MiB，RocksDB 9.7.4 默认 64 MiB；每个条目除了键值之外还要存序列号和至少一个指针，所以默认配置下一个 memtable 的条目数远达不到 \(1.68 \times 10^7\)，上限不会起作用。把 write buffer 调得很大并且写入极小的键值时，才会越过这个规模，代价按第七节末尾所说线性增长。

RocksDB。 InlineSkipList 把键直接存在节点内存里，省掉一个指向键的指针；默认的 memtable_factory 是 SkipListFactory，allow_concurrent_memtable_write 默认开启，而且只有 SkipListFactory 支持它。多写者并发插入用 CAS 完成，详见并发跳表。

JDK。 ConcurrentSkipListMap 自 1.6 起提供。doPut 里新节点先以 \(1/4\) 的概率获得索引（(lr & 0x3) == 0），之后每多一层取决于 64 位随机数的最高位，概率 \(1/2\)；源码注释是 “create at most 62 indices”。所以它的层数分布与 Pugh 的几何分布不同：\(\Pr[\text{至少 } k \text{ 层索引}] = \frac14 \cdot (\frac12)^{k-1}\)。删除时先在节点后插入标记节点，再摘除，这套协议属于并发跳表的内容。

四个实现都取 \(p = 1/4\) 或以 \(1/4\) 起步，与 Pugh 的推荐一致。Pugh 还讨论过”修正骰子”：抽到的高度比当前最高层高出不止 1 时，截成最高层加 1。Redis 和 LevelDB 没有这样做，抽到的高度只受固定上限约束；JDK 每次插入最多给头节点加一层，效果与修正骰子类似。

十、实测：访问次数与绑核计时

环境与口径

• CPU：Intel Core i9-12900K（24 个逻辑 CPU，L2 共 15 MiB，L3 30 MiB）；WSL2，内核 6.6.87.2-microsoft-standard-WSL2；GCC 16.1.1。完整信息在 reproduce/results/env.txt。
• 编译运行（run.sh 会依次执行）：

cd reproduce
gcc -O2 -Wall -Wextra -o test test.c && ./test
gcc -O1 -g -fsanitize=address,undefined -fno-sanitize-recover=all -o test_san test.c && ./test_san
gcc -O2 -Wall -Wextra -o exp exp.c -lm && taskset -c 3 ./exp results
gcc -O2 -Wall -Wextra -o bench bench.c
for s in treap-rot treap-sm skip-1/2 skip-1/4; do taskset -c 3 ./bench $s 1000000 1; done
python3 plot_results.py

• 对拍：test.c 把两种 treap、多组参数的跳表（\(p = 1/2, 1/4, 1/16\)，层数上限 3 和 32）与排序数组对拍，含 INT64_MIN、INT64_MAX 等极端键，随机插删过程中检查 BST 序、堆序、子树大小、span 与层结构；-O2 版本和 ASan/UBSan 版本都输出 all tests passed。
• 计数实验 E0 到 E6 与时钟无关，随机数由固定种子的 xoshiro256** 生成，两次完整运行的输出逐字节一致。
• 计时：机器上同时有其他任务，因此绑定到 CPU 3；每种结构在 \(n = 10^6\) 下用种子 1 到 5 各跑一次，取中位数。计时只看相对趋势。

读了多少个不同节点

实验 E5：\(n = 10^6\)，每次成功查找平均读过的不同节点数（5 次中位数）为 treap 25.78、跳表 \(p = 1/2\) 28.04、\(p = 1/4\) 34.62，\(\log_2 n = 19.93\)。Treap 的值就是平均深度（与第四节 E3 的 25.8 一致）。E5 与 E4 用的是不同的随机表，\(p = 1/2\) 的 28.04 与 E4 的 28.97 之差是表与表之间的波动。按”每次查找碰到多少个可能不在缓存里的节点”计，treap 最少，\(p = 1/4\) 的跳表最多。

计时

单位为 ns/次，5 次中位数，绑定 CPU 3。键为 \(0..n-1\) 的随机排列，先全部插入，再按新的随机顺序各成功查找一次，再按随机顺序全部删除；两种结构的查找都带计数器。

原始数据在 reproduce/results/bench.txt。同一结构 5 次之间的差距可达 20%（旋转版 treap 插入从 732.5 到 883.2 ns），所以插入和删除列的差别都不足以排序；稳定的只有查找列：两种 treap 约 490 到 500 ns，跳表 \(p = 1/2\) 约 720 ns，\(p = 1/4\) 约 850 ns，5 次里每一次都是这个顺序。

查找的差距（\(p = 1/2\) 比 treap 慢约 46%）比不同节点数的差距（约 9%）大得多，只用”缓存未命中次数”解释不了。可能的因素包括跳表每次查找多出约 13 次比较（38.5 对 25.8），每次比较都是难以预测的分支；以及跳表节点大小不一、高层指针可能落在另一条缓存行。本文没有用硬件性能计数器测量，这里只能列为假设。

对手看得见层数时

实验 E6 复现 Pugh 的警告：\(p = 1/4\)、\(n = 10^5\) 的跳表，平均查找路径 33.9 步；删掉全部 25197 个高度大于 1 的节点后，剩下 \(n' = 74803\) 个节点全在第 1 层，平均查找路径 37401 步，恰为单链表的 \((n'-1)/2\)。删除的都是合法操作，只是删除的选择依赖了层数。

十一、选型与陷阱

几个容易出错的地方：

• 优先级位数。 唯一性要求优先级互不相同。\(n\) 个独立均匀的 \(b\) 位优先级中出现相同值的期望对数约为 \(n^2/2^{b+1}\)：\(b = 64\)、\(n = 10^6\) 时约 \(2.7 \times 10^{-8}\)，可以忽略；\(b = 32\) 时约 116 对。相同的优先级不会破坏正确性，但会让形状分布偏离随机 BST。
• 按 \(k\) 和 \(k+1\) 两次 split 来删除。 这种写法在 \(k\) 取整数类型最大值时溢出（有符号整数溢出在 C 里是未定义行为）。按键下降、用两棵子树的 merge 替换目标节点（treap_erase_sm）没有这个问题。
• 层数上限低于 \(L(N)\)。 不影响正确性，但规模越过 \((1/p)^{\mathrm{MaxLevel}}\) 后查找退化为线性增长（第七节）。
• 暴露随机状态。 把节点层数、优先级或可预测的随机数种子暴露给不可信的调用者，等于撤掉了期望界的前提（E6）。用键的哈希当优先级时，哈希函数同样不能让对手知道。
• 递归深度。 本文的 split/merge 是递归写法，深度等于树高，\(n = 10^6\) 时约 50；若优先级生成出错（例如所有节点拿到同一个值），树退化成链，递归会栈溢出。Seidel–Aragon 建议的迭代写法没有这个问题。

十二、争论与开放问题

跳表比平衡树快吗

Pugh 的摘要写的是跳表的插入和删除算法”much simpler and significantly faster than equivalent algorithms for balanced trees”；引言说简单带来”significant constant factor speed improvements”。他在 Sun-3/60 上用 \(2^{16}\) 个整数键测的表 2 支持插入删除更快的说法（跳表 0.065 与 0.059 ms，非递归 AVL 0.10 与 0.085 ms），但查找是 AVL 更快（0.046 对 0.051 ms）；键换成实数后，他报告跳表比 AVL 略慢。

之后的证据各有侧重。Wang 等人在 SIGMOD 2018 比较内存索引时，他们测试的无锁跳表（带后台线程建索引塔的 “No Hot Spot” 变体）在多线程下性能最差，原因是后台线程建塔跟不上插入。antirez 的理由（第八节）只说范围遍历的局部性”至少不差”。本文的单线程测量里，treap 查找比跳表快，插入删除分不出高下；按读过的不同节点计，treap 也更少。这些数据来自不同的年代、硬件和实现，都不足以支持”跳表更快”或”平衡树更快”的一般结论。本文的看法是：跳表今天的主要优势不在单线程速度，而在插入只做局部修改，因此容易做成无锁并发，以及 span 这类增强实现起来简单。

对手看得见随机性时

Pugh 把”对手看不到层数”作为假设直接写进论文，但在服务端数据结构里，对手往往能通过响应时间推测内部结构。Bethea 和 Reiter（ESORICS 2009）以”耗时不可预测的数据结构”为题研究这一问题；Nussbaum 和 Segal（DPM 2019）专门分析了跳表的计时攻击。Fischlin、Huppert 和 Markelon（CCS 2025，ePrint 2025/1611）形式化了能观察结构的自适应对手，提出只靠插入就能把跳表退化成线性时间的 “gap attack”；他们同时发现 treap 在这一模型下天然稳健，并给出修改删除机制后可证明稳健的构造。

第十节的 E6 既要求对手知道层数，又需要删除操作；按 Fischlin 等人的结果，能观察结构的对手只做插入也足以让跳表退化。两种结构在这一模型下表现不同，说明”期望对数”这个共同的结论掩盖了它们对对手信息的不同敏感度。第九节的四个生产实现都使用普通的随机层数，没有采用这些稳健构造。

开放问题

• 有限独立性与实际生成器之间的空白。 Seidel–Aragon 定理 3.3 在 8 维独立的优先级下给出界，而生产代码用的是 libc random()、Park–Miller、ThreadLocalRandom 这类生成器，它们不属于定理要求的 \(k\) 维独立族，论文的界不能直接套用。本文的实验只使用 xoshiro256**，没有覆盖这些生成器。
• 稳健构造的代价。 Fischlin 等人的构造在渐近意义上保持对数期望，但在真实工作负载下的常数开销、与并发实现能否兼容，还没有看到生产系统层面的评估。
• 查找耗时的构成。 第十节中跳表查找比 treap 慢的幅度远大于读过的节点数之差，分支预测和缓存行布局各占多少，需要用硬件计数器测量才能回答；换一台机器或一种内存分配器，结论也可能不同。

十三、参考资料

规范与文档

• Redis 7.2.5，redis.conf：zset-max-listpack-entries 128、zset-max-listpack-value 64。
• Java SE 21 API，java.util.concurrent.ConcurrentSkipListMap（@since 1.6）。

源码

• Redis 7.2.5：src/server.h（ZSKIPLIST_MAXLEVEL、ZSKIPLIST_P、zskiplistNode、zset），src/t_zset.c（文件头注释、zslRandomLevel、zslInsert、zslDeleteNode、zslGetRank、zsetRank）。
• LevelDB 1.23：db/skiplist.h（kMaxHeight、RandomHeight、线程安全约定），util/random.h，include/leveldb/options.h（write_buffer_size）。
• RocksDB v9.7.4：memtable/inlineskiplist.h（max_height、branching_factor、kMaxPossibleHeight、InsertConcurrently），memtable/skiplistrep.cc，include/rocksdb/advanced_options.h（memtable_factory），include/rocksdb/options.h（write_buffer_size、allow_concurrent_memtable_write）。
• OpenJDK jdk-21-ga：src/java.base/share/classes/java/util/concurrent/ConcurrentSkipListMap.java（doPut）。

核心论文

• C. R. Aragon, R. G. Seidel, “Randomized search trees”, FOCS 1989, pp. 540–545, doi:10.1109/SFCS.1989.63531.
• R. Seidel, C. R. Aragon, “Randomized search trees”, Algorithmica 16(4–5):464–497, 1996, doi:10.1007/BF01940876.
• W. Pugh, “Skip lists: a probabilistic alternative to balanced trees”, Communications of the ACM 33(6):668–676, 1990, doi:10.1145/78973.78977.
• W. Pugh, “Skip lists: a probabilistic alternative to balanced trees”, WADS 1989, LNCS 382, pp. 437–449, doi:10.1007/3-540-51542-9_36.
• W. Pugh, “A Skip List Cookbook”, University of Maryland, UMIACS-TR-89-72.1 / CS-TR-2286.1, 1989（1990 年修订）。
• J. Vuillemin, “A unifying look at data structures”, Communications of the ACM 23(4):229–239, 1980, doi:10.1145/358841.358852.

其他论文

• E. M. McCreight, “Priority search trees”, SIAM Journal on Computing 14(2):257–276, 1985.
• C. Martínez, S. Roura, “Randomized binary search trees”, Journal of the ACM 45(2):288–323, 1998.
• G. E. Blelloch, M. Reid-Miller, “Fast set operations using treaps”, SPAA 1998, pp. 16–26, doi:10.1145/277651.277660.
• G. E. Blelloch, D. Ferizovic, Y. Sun, “Just join for parallel ordered sets”, SPAA 2016, pp. 253–264.
• L. Devroye, “A note on the height of binary search trees”, Journal of the ACM 33(3):489–498, 1986.
• B. Reed, “The height of a random binary search tree”, Journal of the ACM 50(3):306–332, 2003.
• M. Drmota, “An analytic approach to the height of binary search trees II”, Journal of the ACM 50(3):333–374, 2003.
• T. Papadakis, J. I. Munro, P. V. Poblete, “Average search and update costs in skip lists”, BIT 32(2):316–332, 1992.
• L. Devroye, “A limit theory for random skip lists”, Annals of Applied Probability 2(3), 1992.
• P. Kirschenhofer, H. Prodinger, “The path length of random skip lists”, Acta Informatica 31(8):775–792, 1994.
• Z. Wang, A. Pavlo, H. Lim, V. Leis, H. Zhang, M. Kaminsky, D. G. Andersen, “Building a Bw-Tree takes more than just buzz words”, SIGMOD 2018, pp. 473–488.
• D. Bethea, M. K. Reiter, “Data structures with unpredictable timing”, ESORICS 2009, LNCS 5789, pp. 456–471.
• E. Nussbaum, M. Segal, “Skiplist timing attack vulnerability”, DPM 2019, LNCS, pp. 49–58.
• M. Fischlin, M. Huppert, S. Markelon, “Probabilistic skipping-based data structures with robust efficiency guarantees”, ACM CCS 2025, pp. 1127–1141, doi:10.1145/3719027.3765149；ePrint 2025/1611。

工程资料

• S. Sanfilippo（antirez），Hacker News 评论 1171934，2010-03-06，回答 Redis 有序集合为何用跳表。

实验

• reproduce/treap.h、reproduce/skiplist.h、reproduce/rng.h：本文全部结构的实现与随机数生成器。
• reproduce/test.c：与排序数组对拍，含 ASan/UBSan 构建。
• reproduce/exp.c：E0 到 E6 计数实验，输出 results/exp.txt、results/depth_by_rank.csv、results/skiplist_p.csv。
• reproduce/bench.c：第十节计时，结果在 results/bench.txt、results/bench_summary.txt，环境在 results/env.txt。
• reproduce/draw_figures.py：生成六张示意图，并断言图中的旋转、切分路径、查找路径与名次数值；reproduce/plot_results.py：由实验结果生成两张数据图。
• reproduce/run.sh：依次执行以上全部步骤。

系列导航： - 上一篇：B+tree 与 LSM-tree：原地更新与异地更新的读、写、空间代价 - 下一篇：线段树与树状数组：前缀分解、懒标记与自底向上实现

相关阅读： - 红黑树与 AVL：旋转次数、树高与 Linux 内核的选择 - 并发跳表：ConcurrentSkipListMap 的设计 - 持久化数据结构：路径复制、节点复制与宽分支 trie - 随机化算法：当运气成为武器