【Redis】排序

Metadata

title: 【Redis】 排序
date: 2023-07-09 14:07
tags:
  - 行动阶段/完成
  - 主题场景/数据存储
  - 笔记空间/KnowladgeSpace/ProgramSpace/BasicsSpace
  - 细化主题/数据存储/Redis
categories:
  - 数据存储
keywords:
  - 数据存储/Redis
description: 【Redis】 排序

概述

Redis的SORT命令可以对列表键、集合键或者有序集合键的值进行排序。

本章将对SORT命令的实现原理进行介绍，并说明包括ASC、DESC、ALPHA、LIMIT、STORE、BY、GET在内的所有SORT命令选项的实现原理。

SORT命令通过将被排序键包含的元素载入到数组里面，然后对数组进行排序来完成对键进行排序的工作。
在默认情况下，SORT命令假设被排序键包含的都是数字值，并且以数字值的方式来进行排序。
如果SORT命令使用了ALPHA选项，那么SORT命令假设被排序键包含的都是字符串值，并且以字符串的方式来进行排序。
SORT命令的排序操作由快速排序算法实现。
SORT命令会根据用户是否使用了DESC选项来决定是使用升序对比还是降序对比来比较被排序的元素，升序对比会产生升序排序结果，被排序的元素按值的大小从小到大排列，降序对比会产生降序排序结果，被排序的元素按值的大小从大到小排列。
当SORT命令使用了BY选项时，命令使用其他键的值作为权重来进行排序操作。
当SORT命令使用了LIMIT选项时，命令只保留排序结果集中LIMIT选项指定的元素。
当SORT命令使用了GET选项时，命令会根据排序结果集中的元素，以及GET选项给定的模式，查找并返回其他键的值，而不是返回被排序的元素。
当SORT命令使用了STORE选项时，命令会将排序结果集保存在指定的键里面。
当SORT命令同时使用多个选项时，命令先执行排序操作（可用的选项为ALPHA、ASC或DESC、BY），然后执行LIMIT选项，之后执行GET选项，再之后执行STORE选项，最后才将排序结果集返回给客户端。
除了GET选项之外，调整选项的摆放位置不会影响SORT命令的排序结果。

SORT<key>命令的实现

SORT命令的最简单执行形式为：

SORT <key>

这个命令可以对一个包含数字值的键key进行排序。

服务器执行SORT numbers命令的详细步骤如下：
1）创建一个和numbers列表长度相同的数组，该数组的每个项都是一个redis.h/redisSortObject结构。
2）遍历数组，将各个数组项的obj指针分别指向numbers列表的各个项，构成obj指针和列表项之间的一对一关系，如图21-2所示。
3）遍历数组，将各个obj指针所指向的列表项转换成一个double类型的浮点数，并将这个浮点数保存在相应数组项的u.score属性里面，如图21-3所示。
4）根据数组项u.score属性的值，对数组进行数字值排序，排序后的数组项按u.score属性的值从小到大排列，如图21-4所示。
5）遍历数组，将各个数组项的obj指针所指向的列表项作为排序结果返回给客户端，程序首先访问数组的索引0，返回u.score值为1.0的列表项”1”；然后访问数组的索引1，返回u.score值为2.0的列表项”2”；最后访问数组的索引2，返回u.score值为3.0的列表项”3”。

ALPHA选项的实现

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

SORT <key> ALPHA

以下命令展示了如何使用SORT命令对一个包含三个字符串值的集合键进行排序：

服务器执行SORT fruits ALPHA命令的详细步骤如下：
1）创建一个redisSortObject结构数组，数组的长度等于fruits集合的大小。
2）遍历数组，将各个数组项的obj指针分别指向fruits集合的各个元素，如图21-5所示。
3）根据obj指针所指向的集合元素，对数组进行字符串排序，排序后的数组项按集合元素的字符串值从小到大排列：因为”apple”、”banana”、”cherry “三个字符串的大小顺序为”apple”<”banana”<”cherry “，所以排序后数组的第一项指向”apple”元素，第二项指向”banana”元素，第三项指向”cherry “元素，如图21-6所示。
4）遍历数组，依次将数组项的obj指针所指向的元素返回给客户端。

ASC选项和DESC选项的实现

在默认情况下，SORT命令执行升序排序，排序后的结果按值的大小从小到大排列，以下
两个命令是完全等价的：

SORT <key>
SORT <key> ASC

BY选项的实现

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

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

服务器执行SORT fruits BY*-id ALPHA命令的详细步骤如下：
1）创建一个redisSortObject结构数组，数组的长度等于fruits集合的大小。
2）遍历数组，将各个数组项的obj指针分别指向fruits集合的各个元素。
3）遍历数组，根据各个数组项的obj指针所指向的集合元素，以及BY选项所给定的模式*-id，查找相应的权重键：
将各个数组项的u.cmpobj指针分别指向相应的权重键（一个字符串对象）。
5）以各个数组项的权重键的值为权重，对数组执行字符串排序
6）遍历数组，依次将数组项的obj指针所指向的集合元素返回给客户端。

LIMIT选项的实现

通过LIMIT选项，我们可以让SORT命令只返回其中一部分已排序的元素。
LIMIT选项的格式为LIMIT<offset><count>：

offset参数表示要跳过的已排序元素数量。
count参数表示跳过给定数量的已排序元素之后，要返回的已排序元素数量。

服务器执行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指针所指向的元素”a”、”b”、”c”、”d”返回给客户端。
服务器执行SORT alphabet ALPHA LIMIT 2 3命令时的第一至第三步都和执行SORTalphabet ALPHA LIMIT 0 4命令时的步骤一样，只是第四步有所不同，上面的第4步如下：
4）根据选项LIMIT 2 3，将指针移动到数组的索引2上面，然后依次访问array [2]、array [3]、array [4]这3个数组项，并将数组项的obj指针所指向的元素”c”、”d”、”e”返回给客户端。

GET选项的实现

在默认情况下，SORT命令在对键进行排序之后，总是返回被排序键本身所包含的元素。

通过使用GET选项，我们可以让SORT命令在对键进行排序之后，根据被排序的元素，以及GET选项所指定的模式，查找并返回某些键的值。

服务器执行SORT students ALPHA GET*-name命令的详细步骤如下：
1）创建一个redisSortObject结构数组，数组的长度等于students集合的大小。
2）遍历数组，将各个数组项的obj指针分别指向students集合的各个元素，
3）根据obj指针所指向的集合元素，对数组进行字符串排序
4）遍历数组，根据数组项obj指针所指向的集合元素，以及GET选项所给定的模式，查找响应的键
5）遍历查找程序返回的三个键，并向客户端返回它们的值：
6）遍历数组，根据数组项obj指针所指向的集合元素，以及两个GET选项所给定的*-name模式和*-birth模式，查找相应的键：
7）遍历查找程序返回的六个键，并向客户端返回它们的值：

STORE选项的实现

通过使用STORE选项，我们可以将排序结果保存在指定的键里面，并在有需要时重用这个排序结果：

服务器执行SORT students ALPHA STORE sorted_students命令的详细步骤如下：
1）创建一个redisSortObject结构数组，数组的长度等于students集合的大小。
2）遍历数组，将各个数组项的obj指针分别指向students集合的各个元素。
3）根据obj指针所指向的集合元素，对数组进行字符串排序。
4）检查sorted_students键是否存在，如果存在的话，那么删除该键。
5）设置sorted_students为空白的列表键。
6）遍历数组，将排序后的三个元素”jack”、”peter”和”tom”依次推入sorted_students列表的末尾，相当于执行命令RPUSH sorted_students”jack”、”peter”、”tom”。
7）遍历数组，向客户端返回”jack”、”peter”、”tom”三个元素。

多个选项的执行顺序

选项的执行顺序

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

选项的摆放顺序

另外要提醒的一点是，调用SORT命令时，除了GET选项之外，改变选项的摆放顺序并不会影响SORT命令执行这些选项的顺序。