redis · 9 4 月, 2021 0

Redis排序实现

排序

Redis的sort命令可以对列表键, 集合键或者有序结合的键进行排序.

以下代码展示了SORT命令对列表键进行排序的例子:

redis> RPUSH numbers 5 3 1 4 2
redis> LRANGE numbers 0 -1
redis> SORT numbers
redis> SADD alphabet a b c d e f g
redis> SMEMBERS alphabet
redis> SORT alphabet ALPHA

 

接下来使用SORT命令和BY选项, 以jack_number,peter_number,tom_number三个值为权重weight，对有序集合test-result中的jack,peter,tom三个成员进行排序:

redis> ZADD test-result 3.0 jack 3.5 peter 4.0 tom
​
# 为哥哥元素设置序号
redis> MSET peter_number 1 tom_number 2 jack_number 3
​
# 以序号为权重, 对有序集合中的元素进行排序
redis> SORT test_result by *_number

 

本章节将会对排序的原理进行学习, 并说明包括ASC,DESC,ALPHA,LIMIT,STORE,BY,GET在内的所有的SORT命令选项的实现原理。

SORT <key>命令的实现

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

SORT <key>

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

以下实例展示了如何使用SORT命令对一个包含三个数值的列表进行排序:

redis> RPUSH numbers 3 1 2
redis> 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.socre值为2.0的列表项2.最后访问数组的索引2, 返回u.score值为3.0的列表项3

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

ALPHA 选项的实现

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

SORT <key> ALPHA

 

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

SADD fruits apple banana cherry
​
SORT fruits ALPHA

 

SORT fruits ALPHA命令的详细步骤

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

  • 遍历数组, 将各个数组项的obj指针分别指向fruits集合的各个元素

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

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

ASC选项和DESC选项的实现

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

SORT <key>
SORT <key> ASC

 

相反地, 在执行SORT命令时使用DESC选项, 可以让命令执行降序排列, 让排序后的结果按值的大小从大到小排列:

SORT <key> DESC

一下是两个对numbers列表进行升序排序的例子, 第一个命令根据默认设置, 对numbers列表进行排序, 而第二个命令则通过显式地使用ASC选项, 对numbers列表进行升序排序, 两个命令产生的结果完全一样:

redis> RPUSH numbers 3 1 2
​
redis> SORT numbers
​
redis> SORT numbers ASC
​
redis> SORT numbers DESC

 

排序算法

升序排序和降序排序都由相同的快速排序算法执行, 他们之间的不同之处在于:

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

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

因为升序对比和降序对比的结果正好相反, 所以他们会产生元素排列方式正好相反的两种排序结果。

BY 选项的实现

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

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

redis> SADD fruits "apple" "banana" "cherry"
redis> SORT fruits ALPHA
redis> MSET apple-price 8 banana-price 5.5 cherry-price 7

 

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指针所指向的集合元素返回给客户端

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

BY 选项默认假设权重键保存的值为数字值, 如果权重键保存的是字符串的话, 那么就需要再使用BY选项的同时，配合使用ALPHA选项

redis> SADD fruits "apple" "banana" "cherry"
redis> MSET apple-id "FRUIT-25" banana-id "FRUIT-79" cherry-id "FRUIT-13"
reids> SORT fruits BY *-id ALPHA

 

sort fruits BY *-id ALPHA 命令的详细步骤

  • 创建一个redisSortObject结构数组, 数组的长度等于fuits集合的大小

  • 遍历数组, 将各个数组项的obj指针分别指向fruits集合的各个元素

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

    • 对于apple元素, 查找程序返回权重键”apple-id”

    • 对于”banana”元素, 查找程序返回权重键”banana-id”

    • 对于”cherry”元素, 查找程序返回权重键”cherry-id”

  • 将各个数组项的u.compobj指针分别指向对应的权重键

  • 以各个数组项的权重键的值为权重, 对数组执行字符串排序

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

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

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

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

NOTE: 其他SORT <key> BY <pattern> ALPHA命令的执行步骤也和这里给出的步骤类似

LIMIT 选项的实现

在默认情况下, SORT命令总会将排序后的所有元素都返回给客户端: 但是通过LIMIT选项， 我们可以让SORT命令只返回其中一部分已排序的元素.

LIMIT 选项的格式为LIMIT <offset> <count>

  • offset参数表示要跳过的已排序元素数量

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

GET选项的实现

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

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

redis> SET peter-name "Peter White"
redis> SET jack-name "JACK SNOW"
redis> SET tom-name "Tom Smith"
​
redis> SORT students ALPHA GET *-name

 

服务器执行SORT students ALPHA GET *-name详细操作步骤

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

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

  • 根据obj指针所指向的集合元素, 对数组进行字符串排序

    • 被排序到数组索引0位置订单是”jack”元素

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

    • 被培训到数组索引2为止的是”tom”元素

  • 遍历数组, 根据数组项obj指针所指向的结合元素, 以及GET选项所给定的*-name模式, 查找对应的键

    • 对于”jack”元素和*-name模式, 查找程序返回键jack-name

    • 对于”peter”元素和*-name模式, 查找程序返回键peter-name

    • 对于”tom”元素和*-name模式, 查找程序返回键tom-name

  • 遍历查找程序返回的三个键, 并向客户端返回他们的值

    • 首先返回的是”jack-name”键的值”Jack Snow”

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

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

STORE 选项的实现

在默认情况下, Sort命令只向客户端返回排序结果, 而不是保存排序结果:

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

redis> SORT students ALPHA STORE sorted_students
redis> LRANGE sorted_students 0 -1

 

服务器执行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命令的执行过程可以分为以下四步:

  • 排序: 在这一步, 命令会使用ALPHA,ASC,DESC,BY这几个选项, 对输入键进行阿皮序, 并得到一个排序结果集

  • 限制排序结果的长度: 在这一步, 命令会使用LIMIT选项，对排序结果集的长度进行限制, 只有limit选项指定的那部分元素会被保留在排序结果集中

  • 获取外部键: 在这一步, 命令会使用GET选项, 根据排序结果集中的元素, 以及GET选项指定的模式, 查找并获取指定键的值, 并用这些值来作为新的排序结果集

  • 保存排序结果集: 在这一步, 命令会使用STORE选项, 将排序结果集保存到指定的键上面

  • 向客户端返回排序结果集: 在最后一步, 命令遍历排序结果集, 并以此向客户端返回排序结果集中的元素.

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>

  • 最后, 命令遍历排序结果集, 将结果集中的元素依次返回给客户端

选项的摆放顺序

调用SORT命令时, 除了GET选项之外, 改变选项的拜访顺序并不会影响SORT命令执行这些选项的顺序.

不过, 如果命令包含了多个GET选项, 那么在调整选项的位置时, 我们必须要争多个GET选项的摆放顺序不变, 这才可以让排序结果保持不变.

SORT <key> STORE <store_key> GET <pattern-a> GET <pattern-b>
​
SORT <key> STORE <store_key> GET <pattern-b> GET <pattern-a>
这两个语句会产生不一样的结果。

NOTE: 因此在调整SORT命令各个选项的摆放顺序时, 必须对GET选项的顺序小心处理

相关文章：

  1. redis持久化
  2. redis AOF持久化实现原理
  3. REDIS数据结构-集合对象(Set)
  4. REDIS分布式实现-复制
Avatar photo

专注着

一个奋斗在编程路上的小伙

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注