整数集合的定义

Redis 中的整数集合 intset 是用来保存多个不重复的整数值且有序的集合抽象数据结构，可以保存类型为 int16-t 、int32-t 或者 int64-t 的整数值。它是实现集合键底层之一。

整数集合应用场景

整数集合在 Redis 中作为了集合 Set 数据结构的底层实现之一。

当一个集合中的元素都是整数值，且元素不多的时候，整数集合就会作为集合 Set 的底层实现。

举个例子：如果我们创建一个只包含五个元素的集合键，并且集合中的所有元素都是整数值，那么这个集合键的底层实现就会是整数集合：

redis> SADD numbers 1 3 5 7 9
 (integer) 5 
redis> OBJECT ENCODING numbers 
"intset"

整数集合的实现

整数集合（intset）是Redis用于保存整数值的集合抽象数据结构，它可以保存类型为int16_t、int32_t或者int64_t的整数值，并且保证集合中不会出现重复元素。

整数结合的结构定义：

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

属性说明：

• contents数组：是整数集合的底层实现：整数集合的每个元素都是contents数组的一个数组项（item），各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。
• length属性：记录了整数集合包含的元素数量，也即是contents数组的长度。
• encoding属性，决定数组contents存储元素的真正类型。

• • INTSET_ENC_INT16：int16_t类型的整数值（最小值为32768，最大值为32767）
  • INTSET_ENC_INT32：int32_t类型的整数值（最小值为2147483648，最大值为2147483647）
  • INTSET_ENC_INT64：个int64_t类型的整数值（最小值为9223372036854775808，最大值为9223372036854775807）

 

整数集合的结构：

如图6-1：一个包含5个int16_t类型整数数值的整数集合：contents数组的大小等于sizeof（int16_t）*5=16*5=80位。

如图6-2：一个包含4个int64_t类型整数数值的整数集合：contents数组的大小等于sizeof（int64_t）*4=64*4=256位。

插入元素操作：

• 插入元素的时候，会先计算新元素所需的长度，然后if 判断是否需要升级操作。
• 如果新元素的编码类型比原来整数集合的 encoding 值大，那么进行集合升级操作，之后将升级后的整数集合返回。
• 不满足升级操作的话，先查找新元素是否在原来的整数集合存在，

• • 存在，操作失败，返回原来的整数集合。这里是为了保证整数集合的元素唯一性。
  • 不存在，就会为集合调整新的内存空间，然后将新元素设置进他合适的位置上。

• 之后为 length 属性值加一，返回新的整数集合，完成了插入操作。

查找元素操作：

• 查找元素开始的时候，先对整数集合是否有值进行判断，没值就返回0。
• 有值就通过获取首尾元素的值来判断该元素是否存在集合中，因为整数集合的有序性，通过最大最小值可以直接判断出是否存在。
• 然后通过数组的二分查找思想的代码，快速查找该元素的位置，最终找到了位置就返回1表示找到并将找到的位置设置到 pos 属性，0表示没找到。

删除元素操作：

• 先计算需要删除元素的编码类型，只有当元素的编码类型小于等于整数集合的 encoding 的时候在进行下一步，(因为大于的话，表示该元素不存在整数集合中)；
• 且调用 intsetSearch 函数查找元素存在，存在才执行具体的删除操作。
• 具体删除操作的时候，调用 intsetMoveTail 函数将原来这个元素的位置后面的元素往前移动。
• 最后重新调整集合的内存空间，以及集合的长度完成了最终的删除操作。

升级

每当向集合添加元素的时候，如果新元素的类型比enconding属性的类型长时，需要先对整个整数集合需要进行升级，然后把新元素添加进来。

升级操作步骤：时间复杂度为O（N）

• 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
• 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
• 将新元素添加到底层数组里面。
• 将enconding改为当前类型，长度加一。

升级过程案例：

（1）一个包含三个int16_t类型的整数集合，整数集合底层数组的大小为3*16=48位。

（2）添加一个新元素65535，类型是int32_t的>int16_t，进行升级。

先进行空间重分配；分配的空间大小是= 4*32 - 3*16= 128 - 48 = 80位；

在对倒数第3个元素进行类型转换；

在对倒数第2个元素进行类型转换；

在对倒数第1个元素进行类型转换；

类型转换完成后，将新元素添加到尾部；

 

最后，程序将整数集合encoding属性的值从INTSET_ENC_INT16改为INTSET_ENC_INT32，并将length属性的值从3改为4;

升级之后新元素的摆放位置

因为引发升级的新元素的长度总是比整数集合现有所有元素的长度都大，所以这个新元素的值要么就大于所有现有元素，要么就小于所有现有元素：

• 在新元素小于所有现有元素的情况下，新元素会被放置在底层数组的最开头（索引0）；
• 在新元素大于所有现有元素的情况下，新元素会被放置在底层数组的最末尾（索引length1）。

升级的好处

整数集合的升级策略有两个好处，一个是提升整数集合的灵活性，另一个是尽可能地节约内存。

（1）提升灵活性

因为整数集合可以通过自动升级底层数组来添加元素，所以可以任意添加不同类型的数值(int16_t,int32_t,int64_t)，不必担心类型错误。

（2）尽可能的节约内存

不必上来就定义int64_t类型(或者更长的类型)的数组，而是在需要的时候在扩展为int64_t(或者更长的类型)；

 

降级-不支持

整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。

 

总结

• 整数集合是集合键的底层实现之一。
• 整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型。
• 升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存。
• 整数集合只支持升级操作，不支持降级操作。

 

黄健宏 著. Redis设计与实现 (Chinese Edition) (Kindle 位置 938-940). Kindle 版本.