《Redis设计与实现》读书笔记(四)整数集合

158 阅读2分钟

整数集合存在的意义

整数集合(intset)是集合键的底层实现之一,当一个集合只包含整数值元素,并且集合的元素数量不多时(限制值默认 server.set_max_intset_entries = OBJ_SET_MAX_INTSET_ENTRIES = 512),Redis就会使用整数集合作为集合键的底层实现

整数集合的特点

  • 类型为int16_t、int32_t、int64_t的整数值
  • 集合中不出现重复的元素
  • 有序

整数集合结构

  typedef struct intset {
      //编码方式
      uint32_t encoding;
      //集合包含的元素数量
      uint32_t length;
      //保存元素的数组
      int8_t contents[];
  } intest
  1. contents数组是整数集合的底层实现:整数集合中每个元素都是contents数组的一个数组项(item),各个项在数组中是按值的大小从小到大有序的排列,并且不会出现任何重复项。
  2. length属性记录了整数集合包含的元素数量,也就是contents数组的长度
  3. contents类型取决于encoding属性的值
    (1)如果encoding属性的值为INTSET_ENC_INT16,那么contents是一个int16_t类型的数组,数组里每个项都是一个int16_类型的整数值(min -32768 max 32767) (2)如果encoding属性的值为INTSET_ENC_INT32,那么contents是一个int32_t类型的数组,数组里每个项都是一个int32_类型的整数值(min -2147483648 max 2147483647) (3)如果encoding属性的值为INTSET_ENC_INT64,那么contents是一个int64_t类型的数组,数组里每个项都是一个int64_类型的整数值(min -9223372036854775808 max 9223372036854775807)

整数集合升级

添加元素时,如果新元素的类型比整数集合中现有看的所有元素的类型都要长时,整数集合需要先进性升级(upgrade),然后才能将新元素添加到整数集合里。

升级的步骤(分三步)

  1. 根据新元素类型,扩展整数集合底层数组的空间大小,并为新元素分配空间
  2. 将底层数组现有的所有元素都转换成与新元素相同的类型,并将类型转换后的元素放置到正确的位置上,而且放置过程中,需要维持底层数组的有序性质不变
  3. 将新元素放置到底层数组中

时间复杂度

每次向整数集合添加新元素都可能会引起升级,每次升级都需要对底层数组中已有元素的进行类型转换,所以添加新元素的时间负责度为O(N)

好处

  1. 提升灵活性
  2. 节约内存