Redis的底层数据结构-整数集合

整数集合(intset)是Redis用于保存整数值的集合抽象数据类型,它可以保存类型为int16_t、int32_t 或者int64_t 的整数值,并且保证集合中不会出现重复元素。

  定义如下:

typedef struct intset{
     //编码方式
     uint32_t encoding;
     //集合包含的元素数量
     uint32_t length;
     //保存元素的数组
     int8_t contents[];
 
}intset;

  整数集合的每个元素都是 contents 数组的一个数据项,它们按照从小到大的顺序排列,并且不包含任何重复项。

  length 属性记录了 contents 数组的大小。

  需要注意的是虽然 contents 数组声明为 int8_t 类型,但是实际上contents 数组并不保存任何 int8_t 类型的值,其真正类型有 encoding 来决定。

  ①、升级

  当我们新增的元素类型比原集合元素类型的长度要大时,需要对整数集合进行升级,才能将新元素放入整数集合中。具体步骤:

  1、根据新元素类型,扩展整数集合底层数组的大小,并为新元素分配空间。

  2、将底层数组现有的所有元素都转成与新元素相同类型的元素,并将转换后的元素放到正确的位置,放置过程中,维持整个元素顺序都是有序的。

  3、将新元素添加到整数集合中(保证有序)。

  升级能极大地节省内存。

  ②、降级

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

上一篇:activeMQ、rabbitMQ学习对比心得


下一篇:sscanf中的format格式