硬核揭秘 Redis 有序集合：为什么跳表比红黑树更香？

洛水晗

723人浏览 · 2026-04-12 20:16:04

洛水晗 · 2026-04-12 20:16:04 发布

一、什么是跳表（Skip List）？

跳表（Skip List）是一种多层级的有序链表，如下图所示：

层级3:  HEAD ───────────────────────────────► ∞
层级2:  HEAD ──────────────► 16 ────────────► ∞
层级1:  HEAD ──► 8 ────────► 16 ────────────► ∞
层级0:  HEAD ──► 8 ──► 12 ─► 16 ─► 20 ──────► ∞

多个层级：每层都是有序链表
逐层向下：高层是低层的"快速通道"
目标：把时间复杂度从 O(n) → O(log₂n)，实现二分查找

二、为什么需要层级？

对于单层有序链表，搜索需要挨个遍历，时间复杂度 O(n)：

链表: 3 → 7 → 12 → 15 → 23 → 31 → 45
查找12: 3→7→12  (遍历3次)
查找45: 3→7→12→15→23→31→45  (遍历7次)

加层级的目的：实现类似二分查找的效果

层级1（快速通道）: 3 ──────────────► 23 ──────────► ∞
层级0（底层链表）: 3 → 7 → 12 → 15 → 23 → 31 → 45

查找12: 层级1: 3→23 (超过12) → 下沉
        层级0: 7→12 ✓  (只遍历2次！)

🔑 核心思想：每比较一次，排除一半节点。层级越高，跳跃跨度越大。

三、插入操作：为什么要随机层级？

理想跳表

如果每次插入都重新构建理想跳表（每层概率 1/2）：

每层节点数 = 底层节点数 × (1/2^层级)

理想状态下，每层都像二分查找一样均匀分布

问题：增删会破坏结构

理想跳表在插入/删除后需要重构，代价太大！

解决方案：随机层级

import random

def random_level(max_level: int = 16) -> int:
    """随机生成层级，概率逐层减半"""
    level = 0
    while random.random() < 0.5 and level < max_level:
        level += 1
    return level

为什么是 0.5 的概率？

每升高一层，节点数量减半
这正是二分查找的核心思想
层级越高，节点越稀疏，跳跃越远

插入过程图解

原始跳表:
L2: HEAD ──────────► 30 ──────────────────► ∞
L1: HEAD ───► 10 ───► 30 ────────────────► ∞
L0: HEAD ──► 5 ─► 10 ─► 20 ─► 30 ─► 40 ─► ∞

要插入 25，随机层级=2:

Step 1: L2  30 > 25，向前 ──────────────────► 发现要插入位置
Step 2: L1  30 > 25，向前 ───► 10 ──► 插入点
Step 3: L0  20 < 25 < 30，插入到 20 和 30 之间

插入后:
L2: HEAD ──────────► 30 ──────────────────► ∞
L1: HEAD ───► 10 ───► 25 ─► 30 ──────────► ∞
L0: HEAD ──► 5 ─► 10 ─► 20 ─► 25 ─► 30 ─► 40 ─► ∞

四、时间复杂度分析

跳表搜索次数

节点数 n	层级数	最坏搜索次数	复杂度
2	1	2	O(log₂n)
4	2	3	O(log₂n)
8	3	4	O(log₂n)
16	4	5	O(log₂n)
n	log₂n	log₂n	O(log₂n)

⚡ 数据量 ≥ 256 时，跳表结构趋于稳定，实际表现非常接近 O(log₂n)

各操作复杂度

操作	时间复杂度	说明
搜索	O(log₂n)	逐层向下，每层排除一半
插入	O(log₂n)	搜索 + 建立层级指针
删除	O(log₂n)	搜索 + 调整前后指针

五、灵魂拷问：Redis 为什么用跳表而不是红黑树？

5.1 跳表的层式结构通病：空间浪费

跳表: 需要为每个节点分配随机层级
      大量节点 → 多层级指针 → 空间开销

红黑树: 每个节点只有左右父3个指针，无层级限制

但 Redis 选择了跳表，为什么？

5.2 跳表只有在大数据量时才能发挥 O(log₂n) 优势

数据量小：跳表和红黑树性能差异不大
数据量大（>256节点）：跳表时间复杂度稳定趋于 O(log₂n)

5.3 关键原因：范围查找（Range Query）

这是最核心的差异！

红黑树做范围查找：

红黑树结构:
        30
       /  \
     20    40
    /  \   /  \
   10  25 35  50

找 20~40 范围:
20 ✓ → 25 ✓ → 回溯到20 → 向上找30 ✓ → 35 ✓ → 40 ✓
      ↑_________________|
       经历多次无用的回溯！

跳表做范围查找：

跳表:
L1: HEAD ───► 20 ─────────────────► 40 ─► ∞
L0: HEAD ──► 10 ─► 20 ─► 25 ─► 30 ─► 35 ─► 40 ─► 50

找 20~40 范围:
从 L1 找到 20 → 直接沿 L0 顺序取出 20, 25, 30, 35, 40
一气呵成，无回溯！

🔑 跳表最底层（L0）包含所有节点，天然支持范围遍历

六、为什么不用 B+树？

B+树特性

B+树结构（多路平衡搜索树）:
         [ 20 | 40 ]
        /    |    \
    [10|15] [25|30] [45|50]

- 所有数据在叶子节点
- 叶子节点用链表连接
- 高度远低于红黑树（多路）

为什么数据库用 B+树而不是跳表？

对比	B+树	跳表/红黑树
存储介质	磁盘	内存
时间复杂度	O(log₂n) 底数更大	O(log₂n) 底数更小
磁盘 IO	少（高度低）	多
范围查找	叶子链表	都可以
空间利用率	高（每页填满）	低（跳表有层级浪费）

核心原因：

树高度决定磁盘 IO 次数 — B+树多路特性使高度更低，磁盘 IO 更少
数据库主要操作磁盘 — 磁盘 IO 是瓶颈，必须用 B+树
跳表适合内存 — Redis 数据在内存，不需要考虑磁盘 IO

总结

┌─────────────────────────────────────────────┐
│           数据结构选择决策树                  │
├─────────────────────────────────────────────┤
│                                             │
│   数据存储在哪？                             │
│       │                                     │
│   ┌───┴───┐                                 │
│   ▼       ▼                                 │
│  磁盘    内存                                │
│   │       │                                 │
│   ▼       ▼                                 │
│ B+树   数据结构？                            │
│         │                                   │
│     ┌───┴───┐                               │
│     ▼       ▼                               │
│   范围查询? : 纯点查询                       │
│     │                                         │
│     ▼                                         │
│   跳表（范围遍历无敌）                        │
│                                             │
└─────────────────────────────────────────────┘

七、总结

数据结构	适用场景	原因
跳表	Redis ZSet（内存+范围查询）	O(log₂n)，范围遍历无回溯，空间换时间
红黑树	TreeMap（内存+点查询）	内存友好，无层级浪费，不支持范围遍历
B+树	MySQL/磁盘数据库	磁盘IO少，多路平衡，高度低