探索Redis设计与实现7:Redis内部数据结构详解——intset

  • 时间:
  • 浏览:0
  • 来源:UU直播快三_UU直播快3平台

Redis底下使用intset是为了实现集合(set)这名对外的数据价值形式。set价值形式这名于数学上的集合的概念,它含有的元素无序,且必须重复。Redis里的set价值形式还实现了基础的集合并、交、差的操作。与Redis对外暴露的其它数据价值形式这名,set的底层实现,随着元素类型算不算整型以及加上的元素的数目多少,而有所变化。概括来讲,当set中加上的元素全部需用整型且元素数目较少时,set使用intset作为底层数据价值形式,否则,set使用dict作为底层数据价值形式。

系列下一篇待续,敬请期待。

第二种算法:

这名人 前面提到过,set的底层实现,随着元素类型算不算整型以及加上的元素的数目多少,而有所变化。这名,具体到上述命令的执行过程中,集合s1的底层数据价值形式会居于如下变化:

intset的数据价值形式定义如下(出自intset.h和intset.c):

在上图中:

 2016-11-22

关于以上代码,这名人 需用注意的地方包括:

这名人 知道,dict是另有一3个 多用于维护key和value映射关系的数据价值形式,必须当set底层用dict表示的前一天,它的key和value分别是有哪些呢?实际上,key否则要加上的集合元素,而value是NULL。

计算交集的过程共不需要 否分为三每段:

注:本文讨论的代码实现基于Redis源码的3.2分支。

各个字段含义如下:

这名人 在这里简要介绍一下另有一3个 多算法的实现思路。

intsetFind的关键代码如下所示(出自intset.c):

计算差集有这名可能的算法,它们的时间复杂度有所区别。

在本文中这名人 将大体分成另有一3个 多每段进行介绍:

要理解intset的这名实现细节,只需用关注intset的另有一3个 多关键操作基本就还都可否了:查找(intsetFind)和加上(intsetAdd)元素。

底下有有哪些命令的含义:

这名人 在讨论中需用涉及到另有一3个 多Redis配置(在redis.conf中的ADVANCED CONFIG每段):

下图给出了另有一3个 多加上数据的具体例子(点击看大图)。

为了更好地理解Redis对外暴露的set数据价值形式,这名人 先看一下set的这名关键的命令。下面是这名命令举例:

本文是《Redis内部内部结构数据价值形式详解》系列的第七篇。在本文中,这名人 围绕另有一3个 多Redis的内部内部结构数据价值形式——intset展开讨论。

对于小集合使用intset来存储,主要的愿因 是节省内存。很重是当存储的元素个数较少的前一天,dict所带来的内存开销要大得多(含有另有一3个 多哈希表、链表指针以及大量的其它元数据)。很多,当存储大量的小集合否则集合元素全部需用数字的前一天,用intset能节省下一笔可观的内存空间。

在计算差集的开使了了每段,会先分别估算一下这名算法预期的时间复杂度,否则选者复杂度低的算法来进行运算。还有两点需用注意:

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

intset与ziplist相比:

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

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

intset顾名思义,是由整数组成的集合。实际上,intset是另有一3个 多由整数组成的有序集合,从而便于在底下进行二分查找,用于快速地判断另有一3个 多元素算不算属于这名集合。它在内存分配上与ziplist这名这名,是连续的一整块内存空间,否则对于大整数和小整数(按绝对值)采取了不同的编码,尽量对内存的使用进行了优化。

Redis set的并、交、差算法的实现代码,在t_set.c中。其中计算交集调用的是sinterGenericCommand,计算并集和差集调用的是sunionDiffGenericCommand。它们都能一块儿对多个(还都可否多于另有一3个 多)集合进行运算。当对多个集合进行差集运算时,它表达的含义是:用第另有一3个 多集合与第3个集合做差集,所得结果再与第另有一3个 多集合做差集,依次向后类推。

计算并集最简单,只需用遍历所有集合,将每另有一3个 多元素都加上到最后的结果集合中。向集合中加上元素会自动去重。

除了前面提到的可能加上非数字元素造成集合底层由intset转成dict之外,还有这名具体情况可能造成这名转换:

                     

实际上,从时间复杂度上比较,intset的平均具体情况是必须dict性能高的。以查找为例,intset是O(log n)的,而dict还都可否认为是O(1)的。否则,可能使用intset的前一天集合元素个数比较少,很多这名影响不大。

微信公众号【黄小斜】大厂线程池池员,互联网行业新知,终身学习践行者。关注后回复「Java」、「Python」、「C++」、「大数据」、「机器学习」、「算法」、「AI」、「Android」、「前端」、「iOS」、「考研」、「BAT」、「校招」、「笔试」、「面试」、「面经」、「计算机基础」、「LeetCode」 等关键字还都可否获取对应的免费学习资料。 

关于以上代码,这名人 需用注意的地方包括:

需用注意的是,上述第3步在集合中进行查找,对于intset和dict的存储来说时间复杂度分别是O(log n)和O(1)。但可能必须小集合才使用intset,很多还都可否粗略地认为intset的查找也是常数时间复杂度的。否则,如Redis官方文档上所说(http://redis.io/commands/sinter),sinter命令的时间复杂度为:

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

第这名算法:

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

intsetAdd的关键代码如下所示(出自intset.c):

其中需用注意的是,intset可能会随着数据的加上而改变它的数据编码:

这名算法的时间复杂度为O(N*M),其中N是第另有一3个 多集合的元素个数,M是集合数目。

可能要遍历所有集合的每个元素,很多Redis官方文档给出的sunion命令的时间复杂度为(http://redis.io/commands/sunion):