Redis教程

Redis源码学习 - 1.8 - 有序集合

本文主要是介绍Redis源码学习 - 1.8 - 有序集合,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

源码位置:intset.h 和 intset.c

8.1 数据结构

/* Note that these encodings are ordered, so:
 * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

// 以下所有数据在内存中使用小端存储
typedef struct intset {
    uint32_t encoding;          // 编码方式,见上述三种类型 INTSET_ENC_INT**
    uint32_t length;            // 长度
    int8_t contents[];          // 数据内容
} intset;

8.2 常用函数

// 内部函数
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos);     // 二分查找value的位置
// 外部API函数
intset *intsetNew(void);                                                   // 初始化intset*
intset *intsetAdd(intset *is, int64_t value, uint8_t *success);            // 插入value
intset *intsetRemove(intset *is, int64_t value, int *success);             // 删除value
uint8_t intsetFind(intset *is, int64_t value);                             // 查找value,调用intsetSearch
int64_t intsetRandom(intset *is);                                          // 调用rand(),随机获得元素
uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value);               // 获取post位置的元素
uint32_t intsetLen(const intset *is);                                      // 整数集合的长度
size_t intsetBlobLen(intset *is);                                          // 获取集合的字节长度
int intsetValidateIntegrity(const unsigned char *is, size_t size, int deep); // 检查整数集合是否合法
// deep = 0:只检查encoding、length、
// deep = 1:检查encoding、length、content数组有序、content数组元素不重复

8.3 底层实现

8.3.1:插入

/* Insert an integer in the intset */
// [OUT]success: 1成功,0失败
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value);   // 获取数据编码类型:
    uint32_t pos;
    if (success) *success = 1;

    // is->encoding存入的时候调用了一次intrev32ifbe转换成小端数据
    // 读出来的时候,也要再调用一次intrev32ifbe转换回去
    if (valenc > intrev32ifbe(is->encoding)) {
        // 插入值的取值范围 > 当前encoding取值范围,逐个升级所有数据(升级数据类型),算法复杂度:O(N)
        return intsetUpgradeAndAdd(is,value);
    } else {
        // 二分查找value的位置
        if (intsetSearch(is,value,&pos)) {
            // 数据已经存在,插入新值失败
            if (success) *success = 0;
            return is;
        }

        // 新的数组长度,+1表示新增的一个元素
        is = intsetResize(is,intrev32ifbe(is->length)+1); 
        // pos及其之后的数据往后移动一个位置,intsetMoveTail中调用一次memmove函数,算法复杂度O(1)
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }
    
    // 写入值
    _intsetSet(is,pos,value);
    // 更新长度
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

升级和降级:

  • 升级的好处显而易见,在数据的值比较小的时候,可以节省内存空间,同时兼容数据值较大的情况
  • 降级:有序整数集合一旦升级,不支持降级

时间复杂度:

  • 如果新元素是原来的数据类型存不下去的数据(溢出),逐个更新所有数据,复杂度O(N)
  • 如果新元素原来的数据类型能存下,只需要调用一次memmove移动内存数据,复杂度O(1)

8.3.2:删除

/* Delete integer from intset */
// [OUT]success: 1成功,0失败
intset *intsetRemove(intset *is, int64_t value, int *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 0;

    // value在允许范围内,二分查找value的位置
    if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) {
        uint32_t len = intrev32ifbe(is->length);

        if (success) *success = 1;

        // pos之后的数据往前移动一个位置,intsetMoveTail中调用一次memmove函数,算法复杂度O(1)
        if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);
        // 释放了一个元素,需要调整内存大小和数组长度
        is = intsetResize(is,len-1);
        is->length = intrev32ifbe(len-1);
    }
    return is;
}

时间复杂度:

  • 二分查找元素不存在:直接返回失败,复杂度:O(logN)
  • 二分查找元素存在,需要再调用一次memmove函数移动内存数据,复杂度:O(logN)

8.4 一些疑问

为什么有序整数集合中要用小端数据存储?

RDB持久化模式下,intset、ziplist在写入RDB文件中的时候,会直接将对应内存中的数据直接写入到文件中,中间没有任何转换,因为intset、ziplist是保存在连续内存块中的,不需要额外处理。而像list dict skiplist这些结构中的数据是使用指针关联起来的,无法直接写人到文件中,需要额外的转换操作,具体就是将其中的数据转换为字符串写入到文件中。这样以来,如果我们在其他机器上加载RDB文件恢复数据时,就不需要考虑list dict skiplist这些数据的大小端问题,因为他们的数据是以字符串存储的,而intset、ziplist是以整个结构的二进制存储的,需要考虑大小端的问题。

作者:iEternity
链接:https://www.zhihu.com/question/65629444/answer/693414175
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

这篇关于Redis源码学习 - 1.8 - 有序集合的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!