小言_互联网的博客

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

2020-04-01 15:16 302人阅读  评论(0)

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

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

Redis中sort命令简单使用，参考博客：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结构，如下图所示：
  • 2.遍历数组，将数组每项的obj指针指向numbers列表各项，一一对应。如下图所示：
  • 3.遍历数组，将各个obj指针指向的列表项转换成一个double类型的浮点数，然后将这个浮点数保存在对应数组项的u.score属性里。如下图所示：
  • 4.根据数组项的u.score属性的值，对数组进行排序（升序）。如下图所示：
  • 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集合各项，一一对应。如下图所示：
  • 3.根据obj指针指向的集合元素，对数组进行字符串排序，排序后的数组项按集合元素的字符串大小进行排列：apple < banana < cherry，排序后的数组如下图所示：
  • 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时创建数组如下：

执行降序命令：SORT numbers DESC时创建的数组：


四、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集合各个元素，如下图所示：
  • 3.遍历数组，根据各个数组项的obj指针所指向的集合元素、BY选项给定的模式*-price查找对应的权重键
    • 如 apple 元素，则查找键：apple-price，其他类似
  • 4.将各个权重键的值转换成double类型浮点数，然后保存在相应数组项的u.score属性里，如下图所示：
  • 5.以数组项u.score属性的值作为权重，对数组进行排序，得到一个按照u.score属性值升序排序的数组，如下图所示：
  • 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指针指向相应权重键（字符串对象），如下图所示：
  • 5.以各个数组项的权重键的值作为权重，对数组进行字符串排序，如下图所示：
  • 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集合的各个元素，如下图所示：
  • 根据obj指针所指向的集合元素，对数组进行字符串排序，排序后的数组如下图所示：
  • 根据选项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集合的各个元素，如下图所示：
  • 3.根据obj指针指向的集合元素，对数组进行字符串排序，排序后的数组如下图所示：
  • 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指针指向的集合元素，对数组进行字符串排序，排序后数组下图所示：
  • 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/100072950
查看评论
* 以上用户言论只代表其个人观点，不代表本网站的观点或立场