Redis: zset（sorted set，有序集合）

[dushaoshuai]

zset 介绍

Redis zset 是一个有序集合，其中不能存储重复元素，元素按照分数进行排序，分数相同时，元素按照字典序（一个字节一个字节地比较）排序。

向 zset myzset 中添加一个元素 shaouai，其分数为 100：

ZADD myzset 100 shaouai

除了唯一，有序的特性外，zset 还支持范围查询，支持按照索引范围查询、按照分数排序范围查询、按照字典序排序范围查询。

127.0.0.1:6379> ZADD myzset 100 shaouai 120 abc 99 nobody 248 expert
(integer) 4
127.0.0.1:6379> ZRANGE myzset 0 3 WITHSCORES
1) "nobody"
2) "99"
3) "shaouai"
4) "100"
5) "abc"
6) "120"
7) "expert"
8) "248"
127.0.0.1:6379> ZRANGE myzset 95 300 BYSCORE WITHSCORES
1) "nobody"
2) "99"
3) "shaouai"
4) "100"
5) "abc"
6) "120"
7) "expert"
8) "248"

需要注意，按照字典序进行范围查询时，所有元素的分数应该是相同的。

127.0.0.1:6379> DEL myzset
(integer) 1
127.0.0.1:6379> ZADD myzset 0 Redis 0 redis 0 REdis 0 rEDis
(integer) 4
127.0.0.1:6379> ZRANGE myzset - + BYLEX
1) "REdis"
2) "Redis"
3) "rEDis"
4) "redis"

内部数据类型

当 zset 较小时，Redis 使用特殊数据类型来节省空间，当 zset 大到一定程度时，Redis 会将该数据类型转换为较为通用的类型。

具体表现为：

如果元素个数小于 128 个，并且每个元素的值小于 64 字节^1：

---> 如果 Redis 版本 >= 7.0，使用 LISTPACK

---> 如果 Redis 版本 < 7.0，使用 ZIPLIST

否则，采用 hash + SKIPLIST（跳表）的组合来实现 zset。hash 将元素映射到分数，跳表将元素按照分数排序存储，相同分数的元素则按照字典序排序。

本文只关注 hash + 跳表 的组合。

Redis 中跳表实现

（Redis 7.2）

// server.h

// 跳表节点
typedef struct zskiplistNode {
    // 元素
    sds ele;
    // 分数
    double score;
    // 后退指针，指向前一个节点，在从表尾向表头遍历时使用
    struct zskiplistNode *backward;
    // 层数组
    struct zskiplistLevel {
        // 前进指针，指向同层的下一个节点
        struct zskiplistNode *forward;
        // 跨度，当前节点和下一个节点之间的距离，用来计算 rank
        unsigned long span;
    } level[];
} zskiplistNode;

// 跳表
typedef struct zskiplist {
    // 头节点和尾节点，头节点只存储前进指针
    struct zskiplistNode *header, *tail;
    // 节点数量，不包括头节点在内
    unsigned long length;
    // 节点最大层数，不包括头节点在内，最小为 1，最大为 32
    int level;
} zskiplist;

// 使用 hash 和跳表共同实现的 zset
typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

一个 Redis 跳表：

几个命令的执行过程

// TODO. // 暂时写不下去了，先放一放吧。

参见

• OBJECT ENCODING
• zset 相关命令
• Redis 源码：t_zset.c、server.h
• Redis 设计与实现 第 5 章 跳跃表