Redis基本数据类型之ZSet

2020-07-11

Redis ZSet相对于其他四种常用的数据类型，更具吸引力，因为其在很多应用场景中都在使用，如最常见的就是网站排名、微博排名、热点话题等等。

1、简单介绍

Redis 有序集合和集合一样也是string类型元素的集合,且不允许重复的成员。

不同的是每个元素都会关联一个double类型的分数。redis正是通过分数来为集合中的成员进行从小到大的排序。

有序集合的成员是唯一的,但分数(score)却可以重复。

集合是通过哈希表实现的，所以添加，删除，查找的复杂度都是O(1)。集合中最大的成员数为 2^32 - 1 (4294967295, 每个集合可存储40多亿个成员)

2、常用命令

2.1、ZADD-设置值

ZADD key score member [[score member] [score member] …]

将一个或多个 member 元素及其 score 值加入到有序集 key 当中。

如果某个 member 已经是有序集的成员，那么更新这个 member 的 score 值，并通过重新插入这个 member 元素，来保证该 member 在正确的位置上。score 值可以是整数值或双精度浮点数。

2.2、ZSCORE-获取集合元素的分值

ZSCORE key member

返回有序集 key 中，成员 member 的 score 值。

如果 member 元素不是有序集 key 的成员，或 key 不存在，返回 nil 。

2.3、ZINCRBY-集合元素增加分值

ZINCRBY key increment member

有序集 key 的成员 member 的 score 值加上增量 increment 。

可以通过传递一个负数值 increment ，让 score 减去相应的值，当 key 不存在，或 member 不是 key 的成员时相当于新增该集合成员。

2.4、ZCARD-集合元素数量

ZCARD key

当 key 存在且是有序集类型时，返回有序集的数量。当 key 不存在时，返回 0

2.5、ZCOUNT-集合元素分数区间内的元素数量

ZCOUNT key min max

有序集 key 中， score 值在 min 和 max 之间(默认包括 score 值等于 min 或 max )的成员的数量。

2.6、ZRANGE-集合下标区间内的元素

ZRANGE key start stop [WITHSCORES]

获取集合下标区间内的元素。

下标参数 start 和 stop 都以 0 为底，也就是说，以 0 表示有序集第一个成员。超出范围的下标并不会引起错误。比如说，当 start 的值比有序集的最大下标还要大，或是 start > stop 时， [ZRANGE] 命令只是简单地返回一个空列表

2.7、ZREVRANGE-集合下标区间内的元素倒序

ZREVRANGE key start stop [WITHSCORES]

有序集 key 中，指定区间内的成员。其中成员的位置按 score 值递减(从大到小)来排列

2.8、ZRANK-元素在集合中的排名

ZRANK key member

有序集 key 中成员 member 的排名。其中有序集成员按 score 值递增(从小到大)顺序排列。排名以 0 为底，也就是说， score 值最小的成员排名为 0 。

2.9、ZREMRANGEBYRANK-移除指定下标区间内的元素

ZREMRANGEBYRANK key start stop

移除有序集 key 中，指定排名(rank)区间内的所有成员。

区间分别以下标参数 start 和 stop 指出，包含 start 和 stop 在内。下标参数 start 和 stop 都以 0 为底，也就是说，以 0 表示有序集第一个成员，以 -1 表示最后一个成员。

2.10、ZREMRANGEBYSCORE–移除指定分数区间内的元素

ZREMRANGEBYSCORE key min max

移除有序集 key 中，所有 score 值介于 min 和 max 之间(包括等于 min 或 max )的成员

3、内部实现

redis的hash底层的结构是通过ziplist和skiplist两种，我们分析下为什么使用两种及两种结构内部如何存储的及相互转换条件等

3.1、ziplist压缩列表

ziplist 编码的有序集合对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员（member），而第二个元素则保存元素的分值（score）

1	ZADD price 8.5 apple 5.0 banana 6.0 cherry

压缩列表的详细介绍请参考《Redis基本数据类型之Hash-压缩列表》

3.2、skiplist跳跃表

我们先介绍下什么是跳跃表由来：

我们要用某种数据结构来维护一组有序的int型数据的集合，并且希望这个数据结构在插入、删除、查找等操作上能够尽可能着快速，我们首先想到的就是数组

数组：查找方面，用数组存储的话，采用二分法可以在 O(logn) 的时间里找到指定的元素，不过数组在插入、删除这些操作中比较不友好，找到目标位置所需时间为 O(logn) ，进行插入和删除这个动作所需的时间复杂度为 O(n) ，因为都需要移动移动元素，所以最终所需要的时间复杂度为 O(n)

链表：链表在插入、删除的支持上就相对友好，当我们找到目标位置之后，插入、删除元素所需的时间复杂度为 O(1) ，注意，我说的是找到目标位置之后，插入、删除的时间复杂度才为O(1)。但链表在查找上就不友好了，不能像数组那样采用二分查找的方式。

那么有没有一种结构可以集成他们两个的长处呢？

链表本身不能提供二分查找的功能，但是我们可以将一部分关键节点的数据抽到上一层，这样一层一层抽取，每次遍历都从最高层遍历进行比较会快很多。

图中我们抽成4层的链表，这样每次从顶部查找，如查找5，我们先从第四层查找发现5<10，那么就会查找第三层发现5<6，那我们就继续向下查找5>2,我们在本层查找5<6，那就从第二层的“2”节点的位置，下沉到第一层查找，发现5=5，这样我们就查找成功。

基于这种方法，对于具有 n 个元素的链表，我们可以采取 ** (logn + 1) 层指针路径的形式，就可以实现在 O(logn) 的时间复杂度内，查找到某个目标元素了，这种数据结构，我们也称之为跳跃表。

那么我们分析下redis中的跳跃表：

skiplist 编码的有序集合对象使用 zset 结构作为底层实现，一个 zset 结构同时包含一个字典和一个跳跃表

typedef struct zset {
    //字典
    dict *dict;
    //压缩链表
    zskiplist *zsl;
} zset;

zset 结构中的 dict 字典为有序集合创建了一个从成员到分值的映射， 字典中的每个键值对都保存了一个集合元素： 字典的键保存了元素的成员，而字典的值则保存了元素的分值。通过这个字典，程序可以用 O(1) 复杂度查找给定成员的分值， ZSCORE 命令就是根据这一特性实现的，而很多其他有序集合命令都在实现的内部用到了这一特性。

虽然 zset 结构同时使用跳跃表和字典来保存有序集合元素，但这两种数据结构都会通过指针来共享相同元素的成员和分值，所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员或者分值，也不会因此而浪费额外的内存。

我们先分析zskiplist

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

再看下zskiplistNode

typedef struct zskiplistNode {
	//成员变量，redis3.0版本中使用robj类型表示，但是在redis4.0.1中直接使用sds类型表示
    sds ele;
    //分值
    double score;
    //后退指针
    struct zskiplistNode *backward;
    //层
    struct zskiplistLevel {
        //前进指针
        struct zskiplistNode *forward;
        //跨度
        unsigned long span;
    } level[];
} zskiplistNode;

层是数组记录当前节点被抽取到的层数，前进指针用于访问表尾方向的下一个节点，跨度则记录前进指针和当前节点之间的距离。下图中连线上的数子就是距离。

如<o1,1.0>这个元素节点，level[]会记录4层，各个层指向同一层下一个节点的指针及跨度。

我们发现header头指针是不包含元素的，只会记录层的信息，其实结构还是zskiplistNode只是分值和成员变量都是null,会记录该列表中能达到的每一层的信息。

再看下zset里面dict

其实这个字典也没什么分析的只是记录当前列表的所有节点，为什么要同时使用这两种结构呢。

如果我们只使用字典来实现有序集合，那么虽然以 O(1) 复杂度查找成员的分值这一特性会被保留，但是，因为字典以无序的方式来保存集合元素，所以每次在执行范围型操作 —— 比如 ZRANK 、 ZRANGE 等命令时，那么跳跃表执行范围型操作的所有优点都会被保留。

为了让有序集合的查找和范围型操作都尽可能快地执行， Redis 选择了同时使用字典和跳跃表两种数据结构来实现有序集合。

3.3、转换

当有序集合对象可以同时满足以下两个条件时，对象使用 ziplist 编码：

有序集合保存的元素数量小于 128 个；

有序集合保存的所有元素成员的长度都小于 64 字节；

不能满足以上两个条件的有序集合对象将使用 skiplist 编码。

以上两个条件的上限值是可以修改的，配置文件中 zset-max-ziplist-entries 选项和 zset-max-ziplist-value 选项

本文作者： 顾明训
本文链接： https://www.itzones.cn/2020/07/11/Redis基本数据类型之ZSet/
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！