Redis数据结构对象之集合对象和有序集合对象

集合对象

集合对象的编码可以是intset或者hashtable.

概述

intset编码的集合对象使用整数集合作为底层实现，集合对象包含的所有元素都被保存在整数集合里面。

另一方面，hashtable编码的集合对象使用字典作为底层实现，字典的每个键都是一个字符串对象，每个字符串对象包含了一个集合对象，而字典的值则全部被设置为NULL.

例子

• 举个例子。以下代码创建一个如图所示的intset编码集合对象

127.0.0.1:6379> SADD numbers 1 3 5
(integer) 3

• 举个例子，以下代码创建一个如图所示的hashtable编码集合对象

127.0.0.1:6379> SADD fruits "apple" "banana" "cherry"
(integer) 3

编码的转换。

当集合对象可以同时满足以下两个条件时，对象使用intset编码:

• 1.集合对象保存的所有元素都是整数值
• 2.集合对象保存的元素不超过512个
  不能满足中两个条件的集合对象需要使用hashtable编码

对于使用intset编码的集合对象来说，当使用intset编码所需的两个条件的任意一个不能被满足时，就会执行对象的编码转换操作，原本保存在整数集合中的所有元素都会被转移并保存到字典里面，并且对象的编码也会从intset变为hashtable

注意：

第二个条件的上限值是可以修改的，具体请看配置文件中关于set-max-intset-entries选项的说明

例子

• 举个例子，以下代码创建了一个只包含整数的集合对象，该对象的编码为intset:

127.0.0.1:6379> SADD numbers 1 3 5
(integer) 3

不过，只要我们向这个只包含整数元素的集合对象添加一个字符串元素，集合对象的编码转移操作就会被执行:

127.0.0.1:6379> SADD numbers "seven"
(integer) 1
127.0.0.1:6379> OBJECT ENCODING numbers
"hashtable"

除此之外，如果我们创建一个包含512个整数元素的集合对象，那么对象的编码应该会是intset:

127.0.0.1:6379> EVAL "for i=1, 512 do redis.call('SADD', KEYS[1], i) end" 1 integers
(nil)
127.0.0.1:6379> SCARD integers
(integer) 512

但是我们再向集合添加一个新的元素，使得整个元素的元素数量变成513，那么对象的编码转换操作就会被执行:

127.0.0.1:6379> SADD integers 513
(integer) 1
127.0.0.1:6379> OBJECT ENCODING integers
"hashtable"

有序集合对象

有序集合的编码可以是ziplist或者skiplist。

概述

ziplist

ziplist编码的有序集合对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员(member)，而第二个元素则保存元素的分值(score).压缩列表
内的集合元素按分值从小到大进行排序，分值较小的元素被放置在表头的位置(相对分值节点来说)，而分值较大的元素则被放置在靠近表尾的位置。

例子

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

127.0.0.1:6379> ZADD price 8.5 apple 50 banana 6.0 cherry
(integer) 3

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

skiplist

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

typedef struct zset{zskiplist *zsl;dict * dict;
}zset

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

除此之外,zset结构中的dict字典为有序集合创建了一个从成员到分值的映射，字典中的每个键值对都保存了一个集合元素:字典的键保存了元素的成员，而字典的值则保存了元素的分值。通过这个字典，程序可以用O(1)
复杂度查找给定成员的分值，ZSCORE命令就是根据这一特性实现的，而很多其他有序集合命令都在实现的内部用到了这一特性。
有序集合每个元素都是一个字符串对象，而每个元素的分值都是一个double类型的浮点数。值得一提的是，虽然zset结构同时使用跳跃表和字典来保存有序集合的元素，但这两种数据结构都会通过指针来共享相同的成员和分值，所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员或分值，也不会因此而浪费额外的内存

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

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

• 举个例子，如果只是用字典来实现有序集合，虽然以O(1)的复杂度查找成员的分值这一特性会被保留，但是字典以无须的方式来保存集合元素，所以每次在执行范围型操作——比如ZRANK，ZRANGE等命令时，程序都需要对字典保存的所有元素进行排序，完成这种排序需要至少O(NlogN)时间复杂度，以及额外的O(N)内存空间(因为要创建一个数组来保存排序后的元素)。另一方面，如果只使用跳跃表来实现有序集合，那么跳跃表执行范围型操作的所有优点都会被保留，但因为没有了字典，所以根据成员查找分值这一操作的复杂度将从O(1)上升为O(logN)。因为以上原因，为了让有序集合的查找范围和范围型操作都尽可能快地执行，Redis选择了同时使用字典和跳跃表两种数据结构来实现有序集合

例子

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

注意:

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

编码的转换

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

• 1.有序集合保存的元素数量小于128个
• 2.有序集合保存的所有元素成员的长度都小于64字节
  不能满足以上两个条件的有序集合对象将使用skiplist编码

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

例子

• 举个例子,以下代码展示了有序集合因为包含了过多元素而引发编码转换的情况:

// 对象包含了128个元素
127.0.0.1:6379> EVAL "for i=1, 128 do redis.call('ZADD', KEYS[1],i,i) end" 1 numbers
(nil)
127.0.0.1:6379> ZCARD numbers
(integer) 128
127.0.0.1:6379> OBJECT ENCODING numbers
"ziplist"
// 再添加一个新元素
127.0.0.1:6379> ZADD numbers 3.14 pi
(integer) 1
// 对象数量变为129个
127.0.0.1:6379> ZCARD numbers
(integer) 129
// 编码已改变
127.0.0.1:6379> OBJECT ENCODING numbers
"skiplist"

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

// 向有序集合添加一个成员只有三字节长的元素
127.0.0.1:6379> ZADD blah 1.0 www
(integer) 1
127.0.0.1:6379> OBJECT ENCODING blah
"ziplist"
// 向有序集合添加一个成员为66字节长的元素
ZADD blah 2.0 ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
// 编码已改变
127.0.0.1:6379> OBJECT ENCODING blah
"skiplist"

注意:

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