ZSet 底层跳表原理

面试官问："Redis ZSet 的底层结构是什么？"

小刘说："跳表和哈希表。"

面试官追问："跳表是怎么实现的？为什么不用红黑树？"

小刘说："...跳表更快？"

面试官继续追问："跳表每一层是怎么决定跳多远的？"

小刘彻底卡住了。

跳表是 Redis 面试中的高频深水区题。这道题能说清楚"跳表 vs 红黑树"和"为什么跳表用随机层级"的候选人，对数据结构有较深的理解。

一、跳表的数据结构 🔴

1.1 跳表 vs 链表

// 普通链表：O(n) 查找
1 → 5 → 8 → 12 → 20 → NULL
查 12：1→5→8→12，需要遍历 4 次

// 跳表：O(log n) 查找
Level 2:  1 ────────────────────→ 20 ─→ NULL
Level 1:  1 ─────→ 8 ───────────→ 20 ─→ NULL
Level 0:  1 → 5 → 8 → 12 → 16 → 20 ─→ NULL
查 12：
1. Level 2: 1 → 20（跳过）
2. Level 1: 8 → 20（跳过）
3. Level 0: 8 → 12（命中）
总共 5 次比较 vs 链表的 4 次，但跳表层数越多，搜索越快

1.2 跳表节点结构

// 跳表节点
typedef struct zskiplistNode {
    robj *ele;           // member（SDS 字符串）
    double score;        // 分值
    struct zskiplistNode *backward;  // 前向指针（用于逆序遍历）
    struct zskiplistLevel {
        struct zskiplistNode *forward;  // 指向下一节点的指针
        unsigned int span;               // 到下一节点的跨度（用于排名）
    } level[];
} zskiplistNode;

// 跳表
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;  // 头尾指针
    unsigned long length;                  // 节点数量
    int level;                             // 最大层数
} zskiplist;

1.3 跳表图示

跳表结构：
┌─────────────────────────────────────────────────────────┐
│ header                                                    │
│ Level 3:  [+∞] ─────────────────────────────────→ [+∞] │
│ Level 2:  [+∞] ────────────→ [+∞] ──────────────→ [+∞] │
│ Level 1:  [+∞] ───→ [+∞] ───→ [+∞] ───→ [+∞] ───→ [+∞] │
│ Level 0:  [+∞] →[A:1]→[B:3]→[C:5]→[D:8]→[E:12]→[NULL]   │
│           span=1  span=1  span=1  span=1  span=1         │
└─────────────────────────────────────────────────────────┘

二、跳表的操作 🔴

2.1 查找过程

// 跳表查找 ZRANK
zskiplistNode* zskiplistFind(zskiplist *zsl, robj *ele) {
    zskiplistNode *x = zsl->header;
    int i;
    // 从最高层开始，逐层往下搜索
    for (i = zsl->level - 1; i >= 0; i--) {
        while (x->level[i].forward &&
               compare(x->level[i].forward->ele, ele) < 0) {
            // 同层向右找
            x = x->level[i].forward;
        }
    }
    // x 是目标节点的前驱
    x = x->level[0].forward;
    if (x && equal(x->ele, ele))
        return x;
    return NULL;
}

2.2 插入过程

// 插入步骤：
// 1. 查找插入位置（记录每层的前驱节点）
// 2. 随机生成新节点的层数
// 3. 创建新节点，逐层插入

// 随机层级生成：Redis 使用概率模型
int randomLevel(void) {
    int level = 1;
    while (random() < ZSKIPLIST_P)  // ZSKIPLIST_P = 0.25
        level++;
    return min(level, ZSKIPLIST_MAXLEVEL);  // 最大 32 层
}

2.3 层级概率模型

-- Redis 跳表层数概率（ZSKIPLIST_P = 0.25）：
-- 50% 的节点在 Level 0
-- 25% 的节点在 Level 1
-- 6.25% 的节点在 Level 2
-- 1.56% 的节点在 Level 3
-- ...

-- 为什么选 0.25？
-- 跳表期望层数 = 1 / (1 - P) = 1 / 0.75 ≈ 1.33
-- 空间开销可控，查找效率接近理想跳表

三、跳表 vs 红黑树 🟡

3.1 为什么 Redis 用跳表而不是红黑树？

维度	跳表	红黑树
查找复杂度	O(log n)	O(log n)
插入复杂度	O(log n)	O(log n)
删除复杂度	O(log n)	O(log n)
范围查询	O(log n + m)，天然支持	O(log n + m)，需要中序遍历
实现难度	简单	复杂
内存占用	高（节点多个指针）	低（每个节点 3 个指针）
顺序遍历	简单（链表天然有序）	需要中序遍历
线程安全	简单加锁即可	需要旋转操作，复杂

Redis 选择跳表的原因：

范围查询更简单：跳表天然按序排列，范围查询只需找到起点然后顺序遍历
实现简单：跳表只有插入/删除，没有旋转操作
便于逆序遍历：跳表每个节点有 backward 指针

3.2 ❌ 错误示范

候选人原话："跳表比红黑树快，所以 Redis 选跳表。"

问题诊断：两者复杂度相同。Redis 选跳表是因为实现简单和范围查询方便，不是因为性能差异。

候选人原话 2："跳表的层数是固定的。"

问题诊断：跳表每层的跨度是随机的，通过概率模型决定。随机层数保证了跳表的平衡性。

【面试官心理】这道题我能从多个角度追问。比如我会问："跳表和红黑树的内存占用差多少？"能说出"跳表每个节点有多个 forward 指针，红黑树只有 2~3 个"的候选人，说明他真正理解了两者的空间差异。

四、ZSet 的双重索引 🟡

4.1 为什么 ZSet 需要 dict？

-- ZSet 同时维护 skiplist 和 dict：
-- skiplist：按 score 排序，支持 ZRANGEBYSCORE、ZRANK
-- dict：member → score，快速查找 ZSCORE

ZSCORE zset member
-- dict 查找：O(1)，不需要遍历 skiplist
-- 如果只用 skiplist：O(log n)

4.2 一致性保证

-- ZADD zset 1 "a" 2 "b" 3 "c"
-- 同时：
-- skiplist: 插入节点 "a":1, "b":2, "c":3
-- dict:     dict["a"]=1, dict["b"]=2, dict["c"]=3

-- 删除/修改时，两边同时更新，保证一致性

4.3 内存开销

-- 每个 ZSet 节点：
-- skiplist node: ele + score + backward + levels[]
-- dict entry: key + value + next

-- dict 和 skiplist 存的是同一份 member（SDS 指针共享）
-- 内存开销 ≈ skiplist + dict 指针 ≈ 一个节点的 2~3 倍指针

【面试官心理】 ZSet 的双重索引是 Redis 设计中的经典权衡问题。能说清楚 dict 和 skiplist 各司其职、以及为什么需要 dict 的候选人，说明他对 Redis 的数据结构设计有深入理解。

级别	考察重点	期望回答
P5	基本结构	跳表是分层链表，层数随机
P6	原理理解	查找/插入过程、随机层级概率
P7	深度权衡	跳表 vs 红黑树、ZSet dict+skiplist 双重结构

#ZSet 底层跳表原理

#一、跳表的数据结构 🔴

#1.1 跳表 vs 链表

#1.2 跳表节点结构

#1.3 跳表图示

#二、跳表的操作 🔴

#2.1 查找过程

#2.2 插入过程

#2.3 层级概率模型

#三、跳表 vs 红黑树 🟡

#3.1 为什么 Redis 用跳表而不是红黑树？

#3.2 ❌ 错误示范

#四、ZSet 的双重索引 🟡

#4.1 为什么 ZSet 需要 dict？

#4.2 一致性保证

#4.3 内存开销