整数集合存在的意义
整数集合(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
- contents数组是整数集合的底层实现:整数集合中每个元素都是contents数组的一个数组项(item),各个项在数组中是按值的大小从小到大有序的排列,并且不会出现任何重复项。
- length属性记录了整数集合包含的元素数量,也就是contents数组的长度
- 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),然后才能将新元素添加到整数集合里。
升级的步骤(分三步)
- 根据新元素类型,扩展整数集合底层数组的空间大小,并为新元素分配空间
- 将底层数组现有的所有元素都转换成与新元素相同的类型,并将类型转换后的元素放置到正确的位置上,而且放置过程中,需要维持底层数组的有序性质不变
- 将新元素放置到底层数组中
时间复杂度
每次向整数集合添加新元素都可能会引起升级,每次升级都需要对底层数组中已有元素的进行类型转换,所以添加新元素的时间负责度为O(N)
好处
- 提升灵活性
- 节约内存