Redis(源码剖析):75---SORT命令的实现（struct redisSortObject）

程序员文章站 2022-05-20 11:13:46

...

一、SORT <key>命令

命令格式：

SORT <key>

功能：对键key进行排序
默认不带任何选项的SORT：
- 只可以对包含数字键的键key进行排序
- 默认是升序排序
例如下面对一个包含3个数字的列表进行排序

Redis(源码剖析):75---SORT命令的实现（struct redisSortObject）

SORT命令的实现（struct redisSortObject）

以下是redisSortObject结构的完整定义：

SORT命令为每个被排序的键都创建一个与键长度相同的数组，数组的每个项都是一个 redisSortObject结构，根据SORT命令使用的选项不同，程序使用redisSortObject结构的方式也不同
typedef struct _redisSortObject {
    //被排序键的值
    robj *obj;

    //权重
    union {
        //排序数字值时使用
        double score;
        //排序带有BY 选项的字符串值时使用
        robj *cmpobj;
    } u;
} redisSortObject;
服务器执行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"

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

二、ALPHA选项

命令格式：

SORT <key> ALPHA

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

Redis(源码剖析):75---SORT命令的实现（struct redisSortObject）

ALPHA选项的实现

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

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

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

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

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

三、ASC选项与DESC选项

命令格式：

SORT <key> ASC

SORT <key> DESC

功能：默认情况下SORT对排序结果进行升序结果（也就是ASC选项），但是使用DESC选项可以对排序的结果进行降序排序
例如下面的ASC选项与默认排序的结果一致，但是DESC却降序排序

Redis(源码剖析):75---SORT命令的实现（struct redisSortObject）

ASC选项与DESC选项的实现

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

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

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

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

下面第一张图展示了SORT命令在对numbers列表执行升序排序时所创建的数组

下面第二张图展示了SORT命令在对numbers列表执行降序排序时所创建的数组

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

四、BY选项

命令格式：

SORT <key> BY <by-pattern>

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

演示案例

下面第1个SORT命令根据水果的名称进行排序，

但是第2个SORT我们根据其他键的值作为权重来对fruits进行排序

BY选项的实现

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

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

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

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

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

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

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

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

"apple"元素的权重键"apple-price"的值转换之后为8.0

"banana"元素的权重键"banana-price"的值转换之后为5.5

·"cherry"元素的权重键"cherry-price"的值转换之后为7.0

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

权重为5.5的"banana"元素位于数组的索引0位置上

权重为7.0的"cherry"元素位于数组的索引1位置上

权重为8.0的"apple"元素位于数组的索引2位置上

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

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

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

命令格式：

SORT <key> BY <by-pattern> ALPHA

功能：在上面，我们介绍了BY选项可以根据其他权重键的值进行排序，但是其他权重键的值也是数字类型，如果其他权重键的值是字符串类型，那么就可以配合ALPHA选项来实现

演示案例

例如下面第2个SORT根据其他键的值（字符串值）进行排序

带有ALPHA选项的BY选项的实现

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

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

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

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

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

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

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

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

以各个数组项的权重键的值为权重，对数组执行字符串排序，结果如下图所示

权重为"FRUIT-13"的"cherry"元素位于数组的索引0位置上

权重为"FRUIT-25"的"apple"元素位于数组的索引1位置上

权重为"FRUIT-79"的"banana"元素位于数组的索引2位置上

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

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

五、LIMIT选项

命令格式：

SORT <key> LIMIT <offset> <count>

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

演示案例

LIMIT选项的实现

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

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

第2步：遍历数组，将各个数组项的obj指针分别指向alphabet集合的各个元素，如下图所示

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

第3步：根据选项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的第4不如下所示：

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

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

六、GET选项

命令格式：

SORT <key> GET <by-pattern>

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

单个GET选项演示案例

例如下面创建一个students集合，然后又创建了3个字符串对象，接着使用student集合对3个字符串对象进行排序

单个GET选项的实现

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

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

第2步：遍历数组，将各个数组项的obj指针分别指向students集合的各个元素，如下图所示

第3步：根据obj指针所指向的集合元素，对数组进行字符串排序，排序后的数组如下图所示

被排序到数组索引0位置的是"jack"元素

被排序到数组索引1位置的是"peter"元素

被排序到数组索引2位置的是"tom"元素

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

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

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

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

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

首先返回的是jack-name键的值"JackSnow"

然后返回的是peter-name键的值"Peter White"

最后返回的是tom-name键的值"Tom Smith"

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

多个GET选项演示案例

在上面那个演示案例的基础上，我们使用两个GET选项，第一个GET选项先对学生的名称进行排序，然后使用第二个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"

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

七、STORE选项

命令格式：

SORT <key> STORE <new_key>

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

演示案例

STORE选项的实现

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

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

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

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

被排序到数组索引0位置的是"jack"元素。 ·被排序到数组索引1位置的是"peter"元素。 ·被排序到数组索引2位置的是"tom"元素

检查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选项，将排序结果集保存到指定的键上面去
- 向客户端返回排序结果集：在最后这一步，命令遍历排序结果集，并依次向客户端返回排序结果集中的元素