Redis设计与实现 学习笔记 第二十一章 排序
Redis的SORT命令可以对列表键、集合键、有序集合键的值进行排序。
以下代码展示了SORT命令对列表键进行排序的例子:
以下代码展示了SORT命令使用ALPHA选项(ALPHA选项使SORT命令按字典顺序排序,默认SORT命令会将元素当作数字排序,如果元素不能被解释为数字,则将其视为0),对一个包含字符串值的集合键进行排序的例子:
下例使用SORT命令的BY选项,以jack_number、peter_number、tom_number三个键的值为权重,对有序集合test-result中的"jack"、“peter”、"tom"三个成员进行排序:
21.1 SORT <key>
命令的实现
SORT命令的最简单执行形式为:
这个命令可以对一个包含数字值的键key进行排序。
下例展示了如何使用SORT命令对一个包含三个数字值的列表键进行排序:
服务器执行SORT numbers命令的步骤如下:
1.创建一个和numbers列表长度相同的数组,数组中每个项都是一个redis.h/redisSortObject结构,如图21-1所示:
2.遍历数组,将各个数组项的obj指针分别指向numbers列表的各个项,构成obj指针和列表项之间的一对一关系,如图21-2所示:
3.遍历数组,将各个obj指针指向的列表项转换成一个double类型的浮点数,并将这个浮点数保存在相应数组项的u.score属性里,如图21-3所示:
4.根据数组项u.score属性的值,对数组进行数字值排序,排序后的数组项按u.score属性的值从小到大排列,如图21-4所示:
5.遍历数组,将各个数组项的obj指针所指向的列表项作为排序结果返回给客户端。
以下是redisSortObject结构的完整定义:
typedef struct _redisSortObject {// 被排序键的值robj *obj;// 权重union {// 排序数字值时使用double score;// 排序带有BY选项的字符串值时使用robj *cmpobj;} u;
} redisSortObject;
SORT命令为每个被排序的键都创建一个与键长度相同的数组,数组的每个项都是一个redisSortObject结构,根据SORT命令使用的选项不同,程序使用redisSortObject结构的方式也不同。
21.2 ALPHA选项的实现
通过使用ALPHA选项,SORT命令可对包含字符串值的键进行排序:
以下命令展示了如何使用SORT命令对一个包含三个字符串值的集合键进行排序:
服务器执行SORT fruit ALPHA命令的详细步骤如下:
1.创建一个redisSortObject结构数组,数组的长度等于fruits集合的大小。
2.遍历数组,将各个数组项的obj指针分别指向fruits集合的各个元素,如图21-5所示:
3.根据obj指针所指向的集合元素,对数组进行字符串排序,排序后的数组项按集合元素的字符串值从小到大排列,如图21-6所示:
4.遍历数组,依次将数组项的obj指针所指向的元素返回给客户端。
21.3 ASC选项和DESC选项的实现
默认SORT命令按升序排序,以下两个命令完全等价:
在执行SORT命令时使用DESC选项,可以让命令按降序排序:
以下是两个对numbers列表进行升序排序的例子,第一个命令根据默认设置,对numbers列表进行升序排序,第二个命令使用ASC命令,显式地对numbers列表进行升序排序,两个命令产生的效果完全一样:
以下命令对numbers列表进行降序排序:
升序和降序排序都由相同的快速排序算法执行。
图21-7展示了SORT命令对numbers列表执行升序排序时创建的数组:
图21-8展示了SORT命令对numbers列表执行降序排序时创建的数组:
21.4 BY选项的实现
默认SORT命令使用被排序键包含的元素作为排序的权重,元素本身决定了元素在排序后所处的位置。
例如,下例中,排序fruits集合所使用的权重就是"apple"、“banana”、"cherry"三个元素本身:
通过使用BY选项,SORT命令可指定某些字符串键,或某哈希键包含的某些域(field)来作为元素的权重,对一个键进行排序。
例如,下例使用苹果、香蕉、樱桃的价钱,对集合键fruits进行了排序:
MSET命令原子地设置多个键值对。
服务器执行上图SORT命令的步骤如下:
1.创建一个redisSortObject结构数组,数组的长度等于fruits集合的大小。
2.遍历数组,将各个数组项的obj指针分别指向fruits集合的各个元素,如图21-9所示:
3.遍历数组,根据各个数组项的obj指针所指向的集合元素,以及BY选项给定的模式*-price
,查找相应的权重键:
(1)对于"apple"元素,查找程序返回权重键"apple-price"。
(2)对于"banana"元素,查找程序返回权重键"banana-price"。
(3)对于"cherry"元素,查找程序返回权重键"cherry-price"。
4.将各个权重键的值转换成一个double类型的浮点数,然后保存在相应数组项的u.score属性里,如图21-10所示:
5.以数组项u.score属性的值为权重,对数组进行升序排序,如图21-11所示:
6.遍历数组,依次将数组项的obj指针所指向的集合元素返回给客户端。
21.5 带有ALPHA选项的BY选项的实现
BY选项默认假设权重键保存的值为数字值,如果权重键保存的是字符串值,就需要在使用BY选项的同时,配合使用ALPHA选项。
例如,fruits集合包含的三种水果都有一个字符串编号:
我们可以以水果编号为权重,对fruits集合进行排序:
服务器执行上图命令的步骤如下:
1.创建一个redisSortObject结构数组,数组长度等于fruits集合的大小。
2.遍历数组,将各个数组项的obj指针分别指向fruits集合的各个元素,如图21-12所示:
3.遍历数组,根据各个数组项的obj指针所指向的集合元素,以及BY选项所给定的模式*-id
,查找相应的权重键:
(1)对于"apple"元素,查找程序返回权重键"apple-id"。
(2)对于"banana"元素,查找程序返回权重键"banana-id"。
(3)对于"cherry"元素,查找程序返回权重键"cherry-id"。
4.将各个数组项的u.cmpobj指针分别指向相应的权重键(一个字符串对象),如图21-13所示:
5.以各个数组项的权重键的值为权重,对数组执行字符串排序,结果如图12-14所示:
6.遍历数组,依次将数组项的obj指针所指向的集合元素返回给客户端。
21.6 LIMIT选项的实现
默认SORT命令会将排序后的所有元素都返回给客户端:
但通过LIMIT选项,我们可以让SORT命令只返回其中一部分已排序的元素。
LIMIT选项的格式为LIMIT <offset> <count>
:
1.offset参数表示要跳过的已排序元素数量。
2.count参数表示跳过给定数量的已排序元素后,要返回的已排序元素数量。
例如,以下代码首先对alphabet集合进行排序,接着跳过0个已排序元素,然后返回4个已排序元素:
类似地,以下代码先对alphabet集合进行排序,接着跳过2个已排序元素,然后返回3个已排序元素:
服务器执行SORT alphabet ALPHA LIMIT 0 4命令步骤如下:
1.创建一个redisSortObject结构数组,数组的长度等于alphabet集合的大小。
2.遍历数组,将各个数组项的obj指针分别指向alphabet集合的各个元素,如图21-15所示:
3.根据obj指针所指向的集合元素,对数组进行字符串排序,排序后的数组如图21-16所示:
4.根据选项LIMIT 0 4,将指针移动到数组索引0上,然后依次访问array[0]、array[1]、array[2]、array[3]这4个数组项,并将数组项的obj指针指向的元素返回给客户端。
21.7 GET选项的实现
默认SORT命令对键进行排序后,总是返回被排序键中包含的元素。
比如,以下这个对students集合进行排序的例子中,SORT命令返回的是排序后的students集合的元素:
但通过使用GET选项,我们可以让SORT命令对键进行排序后,根据被排序的元素,以及GET选项指定的模式,查找并返回某些键的值。
例如下例中,SORT命令先对students集合进行排序,然后根据排序结果中的元素(学生的简称),查找并返回这些学生的全名:
服务器执行SORT students ALPHA GET *-name命令的步骤如下:
1.创建一个redisSortObject结构数组,数组的长度等于students集合的大小。
2.遍历数组,将各个数组项的obj指针分别指向students集合的各个元素,如图21-17所示:
3.根据obj指针所指向的集合元素,对数组进行字符串排序,排序后的数组如图21-18所示:
4.遍历数组,根据数组项obj指针所指向的集合元素,以及GET选项所给定的*-name
模式,查找相应的键:
(1)对于"jack"元素和*-name
模式,查找程序返回键jack-name。
(2)对于"peter"元素和*-name
模式,查找程序返回键peter-name。
(3)对于"tom"元素和*-name
模式,查找程序返回键tom-name。
5.遍历查找程序返回的符合*-name
模式的三个键,并向客户端返回它们的值。
因为一个SORT命令可以带有多个GET选项,随着GET选项的增多,命令要执行的查找操作也会增多。
例如,以下SORT命令对students集合进行了排序,并通过两个GET选项来获取被排序元素(一个学生)所对应的全名和出生日期:
服务器执行SORT students ALPHA GET *-name GET *-birth
命令的前三个步骤,和执行SORT students ALPHA GET *-name
命令时的前三个步骤相同,但从第四步开始有所区别:
4.遍历数组,根据数组项obj指针所指向的集合元素,以及两个GET选项所给定的*-name
和*-birth
模式,查找相应的键:
(1)对于"jack"元素和*-name
模式,查找程序返回jack-name键。
(2)对于"jack"元素和*-birth
模式,查找程序返回jack-birth键。
(3)对于"peter"元素和*-name
模式,查找程序返回peter-name键。
(4)对于"peter"元素和*-birth
模式,查找程序返回peter-birth键。
(5)对于"tom"元素和*-name
模式,查找程序返回tom-name键。
(6)对于"tom"元素和*-birth
模式,查找程序返回tom-birth键。
5.遍历查找程序返回的六个键,并向客户端返回它们的值。
21.8 STORE选项的实现
默认SORT命令只向客户端返回排序结果,而不保存排序结果。
但通过使用STORE选项,我们可以将排序结果保存在指定的键里,并在有需要时重用这个排序结果,下图中的LRANGE命令的最后的0和-1中间应该有个空格:
服务器执行上图命令的步骤如下:
1.创建一个redisSortObject结构数组,数组长度等于students集合的大小。
2.遍历数组,将各个数组项的obj指针分别指向students集合的各个元素。
3.根据obj指针指向的集合元素,对数组进行字符串排序,排序后的数组如图21-19所示:
4.检查sorted_students键是否存在,如果存在,则删除该键。
5.设置sorted_students为空白列表键。
6.遍历数组,将排序后的三个元素依次推入sorted_students列表末尾,相当于执行命令RPUSH sorted_students “jack” “peter” “tom”。
21.9 多个选项的执行顺序
21.9.1 选项的执行顺序
如果按照选项来划分的话,一个SORT命令的执行过程可分为以下四步:
1.排序:在这一步,命令会使用ALPHA、ASC、DESC、BY选项,对输入键进行排序。
2.限制排序结果集的长度:在这一步,命令会使用LIMIT选项,对排序结果集的长度进行限制。
3.获取外部键:在这一步,命令会使用GET选项,根据GET选项指定的模式,查找并获取指定键的值,并用这些值作为新的排序结果。
4.保存排序结果集:在这一步,命令会使用STORE选项,将结果集保存到指定键上。
5.向客户端返回命令结果。
21.9.2 选项的摆放顺序
调用SORT命令时,除了GET选项外,改变选项的摆放顺序不会影响SORT命令执行这些选项的顺序。但如果命令包含多个GET选项,那么在调整选项位置时,我们必须保证多个GET选项的摆放顺序不变,才能让排序结果集不变。
例如,命令:
和命令:
产生的排序结果集完全一样,但如果将两个GET选项顺序调整一下:
那么命令产生的结果集就会和前面两个命令产生的结果集不同。
21.10 重点回顾
1.SORT命令通过将被排序键包含的元素载入到数组里,然后对数组进行排序来完成对键进行排序的工作。
2.默认SORT命令假设被排序键包含的都是数字值,并且以数字值的方式来排序。
3.如果SORT命令使用了ALPHA选项,那么SORT命令假设被排序键包含的都是字符串值,并且以字符串的方式进行排序。
4.SORT命令的排序操作由快速排序算法实现。
5.SORT命令根据用户是否使用了DESC选项来决定是否使用降序排序。
6.当SORT命令使用BY选项时,命令使用其他键的值作为权重来进行排序操作。
7.当SORT命令使用了LIMIT选项时,命令只保留排序结果集中LIMIT选项指定的元素。
8.当SORT命令使用了GET选项时,命令会根据排序结果集中的元素,以及GET选项给定的模式,查找并返回其他键的值,而不是返回被排序的元素。
9.当SORT命令使用STORE选项时,命令会将排序结果集保存在指定键里。
10.当SORT命令同时使用多个选项时,命令先执行排序操作(可用选项为ALPHA、ASC、DESC、BY),然后执行LIMIT选项,之后执行GET选项,再之后执行STORE选项,最后将结果返回给客户端。
11.除了GET选项外,调整选项的摆放位置不影响SORT命令的排序结果。