压缩列表

压缩列表（ziplist）是 列表键 和哈希键 的底层实现之一。当一个列表键只蕴含大量列表项，并且每个列表项要么就是小整数值，要么就是长度比拟短的字符串，那么 Redis 就会应用压缩列表来做列表键的底层实现。

压缩列表的形成

压缩列表是 Redis 为了 节俭内存 而开发的，是由一系列非凡编码的 间断内存块组成的程序型数据结构 。一个压缩列表能够 蕴含任意多个节点 （entry）， 每个节点能够保留一个字节数组或者一个整数值。

• zlbytes：4 字节，记录 整个压缩列表占用的内存字节数。在对压缩列表进行内存重调配或者计算 zlend 的地位时应用
• zltail：4 字节，记录压缩列表 表尾节点间隔压缩列表的起始地址有多少个字节。通过这个偏移量，毋庸便当整个压缩列表就能够确定表尾节点的地址
• zllen：记录了压缩列表蕴含的节点数量。当这个属性的值小于 65535 时，这个属性的值就是压缩列表蕴含节点的数量，当这个值等于 65535 时，节点的实在数量须要便当能力计算得出
• entryX：压缩列表蕴含的各个节点，节点的长度由节点保留的内存决定
• zlend：非凡值 0xFF（十进制 255），用于标记压缩列表的末端

压缩列表节点的形成

每个压缩列表能够保留 一个字节数组 或者 一个整数值。

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

previous_entry_length

previous_entry_length 属性以字节为单位，记录了压缩列表中前一个节点的长度。previous_entry_length 属性的长度能够是 1 字节或者 5 字节。

如果前一节点的长度小于 254 字节，那么 previous_entry_length 属性的长度为 1 字节；否则长度为 5 字节，其中属性的第一个字节设置为 0xFE，而之后的四个字节则用于保留前一节点的长度。

压缩列表从表尾向表头遍历操作就是应用这一原理实现的，只有领有了一个指向某个节点起始地址的指针，那么通过这个指针以及这个节点的 previous_entry_length 属性，就能够始终向前一个节点回溯，最终达到压缩列表的表头节点。

encoding

encoding 属性记录了节点的 content 属性所保留数据的类型以及长度。

content

节点的 content 属性负责保留节点的值，节点值能够是一个字节数组或者整数，值的类型和长度由节点的 encoding 属性决定。

连锁更新

因为每个节点的 previous_entry_length 属性都记录了前一个节点的长度，如果存在一个压缩列表中，又多个间断的、长度介于 250 字节到 253 字节之间的节点，这时将一个长度大于等于 254 字节的新节点设置为压缩列表的表头节点，之前的第一个节点中的 previous_entry_length 属性长度仅为 1，没方法保留新节点的长度，所以会对压缩列表执行空间重调配操作，将以后节点的 previous_entry_length 属性从原来的 1 字节长拓展为 5 字节长。

同理，以后节点产生重调配操作后，可能会影响到前面的下一个节点，最坏状况下，可能会始终影响到最初一个节点。

Redis 将这种在非凡状况下产生的 间断屡次空间拓展操作 称之为”连锁更新“。

除了增加新节点可能会引发连锁更新之外，删除节点也可能会引发连锁更新。

因为连锁更新在最坏状况下须要对压缩列表执行 N 次空间重调配操作，而每次空间重调配的最坏复杂度为 O(N)，所以间断更新的最坏复杂度为 O(N²)。

只管连锁更新的复杂度较高，但真正造成性能问题的几率是很低的。首先，压缩列表里恰好有多个间断的、长度介于 250 字节至 253 字节之间的节点，连锁更新才可能被触发，在理论中，这种状况并不多见。其次，即便呈现连锁更新，但只有被更新的节点数量不多，就不会对性能造成任何影响。