Redis数据结构之整数集合

机会只留给那些准备充分的人

Posted by irving.gx on April 15, 2020

数据结构

整数集合intset也是redis的一种基本数据结构,其结构定义在src/intset.h文件当中,我们来看下其代码实现:

可以看到整数集合的定义很简单,主要有三个成员变量,分别存储的是编码方式,整数集合包含的元素数量以及包含的元素是什么。整数集合的特点是集合中 不包含重复元素,并且其中的元素从小到大有序排列。

    我们再来看一下整数集合的几种编码方式,我们在src/intset.c当中看到了下列定义

可以看到整数集合有三种编码方式,分别对应的整型范围是

-2^15~2^15-1,

-2^31~2^31-1,

-2^63~2^63-1

下图简单描绘了整数结合的基本结构

在contents数组当中的元素是从小到大进行排列的

添加元素

我们首先看一下添加元素的源代码

我们可以看到在添加元素的逻辑里面会涉及到升级编码方式操作,也就是说如果要添加的新的元素不在现有编码方式的范围之内的话就需要对编码方式进行升级。

212行,判断一下要插入元素的编码是否比当前intset的编码方式要大,我们从图1可以知道

INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64

如果是的话,就需要对当前intset的编码方式进行升级。我们看一下如何对编码方式进行升级并且添加一个新的元素进来。

如果这个新的元素的插入让当前的整数集合编码升级,那么这个元素的值要么比当前集合中所有值都要小,要么比当前集合中所有元素的值都要大,只需要 判断该元素是负值还是正值,如果是负值的话就插入到当前所有元素的前面,如果是正值的话就插入到后面。

170行,我们可以看到在分配完新的编码方式的内存空间之后,是从后向前进行元素位置的重新布局。布局完之后,再根据元素 是正数还是负数把新的元素插入到后面或者前面。再回到图4,如果要插入的元素不需要对当前整数集合的编码方式进行改变的话, 那么就先判断一下新插入的元素是否在当前集合中已经存在了,如果已经存在了就不需要再次插入。我们看下如何查找一个元素是否存在的方法intsetSearch

120行是判断如果当前集合为空就把该元素插入到第0位,123-133行是判断以下两种情况,如果当前元素小于现有元素的最小值就插入到第0位; 如果当前元素大于现有元素的最大值就插入到最后一位。

 由于这个集合中元素是有序排列的,所以从135-145的代码是采用二分法查找是否存在一个元素与将要插入的元素数值相同,上面这个方法就是查找元素的全部流程。 我们再回到图4,在将一个新的元素插入到集合当中的时候,首先要分配内存,然后将所有比新元素大的元素向后移位,这就是intsetMoveTail方法的工作

以上就是关于整数集合intset的解读。


如果对你有帮助,请作者喝一杯牛奶吧