Redis设计与实现第七章笔记

date

Jul 22, 2021

slug

Redis设计与实现第七章笔记

status

Published

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

每个压缩节点可以保存一个字节数组或者一个整数值

previous_entry_length：记录前一个节点的长度，可以是1字节或者5字节。如果前一节点长度小于254字节，那么previous_entry_length属性长度为1字节，前一节点的长度就保存在这一个字节里面；如果大于254字节，那么该属性为5字节，其中属性的第一字节会被设置为0xFE(十进制254)，而之后的四个字节则用于保存前一字节长度。可以用来实现表尾向表头遍历操作

encoding：记录了content属性保存数据的类型和长度。属性为1，2，5字节长，最高位为00、01或者10的是字节数组编码，表示content保存着字节数组，长度由除去最高两位之后的其他位记录；1字节长，值的最高位以11开头的是整数编码：表示节点保存的是整数值，长度由除去最高两位之后的其他位记录

考虑一种情况：在一个压缩列表中，有多个连续的、长度介于250字节到253字节之间的节点e1至eN。

e1和eN的所有节点的previous_entry_length属性都是1字节长的。这时在表头插入一个长度大于等于254字节的新节点New

这就引发了previous_entry_length的连锁更新，删除节点也可以引起连锁更新（大节点后面的小节点删了）

最坏的复杂度为O(N^2)。

连锁更新造成性能问题的几率是很低的：