【Redis】三、Redis整数集合和压缩列表

整数集合

整数集合(intset)是集合建的底层实现之一,当一个集合只包括整数值的元素，并且这个集合的元素数量不多时,Redis就会用整数集合作为集合建的底层实现

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

contents 数组是整数集合的底层实现: 数组中的各个项按值大小有序排列，并且数组中不包含任何重复项;

1. 整数集合是集合建的底层实现之一

2. 整数集合的底层实现为数组,这个数组以有序、无重复的方式保存集合元素，在有需要的时候，程序会根据新添加元素的类型，改变这个数组的类型;
   例如 数组里面保存的 是int16_t位的1、2、3整数 ,如果后来添加int32_t类型的65535整数,那就会将整个集合升级为int32_t 类型的; 并且之前的int16_t类型的1、2、3也会用int32_t类型来保存；

3. 升级操作为整数集合带来了操作上的灵活性,并且尽可能的节约了内存;
   之所以说节约内存,是如果我们存进的整数如果都是 int16_t类型的那么只会用int16_t类型的来保存,这样能够使用更少的内存,只有当存入了 int32_t才会升级;

4. 整数集合只支持升级操作，不支持降级

压缩列表

压缩列表是一种数据结构，这种数据结构的功能是将一系列数据与其编码信息存储在一块连续的内存区域，这块内存物理上是连续的，逻辑上被分为多个组成部分，其目的是在一定可控的时间复杂读条件下尽可能的减少不必要的内存开销，从而达到节省内存的效果

常态的压缩列表内存编码如上图所示，整个内存块区域内分为五个部分，下面分别介绍着五个部分：

zlbytes：

存储一个无符号整数，固定四个字节长度，用于存储压缩列表所占用的字节，当重新分配内存的时候使用，不需要遍历整个列表来计算内存大小。

zltail：

存储一个无符号整数，固定四个字节长度，代表指向列表尾部的偏移量，偏移量是指压缩列表的起始位置到指定列表节点的起始位置的距离。

zllen：

压缩列表包含的节点个数，固定两个字节长度，源码中指出当节点个数大于2^16-2个数的时候，该值将无效，此时需要遍历列表来计算列表节点的个数。

entryX：

列表节点区域，长度不定，由列表节点紧挨着组成。

zlend：

一字节长度固定值为255，用于表示列表结束。

列表节点

上面介绍了压缩列表的总体内存布局，对于初entryX区域以外的四个区域的长度都是固定的，下面再看看entryX区域的编码情况。

每个列表节点由三部分组成：

每个压缩列表节点区域头部包含两部分，一部分叫做previous length，另一部分叫encoding，最后是主体内容，叫做content，下面分别介绍他们：

previous length

用于存储上一个节点的长度，因此压缩列表可以从尾部向头部遍历，即当前节点位置减去上一个节点的长度即得到上一个节点的起始位置。previous length的长度可能是1个字节或者是5个字节，如果上一个节点的长度小于254，则该节点只需要一个字节就可以表示前一个节点的长度了，如果前一个节点的长度大于等于254，则previous length的第一个字节为254，后面用四个字节表示当前节点前一个节点的长度。这么做很有效地减少了内存的浪费。

encoding

节点的encoding保存的是节点的content的内容类型以及长度，encoding类型一共有两种，一种字节数组一种是整数，encoding区域长度为1字节、2字节或者5字节长

content

content区域用于保存节点的内容，节点内容类型和长度由encoding决定，上面可以看出目前content的内容类型有整数类型和字节数组类型，且某些条件下content的长度可能为0。

相信到这里，我们都明白了压缩列表的原理，压缩列表并不是对数据利用某种算法进行压缩，而是将数据按照一定规则编码在一块连续的内存区域，目的是节省内存。下面我们看看压缩列表在Redis中的应用领域。

为啥要使用压缩列表

使用压缩列表的好处除了节约内存之外，还有减少内存碎片的作用，我把这种行为叫做"合并存储"，也就是将很多小的数据块存储在一个比较大的内存区域

压缩列表的问题

添加新节点到压缩列表,或者从压缩列表中删除节点,可能会引发连锁更新操作，但这种操作出现的几率不高