Redis学习笔记(五)压缩列表

database

压缩列表是列表键与哈希键的底层实现之一。当一个列表键只包含少量的列表项,并且每个列表项要么就是小整数值,要么就是长度较短的字符串,那么Redis就会使用压缩列表来做列表键的底层实现。

压缩列表是为了节约内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多的节点,每个节点可以保存一个字节数组或一个整数值。

压缩表可以包含:

1、长度小于等于63字节的字节数组

2、长度小于16383字节的字节数组

3、长度小于等于4294967295字节的字节数组

4、4位长度的无符号整数

5、1字节长度有符号整数

6、3字节长的有符号整数

7、int16类型的整数

8、int32类型的整数

9、int64类型的整数

 

每个压缩列表节点都由previous_entry_length、encoding、content三部分组成

说明:previous_entry_length 保存前一节点的长度,如果前一个节点长度小于254节点,那么previous_entry_length属性需要1字节长的空间来保存这个长度值;如果超度254则需要5个字节长的空间来保存这个长度。

 

连锁更新

由于是连续的内存片段,当在中间插入一个元素时,

 

e1节点的 previous_entry_length属性仅长1字节,当将new节点设置为前置节点时,由于e1的previous_entry_length 长度为1无法保存new节点的长度,所以需要将长度扩展到5个字节空间,因此需要对列表进行空间重新分配操作。同理,如果引发了对e2、e3.。。。的扩展,这种操作称为连锁更新。

连锁更新在最坏的情况下需要对压缩列表执行n次空间的重分配操作,每次空间重分配的最坏复杂度为O(N),所以连锁更新最坏的的复杂度为O(N2)。

 

-------- end --------

每天学一点,总会有收获。

说明:尊重作者知识产权,文中内容参考《Redis设计与实现》,仅在此做学习与大家分享。

 

 

以上是 Redis学习笔记(五)压缩列表 的全部内容, 来源链接: utcz.com/z/533633.html

回到顶部