Redis 整数集合、压缩列表

• 整数集合（intset）：一个不可重复的整数元素集合。
• 压缩列表（ziplist）：为了节约内存而设计的线性数据结构。

第六章 整数集合

6.1 整数集合的实现

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

intset.png

• contents[]：有小到大排列的不重复的整数数组。
• length：contents[]中encoding类型元素的个数，不是数组长度。
• encoding：虽然contents[]是int8_t类型，但具体使用时的编码方式由encoding决定，encoding有三种对应C的基础类型分别是INTSET_ENC_INT16对应 int16_t、INTSET_ENC_INT32对应 int32_t、INTSET_ENC_INT64对应 int64_t，encoding规则按最大的元素使用的标准计算，下面看一下encoding升级过程。

6.2 升级

• 添加新元素时，新元素比encoding的标准大，也就是encoding不满足新元素的容量时需要升级。
• 升级大概过程就是：申请空间，旧元素位置移动，插入新元素，修改encoding。

6.3 升级的好处

• 原因很直接：节约内存

6.4 降级

• 整数集合中不存在降级，也就是即使移除所有大元素，数组也不会有和升级相反的降级操作 。

---

第七章 压缩列表

7.1 压缩列表的构成

压缩列表结构.png

• zlbytes：整个结构占用的字节数。
• zltail：从结构起始，也就是zlbytes算起，到最后一个数据节点的字节数。
• zllen：数据节点数量。
• entryX：具体的数据存储。
• zlend：收尾字符。

7.2 压缩列表节点的构成

• 节点可以保存字节数组或整数值。
• 节点由previous_entry_length、encoding、content三部分组成

7.2.1 previous_entry_length

• previous_entry_length：记录前一个节点的长度。因为地址连续，计算前一个节点时可以直接随机访问。
• 如果前一个节点大于254字节，previous_entry_length设置为1字节。大于256时previous_entry_length为5字节，并且以0xFE开头，后四个字节保存长度。

7.2.1 encoding

• 保存数据的类型和长度。
• encoding代表字节数组根据数组长度有三种情况，分别是1、2、5字节，最高位对应00、01、10，具体长度保存在后续字节中。
• encoding代表数字：固定1字节，最高位是11，后续根据位不同区分int32_t、int16_t等数据类型。

7.2.1 content

• 保存真正的节点数据

7.3 连锁更新

• 扩容更新：因为previous_entry_length属性的长度是根据前一个节点是否大于254字节决定的，例如极限情况下所有节点字节都介于250到253之间，头部放入一个大于254字节的节点，后面所有节点的previous_entry_length都要扩容，每次扩容要重新执行空间分配，导致所有节点连锁更新。
• 反之删除节点也会有这种情况，但举例比较极限，几乎不会出现。