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

  • 时间:
  • 浏览:2
  • 来源:大发快3官方网址—大发快3APP下载

intset的数据形态学 定义如下(出自intset.h和intset.c):

各个字段含义如下:

上面哪此命令的含义:

关于以上代码,我们我们还要注意的地方包括:

在计算差集的时候开始累积,会先分别估算一下并是否算法预期的时间错综复杂度,可是 选用错综复杂度低的算法来进行运算。还有两点还要注意:

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

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

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

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

第二种算法:

计算交集的过程大概也能分为三累积:

我们我们在讨论中总要涉及到一一四个多Redis配置(在redis.conf中的ADVANCED CONFIG累积):

 2016-11-22

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

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

intset与ziplist相比:

我们我们知道,dict是一一四个多用于维护key和value映射关系的数据形态学 ,这么当set底层用dict表示的时候 ,它的key和value分别是哪此呢?实际上,key可是 要加上的集合元素,而value是NULL。

除了前面提到的机会加上非数字元素造成集合底层由intset转成dict之外,还有并是否清况 机会造成什儿 转换:

计算差集有并是否机会的算法,它们的时间错综复杂度有所区别。

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

我们我们前面提到过,set的底层实现,随着元素类型是是是否整型以及加上的元素的数目几块,而有所变化。例如,具体到上述命令的执行过程中,集合s1的底层数据形态学 会趋于稳定如下变化:

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

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

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

关于以上代码,我们我们还要注意的地方包括:

为了更好地理解Redis对外暴露的set数据形态学 ,我们我们先看一下set的某些关键的命令。下面是某些命令举例:

要理解intset的某些实现细节,只还要关注intset的一一四个多关键操作基本就也能了:查找(intsetFind)和加上(intsetAdd)元素。

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

其中还要注意的是,intset机会会随着数据的加上而改变它的数据编码:

第并是否算法:

对于小集合使用intset来存储,主要的原因是节省内存。不怎么是当存储的元素个数较少的时候 ,dict所带来的内存开销要大得多(中含一一四个多哈希表、链表指针以及血块的其它元数据)。可是 ,当存储血块的小集合可是 集合元素全部都是数字的时候 ,用intset能节省下一笔可观的内存空间。

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

什儿 算法的时间错综复杂度为O(N*M),其中N是第一一四个多集合的元素个数,M是集合数目。

本文是《Redis组织组织结构数据形态学 详解》系列的第七篇。在本文中,我们我们围绕一一四个多Redis的组织组织结构数据形态学 ——intset展开讨论。

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

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

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

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

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

                     

在本文中我们我们将大体分成一一四个多累积进行介绍:

在上图中:

Redis上面使用intset是为了实现集合(set)什儿 对外的数据形态学 。set形态学 例如于数学上的集合的概念,它中含的元素无序,且只有重复。Redis里的set形态学 还实现了基础的集合并、交、差的操作。与Redis对外暴露的其它数据形态学 例如,set的底层实现,随着元素类型是是是否整型以及加上的元素的数目几块,而有所变化。概括来讲,当set中加上的元素全部都是整型且元素数目较少时,set使用intset作为底层数据形态学 ,可是 ,set使用dict作为底层数据形态学 。

实际上,从时间错综复杂度上比较,intset的平均清况 是这么dict性能高的。以查找为例,intset是O(log n)的,而dict也能认为是O(1)的。可是 ,机会使用intset的时候 集合元素个数比较少,可是 什儿 影响不大。