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命令的排序结果。

原文地址：https://blog.csdn.net/tus00000/article/details/144000465

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！