Redis（八）：zset/zadd/zrange/zrembyscore 命令源码解析

前面几篇文章，我们完全领略了redis的string,hash,list,set数据类型的实现方法，相信对redis已经不再神秘。

本篇我们将介绍redis的最后一种数据类型: zset 的相关实现。

本篇过后，我们对redis的各种基础功能，应该不会再有疑惑。有可能的话，我们后续将会对redis的高级功能的实现做解析。（如复制、哨兵模式、集群模式）

回归本篇主题，zset。zset 又称有序集合(sorted set)，即是序版本的set。经过上篇的介绍，大家可以看到，redis的读取功能相当有限，许多是基于随机数的方式进行读取，其原因就是set是无序的。当set有序之后，查询能力就会得到极大的提升。

可以根据下标进行定位元素;

可以范围查询元素; 这是有序带来的好处。

那么，我们不妨先思考一下，如何实现有序？两种方法：1. 根据添加顺序定义，1、2、3... ; 2. 自定义排序值; 第1种方法实现简单，添加时复杂度小，但是功能受限；第2种方法相对自由，对于每次插入都可能涉及重排序问题，但是查询相对稳定，可以不必完全受限于系统实现;

同样，我们以功能列表，到数据结构，再功能实现的思路，来解析redis的zset有序集合的实现方式吧。

零、redis zset相关操作方法

zset: Redis 有序集合是string类型元素的集合,且不允许重复的成员。每个元素都会关联一个double类型的分数，通过分数来为集合中的成员进行从小到大的排序。

使用场景如: 保存任务队列，该队列由后台定时扫描; 排行榜;

从官方手册上查到相关使用方法如下：

1> ZADD key score1 member1 [score2 member2]

功能: 向有序集合添加一个或多个成员，或者更新已存在成员的分数

返回值: 添加成功的元素个数(已存在的添加不成功)

2>ZCARD key

功能: 获取有序集合的成员数

返回值: 元素个数或0

3>ZCOUNT key min max

功能: 计算在有序集合中指定区间分数的成员数

返回值: 区间内的元素个数

4>ZINCRBY key increment member

功能: 有序集合中对指定成员的分数加上增量 increment

返回值: member增加后的分数

5>ZINTERSTORE destination numkeys key [key ...]

功能: 计算给定的一个或多个有序集的交集并将结果集存储在新的有序集合 key 中

返回值: 交集元素个数

6>ZLEXCOUNT key min max

功能: 在有序集合中计算指定字典区间内成员数量

返回值: 区间内的元素个数

7>ZRANGE key start stop [WITHSCORES]

功能: 通过索引区间返回有序集合指定区间内的成员

返回值: 区间内元素列表

8>ZRANGEBYLEX key min max [LIMIT offset count]

功能: 通过字典区间返回有序集合的成员

返回值: 区间内元素列表

9>ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT]

功能: 通过分数返回有序集合指定区间内的成员

返回值: 区间内元素列表

10>ZRANK key member

功能: 返回有序集合中指定成员的索引

返回值: member的排名或者 nil

11>ZREM key member [member ...]

功能: 移除有序集合中的一个或多个成员

返回值: 成功移除的元素个数

12>ZREMRANGEBYLEX key min max

功能: 移除有序集合中给定的字典区间的所有成员

返回值: 成功移除的元素个数

13>ZREMRANGEBYRANK key start stop

功能: 移除有序集合中给定的排名区间的所有成员

返回值: 成功移除的元素个数

14>ZREMRANGEBYSCORE key min max

功能: 移除有序集合中给定的分数区间的所有成员

返回值: 成功移除的元素个数

15>ZREVRANGE key start stop [WITHSCORES]

功能: 返回有序集中指定区间内的成员，通过索引，分数从高到低

返回值: 区间内元素列表及分数

16>ZREVRANGEBYSCORE key max min [WITHSCORES]

功能: 返回有序集中指定分数区间内的成员，分数从高到低排序

返回值: 区间内元素列表及分数

17>ZREVRANK key member

功能: 返回有序集合中指定成员的排名，有序集成员按分数值递减(从大到小)排序

返回值: member排名或者 nil

18>ZSCORE key member

功能: 返回有序集中，成员的分数值

返回值: member分数

19>ZUNIONSTORE destination numkeys key [key ...]

功能: 计算给定的一个或多个有序集的并集，并存储在新的 key 中

返回值: 存储到新key的元素个数

20>ZSCAN key cursor [MATCH pattern] [COUNT count]

功能: 迭代有序集合中的元素（包括元素成员和元素分值）

返回值: 元素列表

21> ZPOPMAX/ZPOPMIN/BZPOPMAX/BZPOPMIN

一、zset 相关数据结构

zset 的实现，使用了 ziplist, zskiplist 和 dict 进行实现。

二、zadd 添加成员操作

从添加实现中，我们可以完整领略数据结构的运用。

ziplist添加没啥好说的，skiplist可以稍微提提，大体步骤为四步:

1. 找位置, 从最高层开始, 判断是否后继节点小，如果小则直接在本层迭代，否则转到下一层迭代; (每一层都要迭代至相应的位置)

2. 计算得到一新的随机level,用于决定当前节点的层级;

3. 依次对每一层与原跳表做关联;

4. 设置backward指针;（双向链表）

相对说，skiplist 还是有点抽象，我们画个图来描述下上面的操作：

先看插入过程的目的，主要是为了先理解 skiplist 的构造过程。而在zset的更新过程，是先删除原节点，再进行插入的这么个过程。所以咱们还是有必要再来看看 skiplist 的删除节点过程。

skiplist 删除过程的示意图如下：

最后，我们再来看另一种情况，即zset发生编码转换时，是如何做的。即如何从 ziplist 转换到 skiplist 中呢？

至此，整个添加过程结束。本身是不太复杂的，主要针对 ziplist 和 skiplist 的分别处理（注意有逆向编码）。但为了讲清整体关系，稍显杂乱。

三、zrange 范围查询

范围查询功能，redis提供了好几个，zrange/zrangebyscore/zrangebylex... 应该说查询方式都不太一样，不过我们也不必纠结这些，只管理会大概就行。就挑一个以 下标进行范围查询的实现讲解下就行。

根据范围查找元素，整体是比较简单，迭代输出而已。只是 skiplist 的span维护，得好好想想。

四、zrembyscore 根据分数删除元素

zrembyscore, 首先这是个删除命令，其实它是根据分数查询，我们可以同时解析这两种情况。

删除的逻辑比较清晰，ziplist和skiplist分开处理。大体思路相同是：找到第一个符合条件的元素，然后迭代，直到第一个不符合条件的元素为止。

set虽然从定义上与zset有很多相通之处，然而在实现上却是截然不同的。由于很多东西和之前介绍的知识有重合的地方，也没啥好特别说的。zset 的解析差不多就到这里了。

你觉得zset还有什么有意思的实现呢？欢迎讨论。