Intset 解读

数据结构定义

typedef struct intset {
    uint32_t encoding;    // 编码方式：INTSET_ENC_INT16/32/64
    uint32_t length;      // 集合中元素个数
    int8_t contents[];    // 柔性数组，存储实际的整数数据
} intset;

编码方式

Redis intset支持三种编码方式，根据存储的整数大小自动选择：(只升不降）

#define INTSET_ENC_INT16 (sizeof(int16_t))  // 2字节
#define INTSET_ENC_INT32 (sizeof(int32_t))  // 4字节  
#define INTSET_ENC_INT64 (sizeof(int64_t))  // 8字节

编码选择逻辑：

  • 如果所有整数都在 [-32768, 32767] 范围内，使用 INT16 编码

  • 如果所有整数都在 [-2147483648, 2147483647] 范围内，使用 INT32 编码

  • 否则使用 INT64 编码

核心特性

有序存储

  • 所有元素按照升序排列

  • 支持二分查找，查找时间复杂度 O(log n)

动态编码升级

  • 当插入超出当前编码范围的整数时，自动升级编码

  • 升级过程：重新分配内存 → 按新编码重新存储所有元素

内存优化

  • 根据实际数据范围选择最小编码

  • 避免存储大量小整数时浪费内存

核心函数解析

编码判断函数

static uint8_t _intsetValueEncoding(int64_t v) {
    if (v < INT32_MIN || v > INT32_MAX)
        return INTSET_ENC_INT64;
    else if (v < INT16_MIN || v > INT16_MAX)
        return INTSET_ENC_INT32;
    else
        return INTSET_ENC_INT16;
}

二分查找

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;
    
    // 边界检查
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 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;  // 找到
    } else {
        if (pos) *pos = min;
        return 0;  // 未找到，pos为插入位置
    }
}

编码升级

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intrev32ifbe(is->encoding);
    uint8_t newenc = _intsetValueEncoding(value);
    int length = intrev32ifbe(is->length);
    int prepend = value < 0 ? 1 : 0;  // 负数插入开头，正数插入末尾
    
    // 设置新编码并调整大小
    is->encoding = intrev32ifbe(newenc);
    is = intsetResize(is,intrev32ifbe(is->length)+1);
    
    // 从后往前升级，避免覆盖
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
    
    // 插入新值
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

添加元素

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 1;
    
    // 需要升级编码
    if (valenc > intrev32ifbe(is->encoding)) {
        return intsetUpgradeAndAdd(is,value);
    } else {
        // 二分查找检查是否已存在
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;
            return is;
        }
        
        // 调整大小并移动元素
        is = intsetResize(is,intrev32ifbe(is->length)+1);
        if (pos < intrev32ifbe(is->length)) 
            intsetMoveTail(is,pos,pos+1);
    }
    
    _intsetSet(is,pos,value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

添加元素时，只有不需要升级编码时，才需要二分查找确定插入位置

当需要编码升级时，新值一定超出了当前编码的范围：

  • INT16 → INT32：新值 < -32768 或 > 32767

  • INT32 → INT64：新值 < -2147483648 或 > 2147483647

为什么不需要二分查找？

  1. 数学保证：编码升级意味着新值在现有范围之外

  2. 位置确定：负数→开头，正数→末尾

  3. 性能优化：避免不必要的二分查找

  4. 逻辑简化：直接根据值的符号确定位置

字节序处理

使用 memrev16ifbe、memrev32ifbe、memrev64ifbe 函数处理字节序，确保在不同架构下的一致性

性能特点

  • 查找：O(log n) - 二分查找

  • 插入：O(n) - 需要移动元素保持有序

  • 删除：O(n) - 需要移动元素

  • 内存：根据数据范围优化，比哈希表更节省内存

使用场景

  • 当Set中只包含整数时，且数量不多（< set-max-intset-entries），Redis底层数据结构优先使用intset

  • 当元素数量较少且都是整数时，intset比哈希表更高效

  • 适合存储连续的整数范围

限制

  • 只能存储整数

  • 元素必须有序

  • 插入/删除操作较慢（需要移动元素）

  • 当元素数量超过阈值或包含非整数时，会转换为哈希表

intset 与 ziplist比较

  • ziplist 可存任意二进制串，intset 只能存整数
  • ziplist 无序，intset 从小到大有序。ziplist 上查找只能遍历，intset 可进行二分查找，性能更高
  • ziplist 可对每个数据项进行不同的变长编码（每个数据项前面都有数据长度字段len），intset 只能整体使用一个统一的编码（encoding）