排序 | 彩潭有鲤的札记

type

status

date

slug

summary

SORT <key> 命令的实现

服务器执行 SORT numbers 命令的详细步骤如下：

创建一个和 numbers 列表长度相同的数组，该数组的每个项都是一个 redis.h/redisSortObject 结构：

遍历数组，将各个数组项的 obj 指针分别指向 numbers 列表的各个项，构成 obj 指针和列表项之间的一对一关系：

遍历数组，将各个 obj 指针所指向的列表项转换成一个 double 类型的浮点数，并将这个浮点数保存在相应数组项的 u.score 属性里面

根据数组项 u.score 属性的值，对数组进行数字值排序，排序后的数组项按 u.score 属性的值从小到大排列

遍历数组，将各个数组项的obj指针所指向的列表项作为排序结果返回给客户端：程序首先访问数组的索引0 ，返回u.score值为1.0 的列表项"1"；然后访问数组的索引1，返回u.score值为2.0的列表项"2" ；最后访问数组的索引2，返回u.score值为3.0 的列表项"3" 。

redisSortObject 结构的完整定义：

SORT命令为每个被排序的键都创建一个与键长度相同的数组，数组的每个项都是一个redisSortObject结构，根据SORT命令使用的选项不同，程序使用redisSortObject结构的方式也不同。

ALPHA选项

命令格式：SORT <key> ALPHA

默认的SORT只可以对包含数字的键进行排序，使用ALPHA选项可以对包含字符串值的键进行排序。对一个包含3个字符串值的集合键进行排序：

ALPHA选项的实现

创建一个redisSortObject结构数组，数组的长度等于fruits集合的大小

遍历数组，将各个数组项的obj指针分别指向fruits集合的各个元素：

根据obj指针所指向的集合元素，对数组进行字符串排序，排序后的数组项按集合元素的字符串值从小到大排列：因为"apple"、"banana"、"cherry"三个字符串的大小顺序为"apple"<"banana"<"cherry"，所以排序后数组的第一项指向"apple"元素，第二项指向"banana"元素，第三项指向"cherry"元素

遍历数组，依次将数组项的obj指针所指向的元素返回给客户端

其他SORTALPHA命令的执行步骤也和这里给出的SORT fruits ALPHA命令的执行步骤类似

ASC选项与DESC选项

命令格式：

默认情况下SORT对排序结果进行升序结果（也就是ASC选项），但是使用DESC选项可以对排序的结果进行降序排序

升序排序和降序排序都由相同的快速排序算法执行，它们之间的不同之处在于：

在执行升序排序时，排序算法使用的对比函数产生升序对比结果

而在执行降序排序时，排序算法所使用的对比函数产生降序对比结果

因为升序对比和降序对比的结果正好相反，所以它们会产生元素排列方式正好相反的两种排序结果。以numbers列表为例：

SORT命令在对numbers列表执行升序排序时所创建的数组

SORT命令在对numbers列表执行降序排序时所创建的数组

BY 选项的实现

命令格式：

功能：默认情况下SORT是根据键的元素的值作为权重来进行排序的，但是通过BY选项，SORT命令可以指定某些字符串键，或者某个哈希键所包含的某些域（field）来作为元素的权重对一个键进行排序

第1个SORT命令根据水果的名称进行排序，第2个SORT根据其他键的值作为权重来对fruits进行排序：

服务器执行上面SORT fruits BY*-price命令的详细步骤如下：

创建一个redisSortObject结构数组，数组的长度等于fruits集合的大小

遍历数组，将各个数组项的obj指针分别指向fruits集合的各个元素：

遍历数组，根据各个数组项的obj指针所指向的集合元素，以及BY选项所给定的模式 *-price，查找相应的权重键：

对于"apple"元素，查找程序返回权重键"apple-price"
对于"banana"元素，查找程序返回权重键"banana-price"
对于"cherry"元素，查找程序返回权重键"cherry-price"

将各个权重键的值转换成一个double类型的浮点数，然后保存在相应数组项的u.score属性里面，

以数组项u.score属性的值为权重，对数组进行排序，得到一个按u.score属性的值从小到大排序的数组，

遍历数组，依次将数组项的obj指针所指向的集合元素返回给客户端

其他SORTBY命令的执行步骤也和这里给出的步骤类似

ALPHA选项与BY选项的配合使用

命令格式：

BY选项可以根据其他权重键的值进行排序，但是其他权重键的值也是数字类型，如果其他权重键的值是字符串类型，那么就可以配合ALPHA选项来实现

执行上面SORT fruits BY*-id ALPHA命令的详细步骤如下：

创建一个redisSortObject结构数组，数组的长度等于fruits集合的大小

遍历数组，将各个数组项的obj指针分别指向fruits集合的各个元素

遍历数组，根据各个数组项的obj指针所指向的集合元素，以及BY选项所给定的模式*-id，查找相应的权重键：

对于"apple"元素，查找程序返回权重键"apple-id"
对于"banana"元素，查找程序返回权重键"banana-id"
对于"cherry "元素，查找程序返回权重键"cherry-id"

将各个数组项的u.cmpobj指针分别指向相应的权重键（一个字符串对象）

以各个数组项的权重键的值为权重，对数组执行字符串排序

遍历数组，依次将数组项的obj指针所指向的集合元素返回给客户端

其他SORT BY ALPHA命令的执行步骤也和这里给出的步骤类似

LIMIT选项

命令格式：

功能：使用LIMIT选项可以限制SORT命令返回的结果数量。从offset索引（索引从0开始）处开始返回count条结果

服务器执行上面SORT alphabet ALPHA LIMIT 0 4命令的详细步骤如下：

创建一个redisSortObject结构数组，数组的长度等于alphabet集合的大小

遍历数组，将各个数组项的obj指针分别指向alphabet集合的各个元素

根据obj指针所指向的集合元素，对数组进行字符串排序

根据选项LIMIT 0 4，将指针移动到数组的索引0上面，然后依次访问array [0]、 array[1]、array[2]、array [3]这4个数组项，并将数组项的obj指针所指向的元素"a"、"b"、"c"、"d"返回给客户端

服务器执行SORT alphabet ALPHA LIMIT 2 3命令时的第一至第三步都和执行SORT alphabet ALPHA LIMIT 0 4命令时的步骤一样，只是第四步有所不同：

根据选项LIMIT 2 3，将指针移动到数组的索引2上面，然后依次访问array [2]、 array[3]、array[4]这3个数组项，并将数组项的obj指针所指向的元素"c"、"d"、"e"返回给客户端

SORT命令在执行其他带有LIMIT选项的排序操作时，执行的步骤也和这里给出的步骤类似

GET选项

命令格式：

默认情况下SORT命令返回的是自己排序的结果，使用GET选项可以根据自己键的值来对别对的键进行排序，GET选项支持1个或多个。

服务器执行上面SORT students ALPHA GET*-name命令的详细步骤如下：

创建一个redisSortObject结构数组，数组的长度等于students集合的大小

遍历数组，将各个数组项的obj指针分别指向students集合的各个元素

根据obj指针所指向的集合元素，对数组进行字符串排序

遍历数组，根据数组项obj指针所指向的集合元素，以及GET选项所给定的*-name模式，查找相应的键：

对于"jack"元素和*-name模式，查找程序返回键jack-name
对于"peter"元素和*-name模式，查找程序返回键peter-name
对于"tom"元素和*-name模式，查找程序返回键tom-name

遍历查找程序返回的三个键，并向客户端返回它们的值：

首先返回的是jack-name键的值"JackSnow"
然后返回的是peter-name键的值"Peter White"
最后返回的是tom-name键的值"Tom Smith"

指定多个GET选项：因为一个SORT命令可以带有多个GET选项，所以随着GET选项的增多，命令要执行的查找操作也会增多

服务器执行SORT students ALPHA GET*-name GET*-birth命令的前三个步骤，和上面执行SORT students ALPHA GET*-name命令时的前三个步骤相同，但从第四步开始有所区别：

遍历数组，根据数组项obj指针所指向的集合元素，以及两个GET选项所给定的*- name模式和*-birth模式，查找相应的键：

对于"jack"元素和*-name模式，查找程序返回jack-name键
对于"jack"元素和*-birth模式，查找程序返回jack-birth键
对于"peter"元素和*-name模式，查找程序返回peter-name键
对于"peter"元素和*-birth模式，查找程序返回peter-birth键
对于"tom"元素和*-name模式，查找程序返回tom-name键
对于"tom"元素和*-birth模式，查找程序返回tom-birth键

遍历查找程序返回的六个键，并向客户端返回它们的值：

首先返回jack-name键的值"JackSnow"
其次返回jack-birth键的值"1995-5-24"
之后返回peter-name键的值"Peter White"
再之后返回peter-birth键的值"1995-6-7"
然后返回tom-name键的值"Tom Smith"
最后返回tom-birth键的值"1995-8-16"

STORE选项

命令格式：

使用STORE选项，可以将排序的结果保存到一个新键中

执行上面SORT students ALPHA STORE sorted_students命令的详细步骤如下：

创建一个redisSortObject结构数组，数组的长度等于students集合的大小

遍历数组，将各个数组项的obj指针分别指向students集合的各个元素

根据obj指针所指向的集合元素，对数组进行字符串排序

检查sorted_students键是否存在，如果存在的话，那么删除该键

设置sorted_students为空白的列表键

遍历数组，将排序后的三个元素"jack"、"peter"和"tom"依次推入sorted_students列表的末尾，相当于执行命令RPUSH sorted_students"jack"、"peter"、"tom"

遍历数组，向客户端返回"jack"、"peter"、"tom"三个元素

SORT命令在执行其他带有STORE选项的排序操作时，执行的步骤也和这里给出的步骤类似

SORT命令选项的执行顺序

如果按照选项来划分的话，一个SORT命令的执行过程可以分为以下几步：

排序：在这一步，命令会使用ALPHA、ASC或DESC、BY这几个选项，对输入键进行排序，并得到一个排序结果集

限制排序结果集的长度：在这一步，命令会使用LIMIT选项，对排序结果集的长度进行限制，只有LIMIT选项指定的那部分元素会被保留在排序结果集中

获取外部键：在这一步，命令会使用GET选项，根据排序结果集中的元素，以及 GET选项指定的模式，查找并获取指定键的值，并用这些值来作为新的排序结果集

保存排序结果集：在这一步，命令会使用STORE选项，将排序结果集保存到指定的键上面去

向客户端返回排序结果集：在最后这一步，命令遍历排序结果集，并依次向客户端返回排序结果集中的元素

选项的摆放顺序

调用SORT命令时，除了GET选项之外，改变选项的摆放顺序并不会影响SORT命令执行这些选项的顺序