redis数据结构实现整数集合（intset） - ZhenLinTechnologySalon/- GitHub Wiki

redis数据结构实现--整数集合（intset）

整数集合是集合键的底层实现之一，当一个集合键只包含整数元素，且元素不多时，Redis会采用整数集合作为集合键的底层实现。

可以保存int16_t，int32_t, int64_t类型的整数值。集合中不会出现重复元素

5.1 整数集合的实现

inset结构：

    typedef struct inset{
        //编码方式
        uint32_t encoding;
        
        //集合包含的元素数量
        uint32_t length;
        
        //保存元素的数组
        int8_t contents[];
    }intset;

contents数组就是整数数组的底层实现，各个元素在数组中按数组大小排序，且不可重复

虽然contents数组类型是int8_t，但是数组不存储任何int8_t类型的元素，contents数组真正的类型取决于encoding的值

5.2 升级（upgrade）

当我们添加一个新元素到整数集合中，并且新元素的类型比整数集合中的所有元素类型都要长，那么整数集合需要先进行升级，才能添加此新元素。

添加新元素并升级步骤：

1. 根据新元素类型，拓展整数集合底层数组空间大小，并为新元素分配空间
2. 将底层数组已有元素全部转化成新元素相同类型，并放置到正确的位上，此过程要保持有序性不变
3. 添加新元素
4. 修改encoding

引发升级的新元素长度肯定大于数组内已存的所有元素，所以这个新元素的值要么大于所有现有元素，要么小于所有现有元素。大于所有元素则插入在数组尾，小于所有元素则插入在数组头

升级的好处

升级带来更好的灵活性：整数集合自适应各种不同类型；
升级能够节省内存：确保扩展内存只在有需要的时候进行

5.3 降级