跳表数据结构

跳表（Skip List）是一种支持高效插入、删除和查找的链表结构，用于加速查找操作，特别适用于有序数据集合。它在Redis、LevelDB等系统中被用于**有序集合（Sorted Set）**的实现。

1. 跳表的结构

跳表的核心思想是：
在链表的基础上，引入多级索引，类似于高速公路的匝道，提高查找效率。

一个跳表通常由多层索引构成：

• 最底层（Level 0） 是一个有序单链表，存储所有数据；
• 上层索引（Level > 0） 由部分节点构成，起到“跳跃”的作用，加速查找；
• 最上层索引 由少量节点构成，使得查找可以迅速缩小范围。

示例跳表（3 层）：

Level 2:    1 --------------> 9 ----------------> 19
Level 1:    1 ----> 5 -----> 9 ----> 13 -------> 19
Level 0:    1 -> 3 -> 5 -> 7 -> 9 -> 11 -> 13 -> 15 -> 17 -> 19

每一层都是上一层的子集，节点的“晋升”是概率性的（通常是 1/2）。

2. 跳表的基本操作

查找

跳表的查找过程类似于二分查找：

1. 从最高层索引开始，查找小于目标值的最大节点；
2. 向下移动到下一层索引，继续查找；
3. 直到底层（Level 0），最终在普通链表中找到目标节点或确认其不存在。

时间复杂度：
$$O(\log n)$$ —— 因为跳表的高度是O(log n)，查找路径长度也大约是O(log n)。

插入

1. 查找插入位置，找到前驱节点；
2. 随机决定新节点的层数（常见做法：掷硬币，每次有 50% 概率提升一层）；
3. 在每一层进行插入，更新索引。

时间复杂度：

• 平均 O(log n)，因为最多遍历 log n 层；
• 最坏 O(n)（所有元素都在同一层）。

删除

1. 查找目标节点（与查找操作类似）；
2. 在每一层移除节点；
3. 如果某层为空，则删除该层。

时间复杂度：
$$O(\log n)$$

3. 跳表 vs. 其他数据结构

跳表 vs. 红黑树

• 跳表实现更简单，只需维护索引，而红黑树需要复杂的旋转操作；
• 跳表在分布式环境中更友好，如 Redis 的有序集合（ZSet）采用跳表；
• 红黑树适用于内存受限的场景，因为跳表的索引层需要额外存储空间。

4. 实际应用

Redis

Redis 有序集合（Sorted Set） 的底层结构是 跳表 + 哈希表：

• 跳表：用于范围查询（ZRANGE、ZREVRANGE）
• 哈希表：用于O(1) 查找（ZADD）

LevelDB

Google 的 LevelDB 用跳表存储MemTable，然后刷盘成 SSTable。

5. 代码实现（Java）

跳表节点

class SkipListNode {
    int val;
    SkipListNode[] next; // 指向不同层级的下一个节点

    public SkipListNode(int val, int level) {
        this.val = val;
        this.next = new SkipListNode[level];
    }
}

跳表类

import java.util.Random;

class SkipList {
    private static final int MAX_LEVEL = 16;  // 最大层数
    private final SkipListNode head; // 头节点
    private int levelCount = 1; // 当前最大层数
    private final Random random = new Random();

    public SkipList() {
        head = new SkipListNode(-1, MAX_LEVEL); // 初始化头节点
    }

    // 查找
    public boolean search(int target) {
        SkipListNode cur = head;
        for (int i = levelCount - 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 num) {
        SkipListNode[] update = new SkipListNode[MAX_LEVEL]; // 记录每层的前驱节点
        SkipListNode cur = head;

        for (int i = levelCount - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < num) {
                cur = cur.next[i];
            }
            update[i] = cur;  // 记录前驱节点
        }

        int newLevel = randomLevel();
        levelCount = Math.max(levelCount, newLevel);
        SkipListNode newNode = new SkipListNode(num, newLevel);

        for (int i = 0; i < newLevel; i++) {
            newNode.next[i] = update[i].next[i];
            update[i].next[i] = newNode;
        }
    }

    // 删除
    public void delete(int num) {
        SkipListNode cur = head;
        SkipListNode[] update = new SkipListNode[MAX_LEVEL];

        for (int i = levelCount - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < num) {
                cur = cur.next[i];
            }
            update[i] = cur;
        }

        SkipListNode target = cur.next[0];
        if (target == null || target.val != num) return;

        for (int i = 0; i < levelCount; i++) {
            if (update[i].next[i] != target) break;
            update[i].next[i] = target.next[i];
        }
    }

    // 随机生成层数
    private int randomLevel() {
        int level = 1;
        while (random.nextDouble() < 0.5 && level < MAX_LEVEL) {
            level++;
        }
        return level;
    }
}

6. 总结

• 跳表通过多层索引加速查询，时间复杂度接近O(log n)；
• 插入/删除时动态调整索引，比红黑树实现简单；
• Redis、LevelDB 等系统采用跳表，适用于有序集合、范围查询等场景；
• 比红黑树占用更多空间，但更适合并发和分布式环境。