skip-list · 多层索引

跳表：有序链表叠快速通道

有序链表的查找只能从头逐个走，即使元素有序也得 $O(n)$ ——链表没有数组那样的随机访问。skip list 在这条完整链 (level 0) 之上，叠几层稀疏索引 (express lanes)：每层只收录一部分节点，层越高越稀疏，一步跨过的距离越大。查找从最高层最左的 head 出发，「能跨就向右跨、跨过头就下沉一层」，路径像一段楼梯，平均比较次数降到 $O(\log n)$ 。它用概率性层高替代平衡树的旋转，实现简单、无需再平衡，Redis ZSet、LevelDB 的 memtable 都用它。

**为什么平均是 $O(\log n)$ ?**层高来自抛硬币（几何分布）：一个节点先必然出现在 level 0，然后每次以 1/2 概率再升一层。于是约一半节点只到 level 0、约 1/4 升到 level 1、1/8 到 level 2……总层数期望 $O(\log n)$ 。而在每一层里，查找指针向右跨的步数期望是 $O(1)$ （跨多了就会被上一层提前拦下下沉），于是「层数 × 每层步数」= $O(\log n) \times O(1) = O(\log n)$ 。

插入与删除：都先跑一遍 search 攒下 update[]。插入分三步：其一，先按 search 找到插入位，沿途在每一层记下「将成为新节点左邻」的那个节点，存进 update[lv]；其二，抛硬币定新节点层高 h（几何分布，以 1/2 概率逐层升高）,层高决定它出现在哪几层——只在 level 0..h 露面；其三，在这些层逐层就地接线 new.next[lv] = update[lv].next[lv]; update[lv].next[lv] = new。删除是插入的逆：同样先 search 攒 update[] 定位目标，再逐层把指向目标的指针改接到目标的后继 update[lv].next[lv] = target.next[lv]，目标在它存在的每一层一并消失。两者都只动查找路径上的局部指针，无旋转、无全局回溯。

对比平衡树：用随机性换掉旋转。红黑树 / AVL 靠插入删除后的旋转维持平衡，代码繁琐、边界多。skip list 不维护任何全局不变量，层高纯随机决定，插入只需在查找路径上「就地接线」——实现显著简单，且因为改动局部、无需自底向上回溯旋转，更易于并发（无锁 / 细粒度锁实现成熟）。代价是期望意义上的平衡，最坏仍可能退化，但概率极低。Redis 的 ZSet（有序集合）与 LevelDB / RocksDB 的 memtable 都选了它。

express lane 必须建在有序链上。跳表的前提是 level 0 这条完整链按值有序——高层索引只是「抽样的路标」，靠「 $next.val \le target$ 就跨」来决定方向。若底层无序，高层索引便失去意义。这和单向 / 双向链表的「按值查找仍是 $O(n)$ 」形成对照：那里链表本就不要求有序，而 skip list 是专为有序查找改造的链表。