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

  • 时间:
  • 浏览:1
  • 来源:神彩UU直播现场_彩神UU直播现场官方

在计算差集的始于英文次要,会先分别估算一下并都不 算法预期的时间简化度,也不我选着简化度低的算法来进行运算。还有两点需要注意:

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

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

除了前面提到的也不我加在非数字元素造成集合底层由intset转成dict之外,还有并都不 情况报告也不我造成这种 转换:

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

                     

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

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

各个字段含义如下:

顶端那先 命令的含义:

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

实际上,从时间简化度上比较,intset的平均情况报告是越来越dict性能高的。以查找为例,intset是O(log n)的,而dict可不后能 认为是O(1)的。也不我,也不我使用intset的前一天集合元素个数比较少,这种 这种 影响不大。

计算差集有并都不 也不我的算法,它们的时间简化度有所区别。

计算交集的过程相当于可不后能 分为三次要:

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

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

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

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

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

也不我要遍历所有集合的每个元素,这种 Redis官方文档给出的sunion命令的时间简化度为(http://redis.io/commands/sunion):

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

本文是《Redis实物数据形状详解》系列的第七篇。在本文中,大伙围绕一一一有一个 Redis的实物数据形状——intset展开讨论。

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

intset与ziplist相比:

第并都不 算法:

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

在上图中:

大伙知道,dict是一一一有一个 用于维护key和value映射关系的数据形状,越来越当set底层用dict表示的前一天,它的key和value分别是那先 呢?实际上,key也不我要加在的集合元素,而value是NULL。

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

Redis顶端使用intset是为了实现集合(set)这种 对外的数据形状。set形状同类 于数学上的集合的概念,它中有 的元素无序,且可不后能 重复。Redis里的set形状还实现了基础的集合并、交、差的操作。与Redis对外暴露的其它数据形状同类 ,set的底层实现,随着元素类型是是不是整型以及加在的元素的数目几条,而有所变化。概括来讲,当set中加在的元素都不 整型且元素数目较少时,set使用intset作为底层数据形状,也不我,set使用dict作为底层数据形状。

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

第二种算法:

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

大伙前面提到过,set的底层实现,随着元素类型是是不是整型以及加在的元素的数目几条,而有所变化。同类 ,具体到上述命令的执行过程中,集合s1的底层数据形状会所处如下变化:

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

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

对于小集合使用intset来存储,主要的意味着 是节省内存。一阵一阵是当存储的元素个数较少的前一天,dict所带来的内存开销要大得多(中有 一一有一个 哈希表、链表指针以及小量的其它元数据)。这种 ,当存储小量的小集合也不我集合元素都不 数字的前一天,用intset能节省下一笔可观的内存空间。

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

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

其中需要注意的是,intset也不我会随着数据的加在而改变它的数据编码:

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

 2016-11-22

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

要理解intset的这种 实现细节,只需要关注intset的一一有一个 关键操作基本就可不后能 了:查找(intsetFind)和加在(intsetAdd)元素。