【Redis系列5】Redis(有序)集合对象之intset(整数集合)和skiplist(跳跃表)实现原理分析

| OBJ_ENCODING_INTSET | 使用整数集合实现的集合对象 | intset |

| OBJ_ENCODING_HT | 使用字典实现的集合对象 | hashtable |

intset编码

intset(整数集合)可以保存类型为int16_t，int32_t，int64_t的整数值，并且保证集合中没有重复元素。

intset数据结构定义如下(源码inset.h内)：

typedef struct intset {

uint32_t encoding;//编码方式

uint32_t length;//当前集合中的元素数量

int8_t contents[];//集合中具体的元素

} intset;

下图就是一个intset的集合对象简图：

encoding

encoding记录了当前集合的编码方式，主要有三种：

• INTSET_ENC_INT16

此时contents[]内的每个元素都是一个int16_t类型的整数值，范围是：-32768 ~ 32767(-215 ~ 215-1)

• INTSET_ENC_INT32

此时contents[]内的每个元素都是一个int32_t类型的整数值，范围是：-2147483648 ~ 2147483647(-231 ~ 231-1)

• INTSET_ENC_INT64

此时contents[]内的每个元素都是一个int64_t类型的整数值，范围是：-9223372036854775808 ~ 9223372036854775807(-263 ~ 263-1)

contents[]

contents[]虽然结构的定义上写的是int8_t类型，但是实际存储类型是由上面的encoding来决定的。

整数集合的升级

假如一开始整数集合中的元素都是16位的，采用了int16_t类型来存储，此时需要再存储一个32位的整数，那么就需要对原先的整数集合进行升级，升级之后才能将32位的整数放入整数集合内。

升级主要有4个步骤：

• 1、根据新添加元素的类型来扩展底层数组空间的大小，按照升级后现有元素的位数来分配新的空间。

• 2、将现有的元素进行类型转换，并将转换类型后的元素从后到前逐个重新放回到数组内。

• 3、将新元素放到数组的头部或者尾部（因为触发升级的条件就是当前数组的整数类型无法存储新元素，所以新元素要么比现有元素都大，要么就比现有元素都小）。