Redis底层数据结构之set
前言
与Java中的HashSet一样，Redis中的set也是无序且存储的元素不重复。set类型其底层有两种实现方式：
- 当
value是整数值时，且数据量不大时使用inset来存储 - 其他情况都是用字典
dict来存储
inset
Redis中inset的结构定义如下所示：
typedf struct inset{
// 编码方式有三种
// 默认 INSET_ENC_INT16
uint32_t encoding;
// 集合元素个数
uint32_t length;
// 实际存储元素的数组
int8_t contents[];
}inset;
# 16位，2个字节，表示范围 -2^16 ~ 2^16
# define INTSET_ENC_INT16 (sizeof(int16_t))
# 32位，4个字节，表示范围 -2^32 ~ 2^32
# define INTSET_ENC_INT32 (sizeof(int32_t))
# 64位，8个字节，表示范围 -2^64 ~ 2^64
#define INTSET_ENC_INT64 (sizeof(int64_t))
各属性含义如下：
-
encoding：编码格式，共有三种，分别INTSET_ENC_INT16、INSET_ENC_INT32和INSET_ENC_INT64，分别对应不同的范围。Redis为了尽可能地节省内存，会根据插入数据的大小选择不一样的类型来进行存储 -
length：元素数量，记录了保存数据的数组contents中共有多少个元素，这样获取个数的时间复杂度就是O(1)。 -
contents：数组，真正存储数据的地方，数组是按照从小到大有序排列的，并且不包含任何重复项。
intset的示意图如下所示：
inset中整数的升级过程
假设现在有一个inset，之前存储到元素都是在-2^16 ~ 2^16之间的整数元素，也就是说inset底层使用INTSET_ENC_INT16的编码格式来存储。现在要新添加一个元素，其在-2^32 ~ 2^32范围内，此时inset就会选择INTSET_ENC_INT32的编码格式encoding来存储，这时就会发生整数的升级过程。其整体流程总结如下：
-
了解旧的存储格式，计算出目前已有元素占用内存大小，计算规则是length * encoding，如 4* 16=64
-
确定新的编码格式，当原有的编码格式不能存储下新增的数据时，此时就要选择新的合适的编码格式
-
根据新的编码格式计算出需要新增的内存大小，然后从尾部将数据插入
-
根据新的编码格式重置之前的值，此时
contents存在两种编码格式设置的值，就需要进行统一，从插入新数据的起始位置开始，从后向前将之前的数据按照新的编码格式进行移动和设置。从后往前是为了防止数据被覆盖
优点：节省内存，根据存入的数据大小选择合适的编码方式，且只在必要的时候进行升级操作。
缺点：升级过程耗费系统资源，还有就是不支持降级，一旦升级就不可以降级。
总结
