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

大家好,我是白泽。今天我们将学习Redis的整数集合与压缩列表这两个数据结构,且在本文中我将尽量只描述这两种结构中重要的部分,而非面面俱到,因为我学Redis数据结构的初衷是为了我能更好理解后面要讲到的Redis对象,而非真的去研究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位的空间),因此需要先动态分配内存空间如下:

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

  1. 同理移动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数据库的知识点了,敬请期待~

评论(0条)

龙8唯一官方网站 游客评论