redis 从0到1完整学习 （五）：集合 IntSet 数据结构

1. 引言

前情提要：
《redis 从0到1完整学习 （一）：安装&初识 redis》
《redis 从0到1完整学习 （二）：redis 常用命令》
《redis 从0到1完整学习 （三）：redis 数据结构》
《redis 从0到1完整学习 （四）：字符串 SDS 数据结构》
本文主要结合源码来介绍 Redis IntSet 的数据结构

2. redis 源码下载

Redis 源码可以点击这里下载，方便查看其中定义的一些数据结构。

3. IntSet 数据结构

Redis 的 IntSet 是一个整数 set 数据结构，用于存储一系列整数值。它具有以下特点：

• 有序性：IntSet 中的元素按照升序排列。
• 唯一性：IntSet 中的元素是唯一的，不会出现重复的值。
• 空间效率：IntSet 使用紧凑的存储方式，元素之间没有额外的空间开销。

Redis 的 IntSet 数据结构常用于需要存储和快速查找整数集合的场景。它提供了一组操作命令，可以对 IntSet 进行插入、删除、查找等操作。

encoding 表示编码方式，支持16位、32位、64位整数；
length 表示元素的个数；
contents 整数数组，保存数据。

下面从源码来分析，Intset 是如何自动升级编码方式到合适的大小的：

// 插入到 IntSet 中
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 {
		// 查找当前值应该放置的位置，如果返回1，表示已经存在一样的值
        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);
    // 元素长度+1
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

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;

    // 重设编码以及size
    is->encoding = intrev32ifbe(newenc);
    is = intsetResize(is,intrev32ifbe(is->length)+1);

	// 从后往前倒序将元素挪到指定位置
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

   	// prepend=1表示为负数，最小的，应该放置到队首
    if (prepend)
        _intsetSet(is,0,value);
    else // prepend=0表示为正数，最大的，应该放置到队尾
        _intsetSet(is,intrev32ifbe(is->length),value);
    // 数组长度+1
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

// 计算 value 插入的位置 pos，同时返回0表示未找到一样的值，1表示找到一样的值
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;

    /* The value can never be found when the set is empty */
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    } else {
		// 比最大的还大，比最小的还小，则可以直接返回要插入的位置
        if (value > _intsetGet(is,max)) {
            if (pos) *pos = intrev32ifbe(is->length);
            return 0;
        } else if (value < _intsetGet(is,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;
        }
    }
	// 找到了，则返回1
    if (value == cur) {
        if (pos) *pos = mid;
        return 1;
    } else { // 没找到，返回要插入的地方
        if (pos) *pos = min;
        return 0;
    }
}

4. 参考

《redis 从0到1完整学习 （一）：安装&初识 redis》
《redis 从0到1完整学习 （二）：redis 常用命令》
《redis 从0到1完整学习 （三）：redis 数据结构》
《redis 从0到1完整学习 （四）：字符串 SDS 数据结构》