Redis数据库整数集合大概介绍

Redis intset 整数集合 笔记

  • 整数集合是集合键的底层实现之一,当一个集合值包含整数值元素,并且这个集合的元素数量不多时,Redis就会使用整数集合做为集合键的底层实现。

整数集合的实现

  • 整数集合(intset)是Redis用于保存整数值的集合抽象数据结构,可以保存类型为int16_t、int32_t、int64_t的整数值,并且保证集合中不会出现重复元素。
  • 每个intset.h/intset结构表示一个整数集合:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    #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; //编码方式
    uint32_t length; //集合包含的元素数量 即contents数组的长度
    int8_t contents[]; //保存元素的数组 整数集合的每个元素都是contents数组的一个数组项,各个项在数组中按值的大小从小到大排序,并且数组中不包含任何重复项。
    } intset;
  • contents结构类型声明为int8_t,但实际上contents不保存任何int8_t类型的值,contents数组的真正类型取决于encoding属性的值。encoding的值可以是INTSET_ENC_INT16,INTSET_ENC_INT32,INTSET_ENC_INT64。

升级

  • 当添加一个新元素到整数集合里面,并且新的类型比集合现有所有元素的类型都长时,整数集合需要升级,然后将新元素添加到整数集合里面。
  • 升级整数集合三步进行
    1. 根据新元素类型,扩展整数集合底层数组空间大小,并为新元素分配空间
    2. 将底层数组现有元素转换成与新元素相同的类型,并将类型转化后的元素放在争取的位上,在放置元素的过程中,需要继续维持底层数组的有序性质不变。
    3. 将新元素添加到底层数组里面。
  • 想整数集合添加新元素的时间复杂度为O(N)

升级的好处

1. 提高数组集合操作的灵活性, C语言为静态类型语言,为了避免类型错误,通常不会将两种不同类型的值放在同一个数据结构中。整数集合通过自动升级底层数组来适应新元素,所以我们可以随意将int16_t, int32_t, int64_t类型的整数添加到集合中,而不必担心类型错误。
2. 尽可能节约内存

整数数组不支持降级,一旦对数组进行了升级,编码会一直保持升级后的状态。