《Redis设计与实现》读书笔记（三十三） ——Redis排序命令sort的实现

《Redis设计与实现》读书笔记（三十三） ——Redis排序命令sort的实现

（原创内容，转载请注明来源，谢谢）

一、基本功能

redis的sort命令，可以对现有列表键、集合键或有序集合键的值进行排序。可以在sort命令后加上alpha参数，则表示按照字母表排序；加上asc、desc，分别是升序和降序。另外也可以通过by加上参数，对用户自定义的内容进行排序。

redis的排序，都是通过快速排序算法来实现的。快速排序算法见以前发过的文章。

二、sort <key>命令的实现

这个命令是对包含数字值的键进行排序。步骤如下：

1）创建一个和待排序元素（如列表、集合等，假设待排序元素为a）长度相同的数组，该数组的每一项都是一个redis.h/redisSortObject结构，该结构包含两个元素，obj与u。

2）遍历整个数组，将每个结构的obj指针，分别指向一个a中的一个元素，构成一对一的关系。

3）遍历整个数组，将每个obj指向的a的元素的值，都转成浮点数，存在数组元素u.score中。

4）根据u.score，对整个数组进行排序。

5）遍历数组，将数组中每个obj对应的列表元素作为返回值，返回给客户端。

排序前：

排序后：

三、alpha选项的实现

命令是sort<key> alpha，这是对字符串进行排序的方式。其和排序数字，区别在于没有利用到u.score，而是将obj指针指向元素之后，直接通过指针来找到相应的内容，并进行排序。

四、asc和desc选项的实现

默认情况，redis通过升序进行排序，结果按从小到大排列，字母从a开始。即：sort <key>和sort <key> asc是等价的，sort <key> desc是倒序。

升序和降序都由相同的快速排序算法执行。

五、by选项的实现

by是允许用户自定义权重，默认情况下是键对应的值就是本身的权重。

通过使用by选项，sort命令可以指定某些字符串的键，或某个哈希键所包含的某些域来作为元素的权重，对一个键进行排序。

例如：

mset fruits apple-price 8 banana-price 5.5 cherry-price 7
sort fruits by *-price

输出结果：

banana
cherry
apple

redis执行过程如下：

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

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

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

例如，对应apple元素，返回apple-price键。

4）将各个权重键对应的值，转成double类型的浮点数，保存到相应数组结构的u.score中。

例如apple-price对应的值是8，被转成8.0存到u.score中。

5）以u.score的值为权重，对数组进行排序。

6）遍历排序后的数组，将结果返回给客户端。

六、带有alpha选项的by选项

当每个键对应的结果是字符串，则需要带有alpha选项。

排序方法和不带alpha的by选项相似，区别在于u。对数字的排序，是保存在u.score中，而对字符串排序，则是利用到u.cmpobj指针，将其指向obj对应的字符串。再利用字符串进行排序，得到结果。

七、limit选项的实现

默认情况下，会将所有排序结果返回给客户端，通过limit可以只返回一部分内容给客户端。格式是limit <offset> <count>，例如：

sort lista limit 0 4

offset表示从第i个开始返回（从0开始是第一个），count表示一共返回几个给客户端。利用该选项，可以实现类似mysql中分页的功能。

详细步骤如下：

1）前几步骤同前面正常的排序，但是排序完成后不直接返回给客户端。

2）根据选项的offset和count，从排序后的第offset个元素开始的，逐个将结果返回给客户端，共返回count个元素。

八、get选项的实现

默认情况下，排序后返回的都是被排序键本身所包含的元素。通过get选项，可以让sort对键排序之后，根据被排序的元素，以及get选项所指定的模式，查找并返回某些键的值。

该选项，和前面的区别在于，返回的时候，会根据get选项指定的内容，将结果进行返回。

九、store选项的实现

默认情况下sort只返回结果，不保存排序结果，通过store可以保存结果，并且指定一个键，将结果保存在那个键。

例如sort listastore listb，会将对lista的排序结果保存在listb。

redis在将排序结果存入某个键的时候，会先查看该键是否存在。如果键已经存在，则会将该键先删除，再重新创建一个新的空白键，并将结果存入，再将结果返回给客户端。

十、多个选项执行的排序

1、执行顺序

sort的完整执行顺序如下：

1）排序，并查看是否有alpha、asc、desc、by这几个选项，有的话根据选项进行排序。

2）限制返回结果的长度，通过limit实现。

3）获取外部键，通过get命令，将外部的键整合到排序结果中。

4）保存排序结果，通过store实现。

5）向客户端返回结果集。

2、选项的摆放顺序

排序除了get命令，其他命令都是按照上述的顺序执行，因此选项放在任意的位置，都不会影响到排序的结果。即limit、store、asc、alpha、by等选项，可以随便混排，不会影响到排序的结果。

当加入了多个get命令，则多个get命令选项的pattern的顺序应该保持一致，才会保证结果顺序是一致的。

十一、总结

1、redis的排序，基本的是sort命令，会将数字集合按照升序进行排列；alpha选项后，会将字符串按照字母表顺序进行排列；asc和desc分别是升序和降序；by会通过特定的内容进行排序；get可以获取外部的键值；limit可以限制返回的结果数量；store是保存排序的结果。

2、redis排序前，会先创建一个和待排序元素大小相同的数组，如果排序的内容是数字，则会将其转成浮点数。

3、redis排序都是通过快速排序算法实现的。

4、除了get选项以外，其他选项的摆放位置不会影响到排序的结果。

——written by linhxx 2017.09.30