【Redis数据结构】intset 整数集合

1. intset 简介

整数集合（intset）是 redis 当中 set 集合类型的底层实现方式之一，即当存放的元素全都是整数类型且元素数量不多的时候，redis就会使用 intset 作为 set 的底层实现

如上图所示，当我们向 s1 当中插入 [1, 2, 3] 三个元素后，使用OBJECT ENCODING s1可以观察到底层结构使用的是intset整数集合

2. intset 底层结构

在 redis 的源码包src/intset.h中就有如下图所示结构体声明：

其中各个字段的含义如下：

contents：本质上是一个字节数组，用于存放存储的整数值（从小到大有序排列且不重复）
length：集合中包含的元素个数
encoding：contents 数组中存储的整数元素的类型（可以为 int16_t、int32_t、int64_t）
- 当encoding字段的值为INTSET_ENC_INT16时，表示数组每一项都是 int16_t 类型大小
- 当encoding字段的值为INTSET_ENC_INT32时，表示数组每一项都是 int32_t 类型大小
- 当encoding字段的值为INTSET_ENC_INT64时，表示数组每一项都是 int64_t 类型大小

如上图所示：该 intset 结构存储了四个整数：[-32768, 1, 2, 8]，因此 length 的值为 4 ，并且每个元素的大小都不超过 int16_t 的范围，所以 encoding 的值为 INTSET_ENC_INT16，此时 contents 数组占用的存储空间就是 sizeof(int16_t) * length = 64 bit

💡 温馨提示：有些小伙伴可能会疑惑为什么 contents 数组的类型统一是 int8_t，那不是存储不了 int64_t 类型的值吗？可以这样来理解：一个 int64_t 类型本质就是 8 个字节，因此完全可以使用多个最小粒度的 int_8 类型表示，将来取值的时候也只需要根据 encoding 类型获取相应长度的数组元素

3. intset 升级

3.1 升级流程

当我们向一个 intset 类型的集合当中插入新元素的时候，如果新元素的类型大小超过了当前的encoding表示的元素类型大小，此时就需要进行升级（upgrade）操作，其流程如下：

首先计算新数组需要开辟的内存大小：(length + 1) * 新元素类型大小
然后倒序地将原数组存储的数值复制到新的索引位置
将新元素复制到对应的索引位置
修改结构体当中的 encoding 和 length 字段

如上图所示，当前的 intset 类型存储的数据是[1, 2, 3]，可以使用 int16 来表示，但是如果现在要插入新元素：65535，此时该新元素的类型大小为 int32_t，因此需要进行升级操作：

首先计算升级后的新数组的大小：sizeof(int32_t) * (length + 1) = 128 位
接下来分别倒序将原来的元素进行复制，比如元素 3 的新索引处应该是 2，起始地址就是 2 * sizeof(int32_t)，即存储到 64 - 95 位处，同理元素 2 的新索引处是 1，起始地址就是 1 * sizeof(int32_t)，即存储到 32 - 63 位处，元素 1 存储到 0 - 31 位处
将新元素移动到对应位置，元素 65535 的索引应该是 3 ，因此复制到 96 - 127 位处
修改 encoding 为 INTSET_ENC_INT32，length 为 4

💡 注意：为什么需要倒序复制呢？这是为了避免覆盖原先的值，比如如果按照正序复制，那么需要先将元素 1 的值覆盖到 0 - 31位，然后获取原先元素 2 的位置（16 - 31位）发现已经被填充了！

3.2 升级的好处

intset 结构的升级主要有以下两点好处：

灵活度高：由于 C 语言是一门静态类型语言，因此 int64_t 类型的数组只能存储 int64_t 类型元素，而 intset 采用的升级流程更加灵活（可以运行时切换元素类型）
节省内存空间：没有固定使用 int64_t 类型存储 int16_t、int32_t 类型的元素，而是采用了运行时动态升级切换的策略，如果存储的元素均为 int16_t 类型，那么只会分配 int16_t 为单位的内存空间