有序集合对象

ziplist 编码的有序集合对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员（member），而第二个元素则保存元素的分值（score）。

压缩列表内的集合元素按分值从小到大进行排序，分值较小的元素被放置在靠近表头的方向，而分值较大的元素则被放置在靠近表尾的方向。

举个例子，如果我们执行以下 ZADD 命令，那么服务器将创建一个有序集合对象作为 price 键的值：

如果 price 键的值对象使用的是 ziplist 编码，那么这个值对象将会是图 8-14 所示的样子，而对象所使用的压缩列表则会是 8-15 所示的样子。

skiplist 编码的有序集合对象使用 zset 结构作为底层实现，一个 zset 结构同时包含一个字典和一个跳跃表：

zset 结构中的 zsl 跳跃表按分值从小到大保存了所有集合元素，每个跳跃表节点都保存了一个集合元素：跳跃表节点的 object 属性保存了元素的成员，而跳跃表节点的 score 属性则保存了元素的分值。通过这个跳跃表，程序可以对有序集合进行范围型操作，比如 ZRANK 、 ZRANGE 等命令就是基于跳跃表 API 来实现的。

有序集合每个元素的成员都是一个字符串对象，而每个元素的分值都是一个 double 类型的浮点数。值得一提的是，虽然 zset 结构同时使用跳跃表和字典来保存有序集合元素，但这两种数据结构都会通过指针来共享相同元素的成员和分值，所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员或者分值，也不会因此而浪费额外的内存。

为什么有序集合需要同时使用跳跃表和字典来实现？

在理论上来说，有序集合可以单独使用字典或者跳跃表的其中一种数据结构来实现，但无论单独使用字典还是跳跃表，在性能上对比起同时使用字典和跳跃表都会有所降低。

举个例子，如果我们只使用字典来实现有序集合，那么虽然以 O(1) 复杂度查找成员的分值这一特性会被保留，但是，因为字典以无序的方式来保存集合元素，所以每次在执行范围型操作 ——比如 ZRANK 、 ZRANGE 等命令时，程序都需要对字典保存的所有元素进行排序，完成这种排序需要至少 O(N \log N) 时间复杂度，以及额外的 O(N) 内存空间（因为要创建一个数组来保存排序后的元素）。

另一方面，如果我们只使用跳跃表来实现有序集合，那么跳跃表执行范围型操作的所有优点都会被保留，但因为没有了字典，所以根据成员查找分值这一操作的复杂度将从 O(1) 上升为 O(\log N) 。

因为以上原因，为了让有序集合的查找和范围型操作都尽可能快地执行，Redis 选择了同时使用字典和跳跃表两种数据结构来实现有序集合。

举个例子，如果前面 price 键创建的不是 ziplist 编码的有序集合对象，而是 skiplist 编码的有序集合对象，那么这个有序集合对象将会是图 8-16 所示的样子，而对象所使用的 zset 结构将会是图 8-17 所示的样子。

注意

为了展示方便，图 8-17 在字典和跳跃表中重复展示了各个元素的成员和分值，但在实际中，字典和跳跃表会共享元素的成员和分值，所以并不会造成任何数据重复，也不会因此而浪费任何内存。

当有序集合对象可以同时满足以下两个条件时，对象使用 ziplist 编码：

注意

以上两个条件的上限值是可以修改的，具体请看配置文件中关于 zset-max-ziplist-entries 选项和 选项的说明。

对于使用 ziplist 编码的有序集合对象来说，当使用 ziplist 编码所需的两个条件中的任意一个不能被满足时，程序就会执行编码转换操作，将原本储存在压缩列表里面的所有集合元素转移到 zset 结构里面，并将对象的编码从 ziplist 改为 skiplist 。

以下代码展示了有序集合对象因为包含了过多元素而引发编码转换的情况：

以下代码则展示了有序集合对象因为元素的成员过长而引发编码转换的情况：

有序集合命令的实现

表 8-11 有序集合命令的实现方法