Redis ZSet底层揭秘：跳跃表SkipList深度解析

一、背景与概述

在 Redis 的五大基本数据类型中，ZSet（有序集合） 是极为重要的一种结构，广泛应用于排行榜、延时任务队列、缓存排序等场景。

ZSet 背后的核心数据结构就是 跳跃表（SkipList） 与哈希表的组合，它是一种兼具有序性、高性能的结构。本文将带你深入剖析其底层实现机制，重点理解 SkipList 的结构、Redis 中的实现、常见操作与复杂度。

二、ZSet 数据结构总览

2.1 ZSet 的组成

ZSet 是 Redis 中用于实现有序集合的数据结构，底层由两部分组成：

• 字典（dict）：用于快速根据成员查找其对应的 score（分值）；
• 跳跃表（skiplist）：用于根据 score 排序，快速定位排名、范围查找等操作。

这两者共同维护 ZSet 的数据一致性，确保既能快速查找，又能保持有序性。

图解：

ZSet
 ├── dict: member -> score 映射（哈希表，O(1) 查找）
 └── skiplist: (score, member) 有序集合（跳跃表，O(logN) 范围查找）

三、跳跃表（SkipList）原理详解

3.1 SkipList 是什么？

跳跃表是一种基于多级索引的数据结构，它可以看作是一个多层链表，每一层是下一层的“索引”版本，从而加快查找速度。

SkipList 的特点：

• 插入、删除、查找时间复杂度为 O(logN)
• 实现简单，效率媲美平衡树
• 天然支持范围查询，非常适合排序集合

3.2 图解结构

以一个存储整数的 SkipList 为例（高度为4）：

Level 4:   ——>      10     ——>     50
Level 3:   ——>   5 ——> 10 ——> 30 ——> 50
Level 2:   ——>   5 ——> 10 ——> 20 ——> 30 ——> 50
Level 1:   ——> 1 ——> 5 ——> 10 ——> 20 ——> 30 ——> 40 ——> 50 ——> 60

每一层链表都可以跳跃地查找下一个节点，从而减少访问节点的数量。

四、Redis 中 SkipList 的实现结构

4.1 核心结构体（源码：server.h）

typedef struct zskiplistNode {
    sds ele;                    // 成员
    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;

⚠️ level[] 是变长数组（C99语法），节点高度在创建时确定。

4.2 插入节点图解

假设当前插入 (score=25, ele="userA")：

Step 1: 随机生成高度 H（比如是3）
Step 2: 找到每层对应的插入位置
Step 3: 调整 forward 和 span 指针
Step 4: 更新 header/tail 等信息

五、关键操作源码解读

5.1 插入节点：zslInsert()

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL];
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    ...
    int level = zslRandomLevel(); // 生成随机层级
    ...
    zskiplistNode *x = zslCreateNode(level, score, ele);
    for (int i = 0; i < level; i++) {
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;
        ...
    }
    ...
    return x;
}

5.2 删除节点：zslDelete()

int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL];
    ...
    for (int i = 0; i < zsl->level; i++) {
        if (update[i]->level[i].forward == x) {
            update[i]->level[i].forward = x->level[i].forward;
        }
    }
    ...
    zslFreeNode(x);
}

5.3 查找节点：zslGetRank()、zslFirstInRange()

Redis 为排名、范围查询提供了高效函数，如：

unsigned long zslGetRank(zskiplist *zsl, double score, sds ele);
zskiplistNode* zslFirstInRange(zskiplist *zsl, zrangespec *range);

六、时间复杂度分析

七、实际应用场景举例

7.1 排行榜系统

ZADD game_rank 100 player1
ZADD game_rank 200 player2
ZADD game_rank 150 player3

ZRANGE game_rank 0 -1 WITHSCORES

7.2 延时队列（定时任务）

利用 score 存储时间戳，实现定时执行：

ZADD delay_queue 1722700000 job_id_1
ZRANGEBYSCORE delay_queue -inf 1722700000

八、优化与注意事项

• 跳跃表节点最大层级为 32，默认概率为 0.25，保持高度平衡；
• 由于同时维护 dict 与 skiplist，每次插入或删除都要双操作；
• ZSet 非线程安全，适合单线程操作或加锁处理；
• 不适合频繁更新 score 的场景，容易造成 skiplist 大量重构。

九、总结

Redis 的 ZSet 是通过字典 + 跳跃表组合实现的高性能有序集合结构。其中跳跃表作为核心组件，提供了高效的插入、删除、范围查找等操作，其逻辑结构清晰、实现简洁，适合高并发场景。

通过本文的源码分析与结构图解，相信你对 SkipList 的工作机制和 Redis 中 ZSet 的底层实现有了更清晰的认识。