压缩列表是列表键与哈希键的底层实现之一。当一个列表键只包含少量的列表项，并且每个列表项要么就是小整数值，要么就是长度较短的字符串，那么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设计与实现》，仅在此做学习与大家分享。
网友评论