IntSet

简介

Redis 的 intset（整数集合）是一种用于存储整数的有序集合数据结构。它在 Redis 的实现中被广泛用于存储有序的整数集合。

具体实现

基本结构

结构定义如下：

1
2
3
4
5
typedef struct intset {
    uint32_t encoding; /* 编码方式，支持存放16位、32位、64位整数*/
    uint32_t length; /* 元素个数 */
    int8_t contents[]; /* 整数数组的头地址*/
} intset;

Redis会将intset中所有的整数按照升序依次保存在contents数组中，结构如图：

image-20250219211630888

由于保存了contens数组的头地址，且数组是一片连续内存，可以通过地址+偏移的方式快速查到指定下标的元素。

空间效率

intset 通过动态调整整数的存储类型，根据存储的整数范围自动选择最合适的编码方式，从而节省内存。encoding包含三种模式，表示存储的整数大小不同：

1
2
3
#define INTSET_ENC_INT16 (sizeof(int16_t)) /* 2字节整数*/
#define INTSET_ENC_INT32 (sizeof(int32_t)) /* 4字节整数*/
#define INTSET_ENC_INT64 (sizeof(int64_t)) /* 8字节整数*/
自动升级

当插入一个超出当前编码范围的整数时，intset 会自动升级到更大的编码类型（例如从 INT16 升级到 INT32），以支持更大的整数。

例如现在有一个intset，元素为{5,10,20}，采用的编码是INTSET_ENC_INT16，则每个整数占2字节：

image-20250219212042536

向该其中添加一个数字：50000，这个数字超出了int16_t的范围，intset会自动升级编码方式到合适的大小。流程如下：

  1. 升级编码为INTSET_ENC_INT32, 每个整数占4字节，并按照新的编码方式及元素个数扩容数组；
  2. 倒序依次将数组中的元素拷贝到扩容后的正确位置；
  3. 将待添加的元素放入数组末尾；
  4. 将inset的encoding属性改为INTSET_ENC_INT32，将length属性改为4。

image-20250219212150080

image-20250219212217596

查找元素实现

intsetFind 函数用于在 intset 中查找一个特定的整数。由于 intset 是一个有序集合，因此可以使用二分查找算法来高效地查找元素。关键代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 在 intset 中查找指定的值
uint8_t intsetFind(intset *is, int64_t value) {
    // 计算目标值所需的编码类型
    uint8_t valenc = _intsetValueEncoding(value);
    // 检查目标值的编码类型是否小于或等于当前 intset 的编码类型
    // 如果目标值的编码类型不匹配，或者目标值不在集合中，则返回 0
    return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is, value, NULL);
}

// 在 intset 中查找指定的值，并返回其位置
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    int min = 0, max = intrev32ifbe(is->length) - 1, mid = -1;  // 初始化二分查找的范围
    int64_t cur = -1;  // 用于存储中间值

    // 如果集合为空，直接返回 0
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;  // 如果需要返回位置，设置为 0
        return 0;  // 返回 0 表示未找到
    } else {
        // 如果目标值大于集合中的最大值，返回 0
        if (value > _intsetGet(is, intrev32ifbe(is->length) - 1)) {
            if (pos) *pos = intrev32ifbe(is->length);  // 设置插入位置为集合末尾
            return 0;  // 返回 0 表示未找到
        } else if (value < _intsetGet(is, 0)) {
            if (pos) *pos = 0;  // 设置插入位置为集合开头
            return 0;  // 返回 0 表示未找到
        }
    }

    // 使用二分查找算法查找目标值
    while (max >= min) {
        mid = ((unsigned int)min + (unsigned int)max) >> 1;  // 计算中间位置
        cur = _intsetGet(is, mid);  // 获取中间位置的值
        if (value > cur) {
            min = mid + 1;  // 如果目标值大于中间值，调整下界
        } else if (value < cur) {
            max = mid - 1;  // 如果目标值小于中间值，调整上界
        } else {
            break;  // 如果找到目标值，退出循环
        }
    }

    // 检查是否找到目标值
    if (value == cur) {
        if (pos) *pos = mid;  // 如果需要返回位置，设置为找到的位置
        return 1;  // 返回 1 表示找到
    } else {
        if (pos) *pos = min;  // 如果未找到，设置插入位置
        return 0;  // 返回 0 表示未找到
    }
}

步骤可以概括为：

  1. 检查目标值的编码类型是否与集合的编码类型匹配。
  2. 使用二分查找算法查找目标值。
  3. 如果找到目标值，返回 1，并设置找到的位置。
  4. 如果未找到目标值，返回 0，并设置插入位置。

时间复杂度为O(logn)

添加元素实现

intsetAdd 函数用于在 intset 中添加一个新元素。由于 intset 是一个有序集合，因此在添加新元素时需要保持其有序性。关键代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 向 intset 中添加一个新元素
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    // 计算新值所需的编码类型
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;  // 用于存储查找结果的位置
    if (success) *success = 1;  // 初始化 success 为 1（表示成功）

    // 检查是否需要升级编码
    // 如果新值的编码类型大于当前集合的编码类型
    if (valenc > intrev32ifbe(is->encoding)) {
        // 升级编码并添加值
        // 这个操作总是成功的，因此不需要设置 success
        return intsetUpgradeAndAdd(is, value);
    } else {
        // 检查值是否已经存在于集合中
        // 如果值已存在，返回 1 并设置 pos 为找到的位置
        // 如果值不存在，返回 0 并设置 pos 为插入位置
        if (intsetSearch(is, value, &pos)) {
            // 如果值已存在，设置 success 为 0（表示失败）并返回集合
            if (success) *success = 0;
            return is;
        }

        // 扩展集合，为新元素腾出空间
        // 增加集合的长度
        is = intsetResize(is, intrev32ifbe(is->length) + 1);
        // 如果插入位置在集合的中间，需要移动尾部元素
        if (pos < intrev32ifbe(is->length)) {
            // 将从 pos 开始的元素向后移动一个位置
            intsetMoveTail(is, pos, pos + 1);
        }
    }

    // 在指定位置插入新值
    _intsetSet(is, pos, value);
    // 更新集合的长度
    is->length = intrev32ifbe(intrev32ifbe(is->length) + 1);
    return is;
}

步骤可以概括为：

  1. 检查是否需要升级编码。
  2. 检查值是否已存在。
  3. 扩展集合，为新元素腾出空间。
  4. 移动尾部元素，为新元素腾出位置。
  5. 插入新值。
  6. 更新集合的长度。

由于需要移动元素，最坏时间复杂度为O(n)

__END__