跳表：用概率分层实现 O(log n) 有序索引

跳表用概率随机化替代传统平衡树的严格旋转，实现了 O(log n) 期望复杂度的有序集合。Redis ZSet、LevelDB、RocksDB 均使用跳表作为核心数据结构。

目录

核心思想

问题：有序链表查找是 O(n)，如何加速？

思路：建多级"快速通道"——

查找 17：

1. 第2层：1 → 9（跳过 1,3,4,6），9 < 17，继续
2. 第2层：9 → 25（25 > 17），下降到第1层
3. 第1层：9 → 17，找到！

概率随机化：每个节点插入时，以概率 p（通常 0.5）晋升到上一层。期望层高 = 1/(1-p) = 2（p=0.5 时），最高层数 log_{1/p}(n)。

结构与原理

随机层高：每层晋升概率 p = 0.5

int randomLevel() {
    int lvl = 1;
    while (random.nextDouble() < 0.5 && lvl < MAX_LEVEL) lvl++;
    return lvl;
}

期望分布：

• 层高 1 的节点：50%
• 层高 2 的节点：25%
• 层高 3 的节点：12.5%
• ...

核心操作

查找

从最高层开始，每层向右走直到 next > target，然后下降：

search(target):
  cur = head
  for i = maxLevel-1 downto 0:
    while cur.next[i] != null && cur.next[i].val < target:
      cur = cur.next[i]     // 在第 i 层向右移动
  cur = cur.next[0]         // 降到第0层后检查
  return cur != null && cur.val == target

插入

1. 查找阶段记录每层的"前驱节点" update[]
2. 随机生成新节点层高
3. 更新各层指针

insert(val):
  update[0..MAX_LEVEL] = 记录每层需要更新 next 的前驱节点
  newLevel = randomLevel()
  newNode = Node(val, newLevel)
  for i = 0 to newLevel-1:
    newNode.next[i] = update[i].next[i]
    update[i].next[i] = newNode

删除

同样需要先找 update[]，然后摘除各层指针：

delete(val):
  update[] = 同上
  target = update[0].next[0]
  if target == null || target.val != val: return false
  for i = 0 to level-1:
    if update[i].next[i] != target: break
    update[i].next[i] = target.next[i]
  return true

Java 实现

import java.util.Random;

/**
 * 跳表：支持有序集合的 add / delete / search，期望 O(log n)
 */
public class SkipList {
    private static final int MAX_LEVEL = 16;
    private static final double P = 0.5;

    private final Node head;
    private int level; // 当前最大有效层数
    private final Random random;

    static class Node {
        int val;
        Node[] next;
        Node(int val, int level) {
            this.val = val;
            this.next = new Node[level];
        }
    }

    public SkipList() {
        head = new Node(Integer.MIN_VALUE, MAX_LEVEL);
        level = 1;
        random = new Random(42);
    }

    private int randomLevel() {
        int lvl = 1;
        while (random.nextDouble() < P && lvl < MAX_LEVEL) lvl++;
        return lvl;
    }

    public boolean search(int target) {
        Node cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < target)
                cur = cur.next[i];
        }
        cur = cur.next[0];
        return cur != null && cur.val == target;
    }

    public void insert(int val) {
        Node[] update = new Node[MAX_LEVEL];
        Node cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < val)
                cur = cur.next[i];
            update[i] = cur;
        }
        // 已存在则不重复插入
        if (cur.next[0] != null && cur.next[0].val == val) return;

        int newLevel = randomLevel();
        if (newLevel > level) {
            for (int i = level; i < newLevel; i++) update[i] = head;
            level = newLevel;
        }
        Node newNode = new Node(val, newLevel);
        for (int i = 0; i < newLevel; i++) {
            newNode.next[i] = update[i].next[i];
            update[i].next[i] = newNode;
        }
    }

    public boolean delete(int val) {
        Node[] update = new Node[MAX_LEVEL];
        Node cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < val)
                cur = cur.next[i];
            update[i] = cur;
        }
        Node target = cur.next[0];
        if (target == null || target.val != val) return false;

        for (int i = 0; i < level; i++) {
            if (update[i].next[i] != target) break;
            update[i].next[i] = target.next[i];
        }
        while (level > 1 && head.next[level - 1] == null) level--;
        return true;
    }
}

验证结果（插入 10 个元素，查找、删除、重复插入、1000 元素有序插入）：全部测试通过 ✓

复杂度分析

为什么是期望 O(log n)：层高由随机化控制，期望第 k 层节点数为 n/2^k，查找时每层期望移动 1/p = 2 步，总层数约 log_{1/p}(n)，故总步数期望为 2 * log₂n。

与确定性平衡树的区别：跳表无旋转操作，实现简单；代价是最坏情况概率性地变差（实践中极少发生）。

对比与选型

Redis 选择跳表而非红黑树的原因：

1. 实现更简单，易于调试
2. 范围查询（ZRANGEBYSCORE）效率相同
3. 并发场景下锁粒度更细

参考资料

• Skip Lists: A Probabilistic Alternative to Balanced Trees (Pugh, 1990)
• Redis ZSet 源码：t_zset.c，跳表实现：server.h 中 zskiplist 结构