Redis数据结构之intset（2）

本文及后续文章，Redis版本均是v3.2.8

上文我们说到intset整型集合的数据结构定义即元素的添加和查询操作，本文我们来看下Redis暴露给外面使用的Set集合，先通过一些基本的命令回顾下set

一、set底层数据结构

我们查阅Redis Set命令文档知道：

sadd用于分别向集合 myset和myset2中添加元素。添加的元素既有数字，也有非数字（”a”和”b”）。
sismember用于判断指定的元素是否在集合内存在。
sinter, sunion和sdiff分别用于计算集合的交集、并集和差集。

我们上文提到，set的底层实现，随着元素类型是否是整型以及添加的元素的数目多少，而有所变化。如，上述命令的执行过程中，集合myset的底层数据结构会发生如下变化：

在开始执行完sadd myset 1 2之后，由于添加的都是比较小的整数，所以myset底层是一个intset，其数据编码encoding = 2。
在执行完sadd myset 10000之后，myset底层仍然是一个intset，但其数据编码encoding从2升级到了4。
在执行完sadd myset a b之后，由于添加的元素不再是数字，myset底层的实现会转成一个dict。

我们知道，dict是一个用于维护key和value映射关系的数据结构，那么当set底层用dict表示的时候，它的key和value分别是什么呢？实际上，key就是要添加的集合元素，而value是NULL。

除了前面提到的由于添加非数字元素造成集合底层由intset转成dict之外，还有两种情况可能造成这种转换：

添加了一个数字，但它无法用64bit的有符号数来表达。intset能够表达的最大的整数范围为-264~264-1，因此，如果添加的数字超出了这个范围，这也会导致intset转成dict。
添加的集合元素个数超过了set-max-intset-entries配置的值的时候，也会导致intset转成dict（具体的触发条件参见t_set.c中的setTypeAdd相关代码）。

对于小集合使用intset来存储，主要的原因是节省内存。特别是当存储的元素个数较少的时候，dict所带来的内存开销要大得多（包含两个哈希表、链表指针以及大量的其它元数据）。所以，当存储大量的小集合而且集合元素都是数字的时候，用intset能节省内存空间。

实际上，从时间复杂度上比较，intset的平均情况是没有dict性能高的。以查找为例，intset是O(log n)的，而dict可以认为是O(1)的。但是，由于使用intset的时候集合元素个数比较少，所以这个影响不大。

二、Redis set的并、交、差算法

Redis set的并、交、差算法的实现代码，在t_set.c中。其中计算交集调用的是sinterGenericCommand，计算并集和差集调用的是sunionDiffGenericCommand。它们都能同时对多个（可以多于2个）集合进行运算。当对多个集合进行差集运算时，它表达的含义是：用第一个集合与第二个集合做差集，所得结果再与第三个集合做差集，依次向后类推。

我们在这里简要介绍一下三个算法的实现思路。

交集

计算交集的过程大概可以分为三部分：

检查各个集合，对于不存在的集合当做空集来处理。一旦出现空集，则不用继续计算了，最终的交集就是空集。
对各个集合按照元素个数由少到多进行排序。这个排序有利于后面计算的时候从最小的集合开始，需要处理的元素个数较少。
对排序后第一个集合（也就是最小集合）进行遍历，对于它的每一个元素，依次在后面的所有集合中进行查找。只有在所有集合中都能找到的元素，才加入到最后的结果集合中。

需要注意的是，上述第3步在集合中进行查找，对于intset和dict的存储来说时间复杂度分别是O(log n)和O(1)。但由于只有小集合才使用intset，所以可以粗略地认为intset的查找也是常数时间复杂度的。因此，如Redis官方文档上所说（http://redis.io/commands/sinter），sinter命令的时间复杂度为：

O(N*M) worst case where N is the cardinality of the smallest set and M is the number of sets.

并集

计算并集最简单，只需要遍历所有集合，将每一个元素都添加到最后的结果集合中。向集合中添加元素会自动去重。

由于要遍历所有集合的每个元素，所以Redis官方文档给出的sunion命令的时间复杂度为（http://redis.io/commands/sunion）：

O(N) where N is the total number of elements in all given sets.

注意，这里同前面讨论交集计算一样，将元素插入到结果集合的过程，忽略intset的情况，认为时间复杂度为O(1)。

差集

计算差集有两种可能的算法，它们的时间复杂度有所区别。

第一种算法：

对第一个集合进行遍历，对于它的每一个元素，依次在后面的所有集合中进行查找。只有在所有集合中都找不到的元素，才加入到最后的结果集合中。

这种算法的时间复杂度为O(N*M)，其中N是第一个集合的元素个数，M是集合数目。

第二种算法：

将第一个集合的所有元素都加入到一个中间集合中。
遍历后面所有的集合，对于碰到的每一个元素，从中间集合中删掉它。
最后中间集合剩下的元素就构成了差集。

这种算法的时间复杂度为O(N)，其中N是所有集合的元素个数总和。

在计算差集的开始部分，会先分别估算一下两种算法预期的时间复杂度，然后选择复杂度低的算法来进行运算。还有两点需要注意：

在一定程度上优先选择第一种算法，因为它涉及到的操作比较少，只用添加，而第二种算法要先添加再删除。
如果选择了第一种算法，那么在执行该算法之前，Redis的实现中对于第二个集合之后的所有集合，按照元素个数由多到少进行了排序。这个排序有利于以更大的概率查找到元素，从而更快地结束查找。

对于sdiff的时间复杂度，Redis官方文档（http://redis.io/commands/sdiff）只给出了第二种算法的结果，是不准确的。

三、基本命令

下表列出了与集合相关的一些基本命令。

序号	命令	说明
1	SADD key member1 [member2]	将一个或多个成员添加到集合
2	SCARD key	获取集合中的成员数
3	SDIFF key1 [key2]	减去多个集合
4	SDIFFSTORE destination key1 [key2]	减去多个集并将结果集存储在键中
5	SINTER key1 [key2]	相交多个集合
6	SINTERSTORE destination key1 [key2]	交叉多个集合并将结果集存储在键中
7	SISMEMBER key member	判断确定给定值是否是集合的成员
8	SMOVE source destination member	将成员从一个集合移动到另一个集合
9	SPOP key	从集合中删除并返回随机成员
10	SRANDMEMBER key [count]	从集合中获取一个或多个随机成员
11	SREM key member1 [member2]	从集合中删除一个或多个成员
12	SUNION key1 [key2]	添加多个集合
13	SUNIONSTORE destination key1 [key2]	添加多个集并将结果集存储在键中
14	SSCAN key cursor [MATCH pattern] [COUNT count]	递增地迭代集合中的元素

参考

Reids设计与实现

--EOF--