Redis源码学习-3-整数集合

嵌牛导读：该篇文章分为数据结构，有序结构和升级三个方面

嵌牛鼻子：数据结构 整数集合 升级

嵌牛提问：为什么设置升级

嵌牛正文：

1. 数据结构

typedef struct intset {

    // 编码方式

    uint32_t encoding;

    // 集合包含的元素数量

    uint32_t length;

    // 保存元素的数组

    int8_t contents[];

} intset;

Redis的intset的元素类型，主要取决于encoding字段，分别保存16, 32, 64位的整数。所以contents前面的类型没有任何意义。

2. 有序结构

intset是一种有序结构，即contents是按照从小到大进行排列的。

因此查找的时候就可以使用二分查找。是O(logN)的时间复杂度。

3. 升级

intset默认保存的是16位大小的数据。

// 设置初始编码

is->encoding = intrev32ifbe(INTSET_ENC_INT16);

当新添加的元素比16位编码大或者小时，就会发生升级。升级效果如下，比如新插入的数字是32位大小的。那么所有contents数组中的内容就会被更新为32位大小。

3.1 具体演示

现在插入65535，因为这个数字大于MAX_INT16，所以需要realloc重新分配内存。因为是大于，所以保留最后的位置。如果是小于，即插入-65535，则是保留最前面的位置。

重新调整index 2位置的元素

*((int32_t*)contents+2)=*((int16_t*)contents+2);

最后，将新加入到的元素安排到最后。

3.2 为什么设置升级？

Redis是内存数据库，所以内存对于Redis来说非常的宝贵。相当于是用时间换空间。

提升了灵活性，对于上层使用者来说，他可以自由使用int16，int32，int64大小的数据。

因为intset是不会降级的，所以其时间消耗并不大，最多仅有2次的升级操作。