redis数据结构之整数集合

2018-11-03 本文已影响3人 0爱上1

用处

整数集合是集合键的底层实现之一

当一个集合中只包含整数值元素且元素的数量不多时，redis就会使用整数集合作为集合键的底层实现

整数集合可以保存类型为int16_t，int32_t，或者int64_t的整数值，并且会保证集合中不会出现重复元素

redis用intset结构来表示一个整数集合

typedef struct intset {
  // 编码方式
  uint32_t encoding;

  // 集合包含的元素数量
  uint32_t length;

  // 保存元素的数组
  int8_t contents[];
}

其中主要是contents数组，用来存储整数集合的每一个元素item，各个项在数组中按值的大小从小到大有序的排列，并且数组中不包含任何重复项

这里需要注意的是：虽然intset结构将contents属性声明为了int8_t类型，但实际上contengs数组并不保存任何的int8_t类型的值，contents数组的真正类型取决于encoding属性的值

即这里如果计算一个整数集合中元素占用大小的话需要根据encoding属性的值得出contents数组的item元素的类型为什么，再乘以length属性的值即可

既然提到升级，那么什么样的场景需要进行整数集合的升级？具体的升级又是升级什么？

前面说到了整数集合具体的contents类型是由encoding属性决定的，那么我们假设一种情况：

当一个整数集合中只有int16_t类型的item时，那么这个整数集合的encoding值为int16_t 即可，不需要采用int64_t类型来浪费内存，

如果这个时候我们向该整数集合中添加了一个int64_t 类型的整数，比如：-2675256175807981027 这个时候现有的整数集合元素类型为int16_t就放不下该元素，这个时候就需要进行整数集合的升级，升级的是整数集合中存储元素的类型

每当我们将一个新元素添加进整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长的时候，整数集合就需要进行升级，升级以后才能将新元素添加到整数集合中

假如现有整数集合中有三个int16_t 类型的元素 1， 2， 3

新元素为int32_t 类型的65535

在第一步中，扩展数组的空间大小是需要根据新元素的类型计算出扩展后的数组空间大小

那么计算出扩展后的底层数组的占用空间大小为：4 * 32 = 128位

另一个需要注意的是数组在内存中是一块连续的内存空间

数组中的下标对应的内存的体现就是位，比如128位的数组，分四个元素，那么对应0下标的元素占用的位就是0-31 ，相应的1下标对应的位是32-63 ，2下标对应的位为64-95 ，而下标3即第四个元素对应的位为96-127位

因为整数集合提供了自动升级功能，所以我们在使用时并不需要担心出现类型错误，可以随意的将不同类型的整数添加到整数集合中

redis设计整数集合时，是可以将整数集合中元素的类型设计成int64_t的，这样带来结果是虽然可以向其中任意添加int16_t，int32_t，int64_t 类型的元素不用担心类型错误，但是弊端就是浪费内存，redis作为内存数据库，对内存尤为重视

整数集合不支持自动降级，一旦对数组进行了升级，encoding编码属性就会一直保存升级以后的状态