Redis ZSet 跳表设计与实现¶

一、ZSet 是什么¶

有序集合（Sorted Set），每个元素关联一个 score，按 score 排序。

ZADD rank 100 "Alice" 90 "Bob"
ZRANGE rank 0 -1

二、为什么用跳表¶

ZSet 需要： - 按 score 范围查询（O(log n)）。 - 插入/删除快。 - 支持排名（rank）。

数组：插入 O(n)。链表：查询 O(n)。平衡树（红黑树）：实现复杂。跳表：简单且 O(log n)。

三、跳表结构¶

在链表上建多层索引：

Level 3:  head ──────────────> 30 ──────────────> null
Level 2:  head ──────> 10 ──────> 30 ──────> 50 ──> null
Level 1:  head ─> 5 ─> 10 ─> 20 ─> 30 ─> 40 ─> 50 -> null

Level 1 是完整链表。
上层是下层的"快速通道"。
查找时从最高层开始，能跳就跳，不能跳就下一层。

四、Redis 跳表节点¶

typedef struct zskiplistNode {
    sds ele;                    // 元素
    double score;               // 分数
    struct zskiplistNode *backward;  // 前驱
    struct zskiplistLevel {
        struct zskiplistNode *forward;  // 后继
        unsigned long span;            // 跨度（用于算 rank）
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;                  // 当前最高层数
} zskiplist;

span 跨度¶

记录每一层跳过了多少个节点，用于 O(log n) 算排名：

rank = sum(span of all forward pointers traversed)

五、随机层数¶

新节点层数不是固定的，随机：

int zslRandomLevel(void) {
    int level = 1;
    while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

P = 0.25（25% 概率升层）。
最大 32 层。
层数越高概率越低：1/4、1/16、1/64...

六、查找流程¶

从最高层开始。
当前节点 next 的 score ≤ 目标，就往前走。
不能走了，降一层继续。
到 Level 1 找到前驱节点。

七、对比平衡树¶

	跳表	红黑树
实现	简单	复杂
范围查询	容易（Level 1 链表）	中序遍历
插入删除	改指针	旋转
并发	容易加锁	复杂
内存	多层索引节点	父子指针

Redis 选跳表就是因为实现简单、范围查询快。

高频追问

跳表查找 O(log n)，最坏 O(n)（概率极低）。
span 用来算 rank，不用遍历。
跳表是随机化数据结构，不是确定性平衡树。