首页 > 代码库 > Redis数据结构之intset
Redis数据结构之intset
本文及后续文章，Redis版本均是v3.2.8
上篇文章《Redis数据结构之robj》，我们说到redis object数据结构，其有5中数据类型：OBJ_STRING，OBJ_LIST， OBJ_SET，OBJ_ZSET，OBJ_HASH。集合对象set有着广泛的实际业务应用场景，它包含的元素无序并且不能重复及集合间的交、并、差等基础的操作。本篇就来说说Redis暴露给我们使用的set集合对象的底层实现-intset。
其实，可以理解为有序整型集合
intset是一个由整数组成的有序集合，从而便于进行二分查找，用于快速地判断一个元素是否属于这个集合。
它在内存分配上与ziplist有些类似，是连续的一整块内存空间，而且对于大整数和小整数采取了不同的编码，尽量对内存的使用进行了优化。
一、intset数据结构定义
typedef struct intset {
uint32_t encoding; //编码类型
uint32_t length; //intset大小，元素个数
int8_t contents[]; //数据存储区，按照升序排序数组
} intset;
/* Note that these encodings are ordered, so:
* INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))
从上述intset结构定义中看到其包含如下字段：
encoding：数据编码，用于表示intset中的每个数据元素用几个字节来表示。其取值如上列出的三种值：
encoding 元素类型 元素占用字节 INTSET_ENC_INT16 int16_t 2 INTSET_ENC_INT32 int32_t 4 INTSET_ENC_INT64 int64_t 8
因此，intset中存储的整数最多只能占用64bit。
length：表示intset中的元素个数。encoding和length两个字段构成了intset的头部（header）。
contents：是一个柔性数组（flexible array member），根据元素大小升序存储，表示intset的header后面紧跟着数据元素。这个数组的总字节数等于(encoding * length)/8。柔性数组在Redis的很多数据结构的定义中都出现过（例如sds, quicklist, skiplist），用于表达一个偏移量。contents需要单独为其分配空间，这部分内存不包含在intset结构当中。
intset可能会随着数据的添加而改变它的数据编码：
最开始，新创建的intset使用占内存最小的INTSET_ENC_INT16（值为2）作为数据编码。
每添加一个新元素，则根据元素大小决定是否对数据编码进行升级。
二、intset基本操作
1、创建集合
/* Create an empty intset. */
intset *intsetNew(void) {
intset *is = zmalloc(sizeof(intset));
is->encoding = intrev32ifbe(INTSET_ENC_INT16);
is->length = 0;
return is;
}
2、查找元素
/* Determine whether a value belongs to this set */
uint8_t intsetFind(intset *is, int64_t value) {
/*判断待查元素编码是否符合条件，不符合直接返回false，否则进入intsetSearch进行实际查找*/
uint8_t valenc = _intsetValueEncoding(value);
return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL);
}
/* Search for the position of "value". Return 1 when the value was found and
* sets "pos" to the position of the value within the intset. Return 0 when
* the value is not present in the intset and sets "pos" to the position
* where "value" can be inserted. */
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
int64_t cur = -1;
/* The value can never be found when the set is empty */
if (intrev32ifbe(is->length) == 0) {
if (pos) *pos = 0;
return 0;
} else {
/* Check for the case where we know we cannot find the value,
* but do know the insert position. */
/* _intsetGet函数仅仅获取set集合中pos位置的值， 如果待查元素大于集合尾部元素，则直接返回待查元素位置为集合长度*/
if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
if (pos) *pos = intrev32ifbe(is->length);
return 0;
} else if (value < _intsetGet(is,0)) {
/*如果待查元素小于集合头部元素，则直接返回待查元素位置为0*/
if (pos) *pos = 0;
return 0;
}
}
/*二分查找*/
while(max >= min) {
mid = ((unsigned int)min + (unsigned int)max) >> 1;
cur = _intsetGet(is,mid);
if (value > cur) {
min = mid+1;
} else if (value < cur) {
max = mid-1;
} else {
break;
}
}
/*找到元素返回1，否则返回0，pos为元素位置*/
if (value =http://www.mamicode.com/= cur) {
if (pos) *pos = mid;
return 1;
} else {
if (pos) *pos = min;
return 0;
}
}
从上述代码中，我们知道
intsetFind：在指定的intset中查找指定的元素value，找到返回1，没找到返回0。_intsetValueEncoding：函数会根据要查找的value落在哪个范围而计算出相应的数据编码。如果
value所需的数据编码比当前intset的编码要大，则它肯定在intset所能存储的数据范围之外，所以这时会直接返回0；否则调用intsetSearch执行一个二分查找算法。intsetSearch在指定的intset中查找指定的元素value，如果找到，则返回1并且将参数pos指向找到的元素位置；如果没找到，则返回0并且将参数pos指向能插入该元素的位置。intsetSearch是对于二分查找算法的一个实现，它大致分为三个部分：特殊处理intset为空的情况。
特殊处理两个边界情况：当要查找的
value比最后一个元素还要大或者比第一个元素还要小的时候。实际上，这两部分的特殊处理，在二分查找中并不是必须的，但它们在这里提供了特殊情况下快速失败的可能。真正执行二分查找过程。注意：如果最后没找到，插入位置在
min指定的位置。代码中出现的
intrev32ifbe是为了在需要的时候做大小端转换的。前面我们提到过，intset里的数据是按小端（little endian）模式存储的，因此在大端（big endian）机器上运行时，这里的intrev32ifbe会做相应的转换。这个查找算法的总的时间复杂度为O(log n)。
3、添加元素
/* Insert an integer in the intset */
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
/*为了节省空间, 判断添加的元素需要编码为何种数据类型, 比如int16, int32, int64*/
uint8_t valenc = _intsetValueEncoding(value);
uint32_t pos;
if (success) *success = 1;
/* Upgrade encoding if necessary. If we need to upgrade, we know that
* this value should be either appended (if > 0) or prepended (if < 0),
* because it lies outside the range of existing values. */
/*如果intset编码位数无法容纳新元素，则需要重新更新整个intset编码*/
if (valenc > intrev32ifbe(is->encoding)) {
/* This always succeeds, so we don‘t need to curry *success. */
/* 更新编码并添加新元素，动态申请更大的空间以足够存储扩展后的length+1个元素 */
return intsetUpgradeAndAdd(is,value);
} else {
/* Abort if the value is already present in the set.
* This call will populate "pos" with the right position to insert
* the value when it cannot be found. */
/*搜索新添加元素是否已经存在，存在则返回失败；这里也就是set中无重复元素的原因*/
if (intsetSearch(is,value,&pos)) {
if (success) *success = 0;
return is;
}
/*扩展内存空间*/
is = intsetResize(is,intrev32ifbe(is->length)+1);
if (pos < intrev32ifbe(is->length))
/*如果添加元素位置不是一整块内存尾部，则需将其后面元素后移一个元素位置*/
intsetMoveTail(is,pos,pos+1);
}
/*pos位置处赋值*/
_intsetSet(is,pos,value);
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
return is;
}
从上述添加元素的代码中，我们知道
intsetAdd在intset中添加新元素value。如果value在添加前已经存在，则不会重复添加，这时参数success被置为0；如果value在原来intset中不存在，则将value插入到适当位置，这时参数success被置为0。如果要添加的元素
value所需的数据编码比当前intset的编码要大，那么则调用intsetUpgradeAndAdd将intset的编码进行升级后再插入value。调用
intsetSearch，如果能查到，则不会重复添加。如果没查到，则调用
intsetResize对intset进行内存扩充，使得它能够容纳新添加的元素。因为intset是一块连续空间，因此这个操作会引发内存的realloc。这有可能带来一次数据拷贝。同时调用intsetMoveTail将待插入位置后面的元素统一向后移动1个位置，这也涉及到一次数据拷贝。值得注意的是，在intsetMoveTail中是调用memmove完成这次数据拷贝的。memmove保证了在拷贝过程中不会造成数据重叠或覆盖。intsetUpgradeAndAdd的实现中也会调用intsetResize来完成内存扩充。在进行编码升级时，intsetUpgradeAndAdd的实现会把原来intset中的每个元素取出来，再用新的编码重新写入新的位置。注意一下
intsetAdd的返回值，它返回一个新的intset指针。它可能与传入的intset指针is相同，也可能不同。调用方必须用这里返回的新的intset，替换之前传进来的旧的intset变量。类似这种接口使用模式，在Redis的实现代码中是很常见的，比如我们之前在介绍sds和ziplist的时候都碰到过类似的情况。intsetAdd算法总的时间复杂度为O(n)。
三、intset整数集合的升级操作
此时contents数组占用的空间为16*3=48位。
升级后的整数集合为：
contents数组中的元素存放顺序为：
新创建的intset只有一个header，总共6个字节。其中
encoding= 2,length= 3。当添加65535的时候，它不再能用2个字节来表示了（2个字节能表达的数据范围是-215~215-1，而32768等于215，超出范围了），因此
encoding必须升级到INTSET_ENC_INT32（值为4），即用4个字节表示一个元素。在添加每个元素的过程中，intset始终保持从小到大有序。
因此升级的步骤为：
1）根据新元素的类型，扩展底层数组的空间大小，并分配空间
2）将底层所有元素都转换成新元素相同的类型，并将转换后的元素放到新分配的空间中。在放置元素的过程中，需要维持底层数组的有序性质不变
3）将新元素加入到底层数组中
由于新加入的元素导致升级，因此新元素的大小一定比之前所有的元素都大，因此将新元素存放在contents数组的最后一项即可。
与ziplist类似，intset也是按小端（little endian）模式存储的。比如，在上图中intset添加完所有数据之后，表示
encoding字段的4个字节应该解释成0x00000004，而第5个数据应该解释成0x000186A0 = 100000。
四、总结
当set中添加的元素都是整型且元素数目较少时，set使用intset作为底层数据结构，否则，set使用dict作为底层数据结构。
1、intset实质就是一个有序数组，存储元素紧密，空间利用率高，而且不容易因频繁地插入删除而产生内存碎片。
2、支持整型编码，intset中所有数据元素的存储类型是一致的。新插入数据时，如果数据的类型大于当前intset的数据类型，则可扩大存储的整型类型（但intset不提供缩小编码类型的能力）。在一定程序上可节省空间，但所有的存取都需要考虑类型。
3、有length字段可记录元素个数，取元素个数操作为常量。
4、添加元素时，可能需要移动至多N个元素，也有可能使编码类型升级，重组intset。由于这两个特点，intset并不适合于频繁插入和存储大量元素。
5、删除元素时，可能需要移动至多N-1个元素。
参考
Redis设计与实现
--EOF--
Redis数据结构之intset