Redis数据结构—整数集合与压缩列表

• Redis数据结构—整数集合与压缩列表
  • 整数集合的实现
  • 整数集合的升级
  • 整数集合不支持降级
  • 压缩列表的构成
  • 压缩列表节点的构成
  • 小结

Redis数据结构—整数集合与压缩列表

大家好，我是白泽。今天我们将学习Redis的整数集合与压缩列表这两个数据结构，且在本文中我将尽量只描述这两种结构中重要的部分，而非面面俱到，因为我学Redis数据结构的初衷是为了我能更好理解后面要讲到的Redis对象，而非真的去研究Redis深层的实现，不会过分深入，够用就好

Redis对象的实现在底层用到了我们目前讲解到的这些数据结构：简单动态字符串SDS、双端链表、字典、以及今天要讲解的整数集合与压缩列表，因此从底层数据结构开始能为我们理解Redis打下坚实的基础，成为面试杀手

整数集合的实现

整数集合是Redis用于保存整数值的集合抽象数据结构，它可以保存int16_t、int32_t、int64_t的整数值，且保证集合中不出现重复元素

contents[]数组的类型这里看上去是int8_t，但事实上contents[]的数据类型依靠encoding的属性决定（encoding可以选择为INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64表示contents[]中元素的数据类型）

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

下面给出的图片是一个包含了五个int16_t类型整数值的整数集合，int16_t表示每个整数是由16位共2个字节表示，因此此时contents[]数组大小为：5 * 16 = 80位

整数集合的升级

当我们向一个已经存在的整数集合中添加元素时，如果加入的元素的数据类型比contents[]数组元素的数据类型长，则整数集合需要进行升级，举个例子，我要在上面那个大小5的16位整数集合中插入一个类型为int32_t的整数65535：

1. 升级首先要做的是，根据新元素的长度，扩大空间，目前有5个元素，加入一个后有6个，且int16_t的元素要升级为int32_t类型（需要6 * 32 = 192位的空间），因此需要先动态分配内存空间如下：

2. 移动元素的位置，将14632往后移动到新的位置，末尾留下一个位置存放32位的65535

3. 同理移动233、18、-5、-6370，并最后将末尾的空间中存入65535

整数集合不支持降级

如果因为插入一个32位的整数使得原本16位的contents[]数组转变为32位，后面又删去了这个32位的整数，这个整数集合将不会降级成16位的contents[]数组

压缩列表的构成

因为压缩列表好像面试中不太出现，所以略讲~

压缩列表就是一块连续的内存，一种顺序型的数据结构，entryX是一个个节点，存放数据，其他属性用于描述整个压缩列表的整体情况（占用内存、节点个数等）

zlbytes：记录整个压缩列表占用的内存字节数

zltail：记录压缩列表表尾节点距离压缩列表的起始地址的偏移量

zllen：记录了压缩列表中节点数量

entryX：压缩列表的各个节点

zlend：特殊值0xFF，用于标记压缩列表的末端

压缩列表节点的构成

节点就是一个个的entryX，是压缩列表的核心，每个节点由三部分组成：

1. previous_entry_length：记录前一个节点的长度，因此可以从当前节点的起始地址计算出前一个节点的起始地址，从而实现压缩列表的逆序遍历
2. encoding：记录的content属性所保存数据的类型以及长度
3. content：负责保存节点的值（一个字节数组或整数）

小结

到目前为止，白泽已经带大家初步学习了Redis底层所有的数据结构：简单动态字符串SDS、双端链表、字典、跳跃表、整数集合、压缩列表，下一篇博客将带大家学习Redis的对象（Redis的对象底层就是这些数据结构实现的），再后面就正式讲解Redis数据库的知识点了，敬请期待~