Redis中的Zset是怎么实现的？

Redis 中的 Zset（Sorted Set，有序集合）是其最复杂、最精妙的数据结构之一。它通过巧妙结合两种数据结构的优势，实现了高性能的排序和检索功能。

一、两种内部编码（实现方式）

Redis 的 Zset 会根据数据情况，在两种编码之间自动切换：

1. ziplist（压缩列表）

当满足以下两个条件时，Zset 会使用 ziplist 编码：

元素数量小于 zset-max-ziplist-entries（默认 128）
每个元素成员（member）的字符串长度小于 zset-max-ziplist-value（默认 64 字节）

存储结构：

[member1, score1, member2, score2, ...]

按 score 值从小到大 紧密排列
插入时需要移动后续元素，时间复杂度 O(N)
优势：内存利用率极高，连续存储，无指针开销

2. skiplist（跳跃表） + dict（字典）

当不满足 ziplist 条件时，自动转换为这个组合结构。这是 Zset 的 主要实现方式。

二、 skiplist + dict 组合实现详解

这是 Redis Zset 设计的精华所在。为什么要用两种数据结构？

1. skiplist（跳跃表）

负责 排序和范围操作。

跳跃表节点结构：

typedef struct zskiplistNode {
    // 成员对象（如字符串"user:1000"）
    robj *obj;
    // 分数（score）
    double score;
    // 后退指针（用于从后往前遍历）
    struct zskiplistNode *backward;
    // 层（Level）
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度（到下一个节点的距离）
        unsigned int span;
    } level[];
} zskiplistNode;

跳跃表示例：

头节点（无数据）
  |
  v
第3层: 10 -----------------------------------> 50
第2层: 10 -------------> 30 -------------> 50
第1层: 10 ---> 20 ---> 30 ---> 40 ---> 50

多层结构：高层的指针跨度大，实现快速定位
平均时间复杂度：
- 查找：O(log N)
- 插入：O(log N)
- 删除：O(log N)

2. dict（字典）

负责 快速查找成员对应的分数。

Key：成员对象（member）
Value：分数（score）

3. 两者如何协同工作？

typedef struct zset {
    // 指向字典的指针
    dict *dict;
    // 指向跳跃表的指针
    zskiplist *zsl;
} zset;

共享数据：成员和分数在两种结构中只存储一次，通过指针共享。

操作流程：

按成员查找分数（ZSCORE）：直接通过 dict，O(1) 完成
按范围查询（ZRANGE）：通过 skiplist，O(log N + M) 完成
插入/更新（ZADD）：
- 先在 dict 中检查成员是否存在
- 在 skiplist 中找到合适位置插入/更新

三、核心操作的时间复杂度

操作	命令	时间复杂度	主要使用的数据结构
插入/更新	ZADD	O(log N)	skiplist + dict
删除	ZREM	O(log N)	skiplist + dict
按成员查分数	ZSCORE	O(1)	dict
获取排名	ZRANK	O(log N)	skiplist
范围查询	ZRANGE	O(log N + M)	skiplist
按分数范围查询	ZRANGEBYSCORE	O(log N + M)	skiplist

四、为什么选择 skiplist 而不是红黑树？

这是 Redis 作者 Antirez 的经典设计选择，原因如下：

实现简单：skiplist 的实现比红黑树简单得多，代码可读性好
范围查询高效：skiplist 本身就是链表，天然支持顺序遍历
并发友好：虽然 Redis 单线程不需要考虑并发，但 skiplist 的简单性使得未来可能的多线程扩展更容易
性能相当：skiplist 的平均性能与红黑树相当，都是 O(log N)

五、内存优化技巧

1. 使用 ziplist 的条件调优

# 配置文件调整
zset-max-ziplist-entries 256    # 提高阈值
zset-max-ziplist-value 128       # 提高阈值

2. 谨慎使用大 member

# 不好的示例：member 过长
ZADD leaderboard 1000 "a_very_long_user_id_that_takes_much_memory:1234567890"

# 好的做法：使用短 member 或编码
ZADD leaderboard 1000 "u:1000"

3. 注意相同 score 时的排序

当多个成员具有相同 score 时，Redis 会按 字典序 排列成员：

ZADD myset 1 "banana" 1 "apple" 1 "cherry"
ZRANGE myset 0 -1  # 返回: apple, banana, cherry

六、生产环境实践

1. 监控 Zset 编码

# 查看 Zset 的编码方式
redis-cli object encoding myzset
# 返回：ziplist 或 skiplist

2. 大 Zset 的性能考虑

当 Zset 非常大时（例如百万级别）：

避免 ZRANGE 全量查询：使用 ZSCAN 进行增量迭代
分片策略：按业务逻辑将大 Zset 拆分成多个小 Zset
定期清理：使用 ZREMRANGEBYSCORE 或 ZREMRANGEBYRANK 清理过期数据

3. Redisson 中的 ZSet

在 Redisson 客户端中，ZSet 被封装为 RScoredSortedSet，提供了更多便捷操作：

RScoredSortedSet<String> zset = redisson.getScoredSortedSet("leaderboard");
zset.add(100.0, "player1");
zset.addAsync(95.5, "player2");  // 异步操作

七、应用场景示例

1. 排行榜

# 实时更新用户分数
ZADD leaderboard 100 "user:100"
ZADD leaderboard 150 "user:101"

# 获取前10名
ZREVRANGE leaderboard 0 9 WITHSCORES

# 获取用户排名
ZREVRANK leaderboard "user:100"

2. 延迟队列

# 将任务和执行时间戳放入 Zset
ZADD delayed_queue 1640995200000 "task:send_email:1001"

# 定期获取到期的任务
ZRANGEBYSCORE delayed_queue 0 1640995200000

3. 时间线/Feed流

# 按时间戳存储动态
ZADD user:1000:feed 1640995200000 "post:123"
ZADD user:1000:feed 1640995300000 "post:456"

# 获取最新的10条动态
ZREVRANGE user:1000:feed 0 9

总结

Redis Zset 的实现体现了工程上的卓越权衡：

双编码自适应：在内存和性能之间自动选择最佳方案
数据结构组合：skiplist 和 dict 的完美结合，兼顾了范围查询和单点查找
时间复杂度优化：核心操作都保持在 O(log N) 或更好

作为架构师，理解 Zset 的内部实现有助于：

在数据量增长时预测性能变化
合理设置参数以优化内存使用
设计更高效的数据访问模式
在需要时正确选择替代方案（如时间序列数据可考虑 Redis TimeSeries 模块）

Redis Zset 是一个经过深度优化的数据结构，它证明了在特定场景下，精心设计的组合数据结构往往比单一通用数据结构更高效。