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

  • 时间:
  • 浏览:2
  • 来源:大发5分6合APP下载_大发5分6合APP官网

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

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

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

大伙知道,dict是有另1个用于维护key和value映射关系的数据底部形态,没有 当set底层用dict表示的很久,它的key和value分别是什么呢?实际上,key可是要添加的集合元素,而value是NULL。

实际上,从时间僵化 度上比较,intset的平均清况 是没有 dict性能高的。以查找为例,intset是O(log n)的,而dict还可以认为是O(1)的。很久,原因着使用intset的很久集合元素个数比较少,统统什儿 影响不大。

大伙在讨论中后要 涉及到有另1个Redis配置(在redis.conf中的ADVANCED CONFIG次要):

                     

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

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

大伙前面提到过,set的底层实现,随着元素类型否有整型以及添加的元素的数目哪几块,而有所变化。类事,具体到上述命令的执行过程中,集合s1的底层数据底部形态会处于如下变化:

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

关于以上代码,大伙都要注意的地方包括:

计算差集有并就有原因着的算法,它们的时间僵化 度有所区别。

大伙在这里简要介绍一下有另1个算法的实现思路。

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

第并就有算法:

关于以上代码,大伙都要注意的地方包括:

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

上边什么命令的含义:

为了更好地理解Redis对外暴露的set数据底部形态,大伙先看一下set的什儿 关键的命令。下面是什儿 命令举例:

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

要理解intset的什儿 实现细节,只都要关注intset的有另1个关键操作基本就还可以了:查找(intsetFind)和添加(intsetAdd)元素。

下图给出了有另1个添加数据的具体例子(点击看大图)。

 2016-11-22

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

什儿 算法的时间僵化 度为O(N*M),其中N是第有另1个集合的元素个数,M是集合数目。

其中都要注意的是,intset原因着会随着数据的添加而改变它的数据编码:

在计算差集的刚开始次要,会先分别估算一下并就有算法预期的时间僵化 度,很久选者僵化 度低的算法来进行运算。还有两点都要注意:

intset与ziplist相比:

除了前面提到的原因着添加非数字元素造成集合底层由intset转成dict之外,还有并就有清况 原因着造成什儿 转换:

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

计算交集的过程离米 还可以分为三次要:

第二种算法:

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

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

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

对于小集合使用intset来存储,主要的原因着是节省内存。不得劲是当存储的元素个数较少的很久,dict所带来的内存开销要大得多(包蕴含另1个哈希表、链表指针以及絮状的其它元数据)。统统,当存储絮状的小集合很久集合元素后要 数字的很久,用intset能节省下一笔可观的内存空间。

原因着要遍历所有集合的每个元素,统统Redis官方文档给出的sunion命令的时间僵化 度为(http://redis.io/commands/sunion):

本文是《Redis外部数据底部形态详解》系列的第七篇。在本文中,大伙围绕有另1个Redis的外部数据底部形态——intset展开讨论。

都要注意的是,上述第3步在集合中进行查找,对于intset和dict的存储来说时间僵化 度分别是O(log n)和O(1)。但原因着还可以了小集合才使用intset,统统还可以粗略地认为intset的查找也是常数时间僵化 度的。很久,如Redis官方文档上所说(http://redis.io/commands/sinter),sinter命令的时间僵化 度为:

各个字段含义如下:

在上图中:

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

在本文中大伙将大体分成有另1个次要进行介绍: