第 21 章： 排序
SORT <key> 命令的实现
Redis 服务器在执行 SORT number 时创建的数据结构。
![digraph {
rankdir = LR;
node [shape = record];
subgraph cluster_array {
style = invis;
array [label = " array | { <array0> array[0] \n redisSortObject | { <obj0> obj | u } } | { <array1> array[1] \n redisSortObject | { <obj1> obj | u } } | { <array2> array[2] \n redisSortObject | { <obj2> obj | u } } "];
}
label = "\n 图 21-1 命令为排序 numbers 列表而创建的数组";
}](_images/graphviz-22a4a72a7775327e441c1b6c45780ada43499e93.png)
![digraph {
rankdir = LR;
node [shape = record];
subgraph cluster_numbers {
label = "numbers 链表"
style = dashed;
one [label = "StringObject \n \"1\""];
two [label = "StringObject \n \"2\""];
three [label = "StringObject \n \"3\""];
three -> one -> two;
}
subgraph cluster_array {
style = invis;
array [label = " array | { <array0> array[0] \n redisSortObject | { <obj0> obj | u } } | { <array1> array[1] \n redisSortObject | { <obj1> obj | u } } | { <array2> array[2] \n redisSortObject | { <obj2> obj | u } } "];
}
array:obj0 -> three;
array:obj1 -> one;
array:obj2 -> two;
label = "\n 图 21-2 将 obj 指针指向列表的各个项";
}](_images/graphviz-f712f7955cf02d331aa0d749b787fd34d224d554.png)
![digraph {
rankdir = LR;
node [shape = record];
subgraph cluster_numbers {
label = "numbers 链表"
style = dashed;
one [label = "StringObject \n \"1\""];
two [label = "StringObject \n \"2\""];
three [label = "StringObject \n \"3\""];
three -> one -> two;
}
subgraph cluster_array {
style = invis;
array [label = " array | { <array0> array[0] \n redisSortObject | { <obj0> obj | u.score \n 3.0 } } | { <array1> array[1] \n redisSortObject | { <obj1> obj | u.score \n 1.0 } } | { <array2> array[2] \n redisSortObject | { <obj2> obj | u.score \n 2.0 } } "];
}
array:obj0 -> three;
array:obj1 -> one;
array:obj2 -> two;
label = "\n 图 21-3 设置数组项的 u.score 属性";
}](_images/graphviz-62a7f2ef499dbbd701168223a41fecbb1afbaa47.png)
![digraph {
rankdir = LR;
node [shape = record];
subgraph cluster_numbers {
label = "numbers 链表"
style = dashed;
one [label = "StringObject \n \"1\""];
two [label = "StringObject \n \"2\""];
three [label = "StringObject \n \"3\""];
three -> one -> two;
}
subgraph cluster_array {
style = invis;
array [label = " array | { <array0> array[0] \n redisSortObject | { <obj0> obj | u.score \n 1.0 } } | { <array1> array[1] \n redisSortObject | { <obj1> obj | u.score \n 2.0 } } | { <array2> array[2] \n redisSortObject | { <obj2> obj | u.score \n 3.0 } } "];
}
array:obj0 -> one;
array:obj1 -> two;
array:obj2 -> three;
label = "\n 图 21-4 排序后的数组";
}](_images/graphviz-9cfef9e2ba5ce22032a12b9c9632854b94cdf6cb.png)
ALPHA 选项的实现
服务器在执行 SORT fruits ALPHA 时创建的数据结构。
![digraph {
rankdir = LR;
node [shape = record];
subgraph cluster_fruits {
label = "fruits 集合";
style = dashed;
apple [label = "StringObject \n \"apple\""];
banana [label = "StringObject \n \"banana\""];
cherry [label = "StringObject \n \"cherry\""];
apple -> cherry -> banana [style = invis];
}
subgraph cluster_array {
style = invis;
array [label = " array | { <array0> array[0] \n redisSortObject | { <obj0> obj | u } } | { <array1> array[1] \n redisSortObject | { <obj1> obj | u } } | { <array2> array[2] \n redisSortObject | { <obj2> obj | u } } "];
}
array:obj0 -> apple;
array:obj1 -> cherry;
array:obj2 -> banana;
label = "\n 图 21-5 将 obj 指针指向集合的各个元素";
}](_images/graphviz-f1e2ca8f10a3809ad0f30d2401c5e676c136cab9.png)
![digraph {
rankdir = LR;
node [shape = record];
subgraph cluster_fruits {
label = "fruits 集合";
style = dashed;
apple [label = "StringObject \n \"apple\""];
banana [label = "StringObject \n \"banana\""];
cherry [label = "StringObject \n \"cherry\""];
apple -> cherry -> banana [style = invis];
}
subgraph cluster_array {
style = invis;
array [label = " array | { <array0> array[0] \n redisSortObject | { <obj0> obj | u } } | { <array1> array[1] \n redisSortObject | { <obj1> obj | u } } | { <array2> array[2] \n redisSortObject | { <obj2> obj | u } } "];
}
array:obj0 -> apple;
array:obj1 -> banana;
array:obj2 -> cherry;
label = "\n 图 21-6 按集合元素进行排序后的数组";
}](_images/graphviz-722130c084517ab4cf2acd4bcc4b791d63ca4a61.png)
ASC 选项和 DESC 选项的实现
图 21-7 展示了 SORT 命令在对 numbers 列表执行升序排序时所创建的数组。
![digraph {
rankdir = LR;
node [shape = record];
subgraph cluster_numbers {
label = "numbers 链表"
style = dashed
one [label = "StringObject \n \"1\""];
two [label = "StringObject \n \"2\""];
three [label = "StringObject \n \"3\""];
three -> one -> two;
}
subgraph cluster_array {
style = invis;
array [label = " array | { <array0> array[0] \n redisSortObject | { <obj0> obj | u.score \n 1.0 } } | { <array1> array[1] \n redisSortObject | { <obj1> obj | u.score \n 2.0 } } | { <array2> array[2] \n redisSortObject | { <obj2> obj | u.score \n 3.0 } } "];
}
array:obj0 -> one;
array:obj1 -> two;
array:obj2 -> three;
label = "\n 图 21-7 执行升序排序的数组";
}](_images/graphviz-c0bafde800e80b9431cf238c5b1ce3448d4b67ce.png)
图 21-8 展示了 SORT 命令在对 numbers 列表执行降序排序时所创建的数组。
![digraph {
rankdir = LR;
node [shape = record];
subgraph cluster_numbers {
label = "numbers 链表"
style = dashed;
one [label = "StringObject \n \"1\""];
two [label = "StringObject \n \"2\""];
three [label = "StringObject \n \"3\""];
three -> one -> two;
}
subgraph cluster_array {
style = invis;
array [label = " array | { <array0> array[0] \n redisSortObject | { <obj0> obj | u.score \n 3.0 } } | { <array1> array[1] \n redisSortObject | { <obj1> obj | u.score \n 2.0 } } | { <array2> array[2] \n redisSortObject | { <obj2> obj | u.score \n 1.0 } } "];
}
array:obj0 -> three;
array:obj1 -> two;
array:obj2 -> one;
label = "\n 图 21-8 执行降序排序的数组";
}](_images/graphviz-a423e61a9781f04afae9582bc9e9dda5dd6933d2.png)
BY 选项的实现
服务器在执行 SORT fruits BY *-price 时创建的数据结构。
![digraph {
rankdir = LR;
node [shape = record];
subgraph cluster_fruits {
label = "fruits 集合";
style = dashed;
apple [label = "StringObject \n \"apple\""];
banana [label = "StringObject \n \"banana\""];
cherry [label = "StringObject \n \"cherry\""];
apple -> cherry -> banana [style = invis];
}
subgraph cluster_array {
style = invis;
array [label = " array | { <array0> array[0] \n redisSortObject | { <obj0> obj | u } } | { <array1> array[1] \n redisSortObject | { <obj1> obj | u } } | { <array2> array[2] \n redisSortObject | { <obj2> obj | u } } "];
}
array:obj0 -> apple;
array:obj1 -> cherry;
array:obj2 -> banana;
label = "\n 图 21-9 将 obj 指针指向集合的各个元素";
}](_images/graphviz-cb92bf7952851453d485000ebbfa4170bfc4bcc7.png)
![digraph {
rankdir = LR;
node [shape = record];
subgraph cluster_fruits {
label = "fruits 集合";
style = dashed;
apple [label = "StringObject \n \"apple\""];
banana [label = "StringObject \n \"banana\""];
cherry [label = "StringObject \n \"cherry\""];
apple -> cherry -> banana [style = invis];
}
subgraph cluster_array {
style = invis;
array [label = " array | { <array0> array[0] \n redisSortObject | { <obj0> obj | u.score \n 8.0 } } | { <array1> array[1] \n redisSortObject | { <obj1> obj | u.score \n 7.0 } } | { <array2> array[2] \n redisSortObject | { <obj2> obj | u.score \n 5.5 } } "];
}
array:obj0 -> apple;
array:obj1 -> cherry;
array:obj2 -> banana;
label = "\n 图 21-10 根据权重键的值设置数组项的 u.score 属性";
}](_images/graphviz-dde4764d3a639aec7b42f6a5e3ea123ba03fd983.png)
![digraph {
rankdir = LR;
node [shape = record];
subgraph cluster_fruits {
label = "fruits 集合";
style = dashed;
apple [label = "StringObject \n \"apple\""];
banana [label = "StringObject \n \"banana\""];
cherry [label = "StringObject \n \"cherry\""];
apple -> cherry -> banana [style = invis];
}
subgraph cluster_array {
style = invis;
array [label = " array | { <array0> array[0] \n redisSortObject | { <obj0> obj | u.score \n 5.5 } } | { <array1> array[1] \n redisSortObject | { <obj1> obj | u.score \n 7.0 } } | { <array2> array[2] \n redisSortObject | { <obj2> obj | u.score \n 8.0 } } "];
}
array:obj0 -> banana;
array:obj1 -> cherry;
array:obj2 -> apple;
label = "\n 图 21-11 根据 u.score 属性进行排序之后的数组";
}](_images/graphviz-f02493e0d145bc8d64ab520d1fb37642d8cbceba.png)
带有 ALPHA 选项的 BY 选项的实现
服务器执行 SORT fruits BY *-id ALPHA 时创建的数据结构。
![digraph {
rankdir = LR;
node [shape = record];
subgraph cluster_fruits {
label = "fruits 集合";
style = dashed;
apple [label = "StringObject \n \"apple\""];
banana [label = "StringObject \n \"banana\""];
cherry [label = "StringObject \n \"cherry\""];
apple -> cherry -> banana [style = invis];
}
subgraph cluster_array {
style = invis;
array [label = " array | { <array0> array[0] \n redisSortObject | { <obj0> obj | u } } | { <array1> array[1] \n redisSortObject | { <obj1> obj | u } } | { <array2> array[2] \n redisSortObject | { <obj2> obj | u } } "];
}
array:obj0 -> apple;
array:obj1 -> cherry;
array:obj2 -> banana;
label = "\n 图 21-12 将 obj 指针指向集合的各个元素";
}](_images/graphviz-04597b79beabd7ff21f6feb147a5ec0874a3ad61.png)
![digraph {
rankdir = LR;
node [shape = record];
subgraph cluster_fruits {
label = "fruits 集合";
style = dashed;
apple [label = "StringObject \n \"apple\""];
banana [label = "StringObject \n \"banana\""];
cherry [label = "StringObject \n \"cherry\""];
apple -> cherry -> banana [style = invis];
}
subgraph cluster_array {
style = invis;
array [label = " array | { <array0> array[0] \n redisSortObject | { <obj0> obj | <cmpobj0> u.cmpobj } } | { <array1> array[1] \n redisSortObject | { <obj1> obj | <cmpobj1> u.cmpobj } } | { <array2> array[2] \n redisSortObject | { <obj2> obj | <cmpobj2> u.cmpobj } } "];
}
array:obj0 -> apple;
array:obj1 -> cherry;
array:obj2 -> banana;
apple_id [label = "StringObject \n \"FRUIT-25\""];
banana_id [label = "StringObject \n \"FRUIT-79\""];
cherry_id [label = "StringObject \n \"FRUIT-13\""];
array:cmpobj0 -> apple_id;
array:cmpobj1 -> cherry_id;
array:cmpobj2 -> banana_id;
label = "\n 图 21-13 将 u.cmpobj 指针指向权重键";
}](_images/graphviz-6b823356a83604f812ee6f2f8c758bbc7572183e.png)
![digraph {
rankdir = LR;
node [shape = record];
subgraph cluster_fruits {
label = "fruits 集合";
style = dashed;
apple [label = "StringObject \n \"apple\""];
banana [label = "StringObject \n \"banana\""];
cherry [label = "StringObject \n \"cherry\""];
apple -> cherry -> banana [style = invis];
}
subgraph cluster_array {
style = invis;
array [label = " array | { <array0> array[0] \n redisSortObject | { <obj0> obj | <cmpobj0> u.cmpobj } } | { <array1> array[1] \n redisSortObject | { <obj1> obj | <cmpobj1> u.cmpobj } } | { <array2> array[2] \n redisSortObject | { <obj2> obj | <cmpobj2> u.cmpobj } } "];
}
array:obj0 -> cherry;
array:obj1 -> apple;
array:obj2 -> banana;
apple_id [label = "StringObject \n \"FRUIT-25\""];
banana_id [label = "StringObject \n \"FRUIT-79\""];
cherry_id [label = "StringObject \n \"FRUIT-13\""];
array:cmpobj0 -> cherry_id;
array:cmpobj1 -> apple_id;
array:cmpobj2 -> banana_id;
label = "\n 图 21-14 按 u.cmpobj 所指向的字符串对象进行排序之后的数组";
}](_images/graphviz-ad361521ffb2340ac9672416ac0e40eb3ed34693.png)
LIMIT 选项的实现
服务器在执行 SORT alphabet ALPHA LIMIT 0 4 时创建的数据结构。
![digraph {
rankdir = LR;
subgraph cluster_alphabet {
label = "alphabet 集合\n";
style = dashed;
node [shape = box];
a [label = "StringObject \n \"a\""];
b [label = "StringObject \n \"b\""];
c [label = "StringObject \n \"c\""];
d [label = "StringObject \n \"d\""];
e [label = "StringObject \n \"e\""];
f [label = "StringObject \n \"f\""];
edge [style = invis];
d -> c -> a;
b -> f -> e;
}
array [label = " array | { array[0] \n redisSortObject | { <obj0> obj | u } } | { array[1] \n redisSortObject | { <obj1> obj | u } } | { array[2] \n redisSortObject | { <obj2> obj | u } } | { array[3] \n redisSortObject | { <obj3> obj | u } } | { array[4] \n redisSortObject | { <obj4> obj | u } } | { array[5] \n redisSortObject | { <obj5> obj | u } } ", shape = record];
edge [minlen = 2.0];
array:obj0 -> d;
array:obj1 -> c;
array:obj2 -> a;
array:obj3 -> b;
array:obj4 -> f;
array:obj5 -> e;
label = "\n 图 21-15 将 obj 指针指向集合的各个元素";
}](_images/graphviz-7bbf453dfc91a6d64b7054197fe517ee4adb4968.png)
![digraph {
rankdir = LR;
subgraph cluster_alphabet {
label = "alphabet 集合\n\n";
style = dashed;
node [shape = box];
a [label = "StringObject \n \"a\""];
b [label = "StringObject \n \"b\""];
c [label = "StringObject \n \"c\""];
d [label = "StringObject \n \"d\""];
e [label = "StringObject \n \"e\""];
f [label = "StringObject \n \"f\""];
edge [style = invis];
d -> c -> a;
b -> f -> e;
}
array [label = " array | { array[0] \n redisSortObject | { <obj0> obj | u } } | { array[1] \n redisSortObject | { <obj1> obj | u } } | { array[2] \n redisSortObject | { <obj2> obj | u } } | { array[3] \n redisSortObject | { <obj3> obj | u } } | { array[4] \n redisSortObject | { <obj4> obj | u } } | { array[5] \n redisSortObject | { <obj5> obj | u } } ", shape = record];
edge [minlen = 2.0];
array:obj0 -> a;
array:obj1 -> b;
array:obj2 -> c;
array:obj3 -> d;
array:obj4 -> e;
array:obj5 -> f;
label = "\n 图 21-16 排序后的数组";
}](_images/graphviz-8fe085fe8f59e25f561373a137619c64c48bc34d.png)
GET 选项的实现
服务器在执行 SORT students ALPHA GET *-name 时创建的数据结构。
![digraph {
rankdir = LR;
subgraph cluster_students {
label = "students 集合";
style = dashed;
node [shape = box];
peter [label = "StringObject \n \"peter\""];
jack [label = "StringObject \n \"jack\""];
tom [label = "StringObject \n \"tom\""];
peter -> jack -> tom [style = invis];
}
node [shape = record];
array [label = " array | { array[0] \n redisSortObject | { <obj0> obj | u } } | { array[1] \n redisSortObject | { <obj1> obj | u } } | { array[2] \n redisSortObject | { <obj2> obj | u } } "];
array:obj0 -> peter;
array:obj1 -> jack;
array:obj2 -> tom;
label = "\n 图 21-17 排序之前的数组";
}](_images/graphviz-18a12b2e02c9ce1249a3186b65e655f4aae74e79.png)
![digraph {
rankdir = LR;
subgraph cluster_students {
label = "students 集合";
style = dashed;
node [shape = box];
peter [label = "StringObject \n \"peter\""];
jack [label = "StringObject \n \"jack\""];
tom [label = "StringObject \n \"tom\""];
peter -> jack -> tom [style = invis];
}
node [shape = record];
array [label = " array | { array[0] \n redisSortObject | { <obj0> obj | u } } | { array[1] \n redisSortObject | { <obj1> obj | u } } | { array[2] \n redisSortObject | { <obj2> obj | u } } "];
array:obj0 -> jack;
array:obj1 -> peter;
array:obj2 -> tom;
label = "\n 图 21-18 排序之后的数组";
}](_images/graphviz-8b1ac497c2c430c3b893fb6f50223e9582e41e47.png)