Redis学习笔记 - 排序（2） - SORT命令的实现

喜欢ヅ旅行 2024-04-17 06:04 26阅读 0赞

参考：<<Redis设计与实现>>

*  注：这本书是基于Redis3.0版本写的，和后面的版本有点差异

Redis中`sort`命令简单使用，参考博客：[https://blog.csdn.net/mytt\_10566/article/details/100042971][https_blog.csdn.net_mytt_10566_article_details_100042971]

### 一、SORT 命令的实现 ###

SORT命令最简形式：`SORT <key>`，用于对包含数字值的键进行排序

示例：

redis> rpush numbers 3 1 2
    (integer) 3
    
    redis> sort numbers
    1) "1"
    2) "2"
    3) "3"

服务器执行`SORT numbers`命令步骤如下：

*  1.创建一个和`numbers`列表长度相同的数组，该数组每项都是一个`redis.h/redisSortObject`结构，如下图所示：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70]
 *  2.遍历数组，将数组每项的`obj`指针指向`numbers`列表各项，一一对应。如下图所示：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 1]
 *  3.遍历数组，将各个`obj`指针指向的列表项转换成一个`double`类型的浮点数，然后将这个浮点数保存在对应数组项的`u.score`属性里。如下图所示：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 2]
 *  4.根据数组项的`u.score`属性的值，对数组进行排序（升序）。如下图所示：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 3]
 *  5.遍历数组，将各项的`obj`指针所指向的列表项作为排序结果返回给客户端

注：

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

`redisSortObject`结构的定义：

typedef struct _redisSortObject { 
    	// 被排序的键
    	robj *obj;
    	// 权重
    	union { 
    		// 排序数字时使用
    		double score;
    		// 排序带有BY选项的字符串值使用
    		robj *cmpobj;
    	} u;
    } redisSortObject;

### 二、ALPHA选项的实现 ###

通过`ALPHA`选项，`SORT`命令可以对包含字符串值的键进行排序：`SORT <key> ALPHA`

示例：

redis> sadd fruits apple banana cherry
    (integer) 3
    
    # 乱序
    redis> smembers fruits
    1) "apple"
    2) "cherry"
    3) "banana"
    
    redis> sort fruits alpha
    1) "apple"
    2) "banana"
    3) "cherry"

服务器执行`SORT fruits alpha`命令步骤如下：

*  1.创建一个和`fruits`集合长度相同的数组，该数组每项都是一个`redis.h/redisSortObject`结构
 *  2.遍历数组，将数组每项的`obj`指针指向`fruits`集合各项，一一对应。如下图所示：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 4]
 *  3.根据obj指针指向的集合元素，对数组进行字符串排序，排序后的数组项按集合元素的字符串大小进行排列：apple < banana < cherry，排序后的数组如下图所示：  
    ![排序后的数组][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 5]
 *  4.遍历数组，依次将数组项的obj指针所指向的元素返回给客户端

### 三、ASC和DESC选项的实现 ###

默认情况情况下，`SORT`命令是升序排序的，即 `SORT key` 等价于 `SORT key ASC`；降序排序命令：`SORT key DESC`。

示例：

redis> sort numbers
    1) "1"
    2) "2"
    3) "3"
    
    redis> sort numbers asc
    1) "1"
    2) "2"
    3) "3"
    
    redis> sort numbers desc
    1) "3"
    2) "2"
    3) "1"

升序和降序排序都由相同的快速排序算法执行，不同点：

*  执行升序排序时，排序算法使用的对比函数产生升序对比结果；执行降序排序时，则相反

执行升序命令：`SORT numbers`时创建数组如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 6]  
执行降序命令：`SORT numbers DESC`时创建的数组：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 7]

### 四、BY选项的实现 ###

默认情况下，`SORT`命令使用被排序键包含的元素作为排序的权重，元素本身决定了排序后的位置。

使用BY选项，`SORT`命令可以使用 ***指定的关键字***、***某个哈希键所包含的域（field）*** 作为元素排序的权重，然后对键进行排序。

示例：

使用水果的价钱对集合键fruits进行排序

redis> mset apple-price 8 banana-price 5.5 cherry-price 7
    OK
    
    redis> sort fruits by *-price
    1) "banana"
    2) "cherry"
    3) "apple"

服务器执行命令：`sort fruits by *-price`步骤如下：

*  1.创建一个redisSortObject结构数组，数组长度为fruits集合大小
 *  2.遍历数组，将各个数组项的`obj`指针指向fruits集合各个元素，如下图所示：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 8]
 *  3.遍历数组，根据各个数组项的`obj`指针所指向的集合元素、BY选项给定的模式`*-price`查找对应的权重键
    
     *  如 apple 元素，则查找键：apple-price，其他类似
 *  4.将各个权重键的值转换成double类型浮点数，然后保存在相应数组项的`u.score`属性里，如下图所示：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 9]
 *  5.以数组项`u.score`属性的值作为权重，对数组进行排序，得到一个按照`u.score`属性值升序排序的数组，如下图所示：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 10]
 *  6.遍历数组，将数组项的`obj`指针指向的元素返回给客户端

### 五、带有ALPHA选项的BY选项的实现 ###

`BY`选项默认假设权重键保存的值是数字，如果是字符串，则要配合使用`ALPHA`选项。

示例：

假设水果都有一个编号（字符串），根据编号进行排序

redis> mset apple-id "FRUIT-25" banana-id "FRUIT-79" cherry-id "FRUIT-13"
    OK
    
    redis> sort fruits by *-id alpha
    1) "cherry"
    2) "apple"
    3) "banana"

服务器执行`sort fruits by *-id alpha`步骤如下：

*  1.创建一个redisSortObject结构数组，数组长度为fruits集合大小
 *  2.遍历数组，将各个数组项的`obj`指针指向fruits集合各个元素
 *  3.遍历数组，根据各个数组项的`obj`指针所指向的集合元素、`BY`选项给定的模式`*-id`查找对应的权重键
    
     *  如 apple 元素，则查找键：apple-id，其他类似
 *  4.将各个数组项的`u.cmpobj`指针指向相应权重键（字符串对象），如下图所示：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 11]
 *  5.以各个数组项的权重键的值作为权重，对数组进行字符串排序，如下图所示：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 12]
 *  6.遍历数组，将数组项的`obj`指针指向的集合元素返回给客户端

### 六、LIMIT选项的实现 ###

默认情况下，`SORT`命令会将排序后的所有元素都返回给客户端。通过`LIMIT`选项，可以让`SORT`命令只返回其中一部分已排序的元素。

LIMIT命令格式：`LIMIT <offset> <counnt>`

*  offset：表示要跳过的已排序元素数量（偏移量）
 *  count：返回数量

示例：

redis> sadd alphabet a b c d e f
    (integer) 6
    
    redis> sort alphabet alpha limit 0 4
    1) "a"
    2) "b"
    3) "c"
    4) "d"
    
    redis> sort alphabet aplha limit 2 3
    1) "c"
    2) "d"
    3) "e"

服务器执行`sort alphabet alpha limit 0 4`命令步骤如下：

*  创建一个redisSortObject结构数组，数组长度等于alphabet集合大小
 *  遍历数组，将各个数组项的`obj`指针指向`alphabet`集合的各个元素，如下图所示：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 13]
 *  根据`obj`指针所指向的集合元素，对数组进行字符串排序，排序后的数组如下图所示：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 14]
 *  根据选项`limit 0 4`，将指针移动到数组的索引0上，然后往后访问4个数组项，然后将数组项`obj`指针指向的元素返回给客户端

### 七、GET选项的实现 ###

默认情况下，`SORT`命令在对键排序后，返回排序键对应的元素。通过使用`GET`选项，可以让`SORT`命令对键排序后，根据被排序的元素，以及`GET`选项指定的模式，查找并返回某些键的值。

示例：

redis> sadd students peter jack tom
    (integer) 3
    
    redis> mset peter-name "Peter White" jack-name "Jack Snow" tom-name "Tom Smith"
    OK
    
    redis> sort students alpha get *-name
    1) "Jack Snow"
    2) "Peter White"
    3) "Tom Smith"

服务器执行`sort students alpha get *-name`命令步骤如下：

*  1.创建一个redisSortObject数组，数组的长度等于students集合的大小
 *  2.遍历数组，将各个数组项的`obj`指针分别指向students集合的各个元素，如下图所示：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 15]
 *  3.根据`obj`指针指向的集合元素，对数组进行字符串排序，排序后的数组如下图所示：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 16]
 *  4.遍历数组，根据数组项`obj`指针指向的集合元素，以及`GET`选项给定的`*-name`模式，查找对应的键：
    
     *  如元素：“jack”，查找键jack-name，并返回结果；其余元素类似
 *  5.遍历查找程序返回的三个键，向客户端返回值

SORT命令也支持带有多个GET选项，例如以下命令：

redis> mset peter-age 20 tom-age 21 jack-age 22
    OK
    
    redis> sort students alpha get *-name get *-age
    1) "Jack Snow"
    2) "22"
    3) "Peter White"
    4) "20"
    5) "Tom Smith"
    6) "21"

此时，在步骤4的时候，遍历集合元素，依次查找给定模式所对应的键：`jack-name`、`jack-age`，然后返回给客户端，其余步骤一致

### 八、STORE选项的实现 ###

默认情况下，`SORT`命令只向客户端返回排序结果，而不保存。使用`STORE`选项，可以将排序结果保存在指定的键里，在有需要时候重用这个结果。

示例：

redis> sort students alpha store sorted_students
    (integer) 3
    
    redis> lrange sorted_students 0 -1
    1) "jack"
    2) "peter"
    3) "tom"

服务器执行`sort students alpha store sorted_students`命令步骤如下：

*  1.创建一个redisSortObject结构数组，数组长度等于students集合大小
 *  2.遍历数组，将各个数组项的`obj`指针分别指向students集合元素
 *  3.根据`obj`指针指向的集合元素，对数组进行字符串排序，排序后数组下图所示：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 17]
 *  4.检查`sorted_students`键是否存在，如果存在，则删除该键
 *  5.设置`sorted_students`为空白的列表键
 *  6.遍历数组，将排序后的元素放入`sorted_students`列表末尾，相当于执行：`rpush sorted_students jack peter tom`
 *  7.遍历数组，向客户端返回元素

### 九、多个选项的执行顺序 ###

一个`SOTRE`命令通常包含多个选项，上面的例子都是单个选项，比较简单。多个选项时，选项的执行是有顺序的。

#### 9.1 选项的执行顺序 ####

如果按照选项来划分，一个`SORT`命令执行过程有下面4个步骤：

*  （1）排序：命令会使用`ALPHA`、`ASC` / `DESC`、`BY`这几个选项，对输入键进行排序，得到一个排序结果集
 *  （2）限制排序结果集的长度：命令使用`LIMIT`选项，对排序结果集的长度进行限制，只有`LIMIT`选项指定的元素会保留在排序结果集中
 *  （3）获取外部键：命令使用`GET`选项，根据排序结果集中的元素，以及`GET`选项指定的模式，查找并获取指定键的值，用这些值来作为新的排序结果集
 *  （4）保存排序结果集：命令使用`STORE`选项，将排序结果集保存到指定的键里
 *  （5）向客户端返回排序结果集：命令遍历排序结果集，依次向客户端返回排序结果集中的元素

注：以上步骤中，后一个步骤必须在前一个步骤完成之后进行。

示例：

客户端向服务器发送以下命令：  
`SORT <key> ALPHA DESC BY <by-pattern> LIMIT <offset> <count> GET <get-pattern> STORE <store_key>`

那么服务器执行步骤如下：

*  首先执行`SORT <key> ALPHA DESC BY <by-pattern>`
 *  接着执行`LIMIT <offset> <count>`
 *  然后执行`GET <get-pattern>`
 *  之后执行`STORE <store_key>`
 *  最后，命令遍历排序结果集，将结果集中的元素依次返回给客户端

#### 9.2 选项的摆放顺序 ####

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

示例：

如下面几个命令，产生的排序结果集一致：

redis> SORT <key> ALPHA DESC BY <by-pattern> LIMIT <offset> <count> GET <get-pattern> STORE <store_key>
    
    redis> SORT <key> LIMIT <offset> <count> BY <by-pattern> ALPHA GET <get-pattern> STORE <store_key> DESC
    
    redis> SORT <key> STORE <store_key> DESC BY <by-pattern> GET <get-pattern> ALPHA LIMIT <offset> <count>

注：如果有多个`GET`选项时，注意下前后顺序，否则产生的结果集不同。

[https_blog.csdn.net_mytt_10566_article_details_100042971]: https://blog.csdn.net/mytt_10566/article/details/100042971
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/3869df11bf9d4f6e819e60e97e4912d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/2818fc1c000241dc85702733951c2939.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/b95fe7152c77422b867609ddeb8833a9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/3b5b0559ad8b44a19b4f160e4b60b441.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/3464b03a070e4bb49d80553c16bdd0ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/8d87a347bd3c4552b9b6d0e3026aa1dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/cbe27421e49f48bbb305c47f6de8218e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/bb58e1a12519447ab87cc8e58cefa988.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 8]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/bd2a75bfd5084d4298b208206997d3a9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 9]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/f923376dcbca4b0c9688c1e97bfbe0a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 10]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/99f27967e8ef4628998bc1a6f8e759af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 11]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/80ba548d8aa74073a171a161c81dd2e9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 12]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/a07b299e4e9044cfa709ba41b4b0c291.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 13]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/e55f3dc4368944aa899b4913b09daabe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 14]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/63d9e80b49f64abe933222125defe81d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 15]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/1f2481b3b185418c94eaec9af178c0d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 16]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/3fbc78f19e854a7a90bf0c583a040bda.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215dHRfMTA1NjY_size_16_color_FFFFFF_t_70 17]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/2707533ef6f440098bda8f673295b273.png