第 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 列表而创建的数组";

}
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 指针指向列表的各个项";

}
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 属性";

}
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    排序后的数组";

}

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 指针指向集合的各个元素";

}
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    按集合元素进行排序后的数组";

}

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    执行升序排序的数组";

}

图 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    执行降序排序的数组";

}

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 指针指向集合的各个元素";

}
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 属性";

}
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 属性进行排序之后的数组";

}

带有 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 指针指向集合的各个元素";

}
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 指针指向权重键";

}
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 所指向的字符串对象进行排序之后的数组";

}

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 指针指向集合的各个元素";

}
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    排序后的数组";

}

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    排序之前的数组";

}
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    排序之后的数组";

}