《Redis 设计与实现》笔记 - 整数集合

数据结构

typedef struct intset {

    // 编码方式
    uint32_t encoding;

    // 集合包含的元素数量
    uint32_t length;

    // 保存元素的数组
    int8_t contents[];

} intset;

+-------------------------+
| intset                  |
|-------------------------|
|encoding=INTSET_ENC_INT16|
|-------------------------|
| length=5                |
|-------------------------|   +-----+--+--+---+-----+
| contents                |-->|-6730|-5|18|233|14632|
+-------------------------+   +-----+--+--+---+-----+

+-------------------------+
| intset                  |
|-------------------------|
|encoding=INTSET_ENC_INT64|
|-------------------------|
| length=4                |
|-------------------------|   +--------------------+-+-+-+
| contents                |-->|-2675256175807981027|1|3|5|
+-------------------------+   +--------------------+-+-+-+

整数集合是 Redis 用于保存整数值的集合抽象数据结构，支持保存 int16_t、int32_t、int64_t 的整数值，并且保证集合中不会出现重复元素。

整数集合中的字段描述：

1. contents 数组是整数集合的底层实现，整数集合的每个元素都是 contents 数组的一个数组项，各个项在数组中按值的大小从小到大地有序排列，并且数组中不包含任何重复项；

2. length 属性记录了整数集合包含的元素数量，也就是 contents 数组的长度；

3. contents 数组的类型取决于 encoding 属性的值。

升级策略

当向整数集合添加一个比现有元素类型都要长的新元素时，整数集合会进行一次升级操作。

升级整数集合需要三个步骤：

1. 根据新元素的类型，扩展 contents 数组，为新元素分配空间；

2. 将 contents 数组的所有元素转换成与新元素相同的类型；

3. 添加新元素。

整数集合的升级策略主要有两点好处：提升整数集合的灵活性、尽可能地节约内存。

整数集合不支持降级。