定义
上一节其实已经提到过，压缩列表，顾名思义，就是排列紧凑的列表。 压缩列表在 Redis 中有两种编码方式，一种是 ZIPLIST，平常说的压缩列表其实一般就是指 ZIPLIST，一种是 LISTPACK，LISTPACK 是在 Redis 5.0 引入，直到 Redis 7.0 完全替代了 ZIPLIST。
使用场景
压缩列表主要为底层数据结构提供紧凑型的数据存储方式，能节约内存（节省链表指针的开销），小数据量的时候遍历访问性能好（CPU 里有高速缓存，也就是 L1~L3 哪些，读取内存的时候一般按照 cache line 来读内存，ZIPLIST 的话内存连续，空间局部性比链表好很多，遍历的时候缓存命中率相对也会高）
ZIPLIST 整体结构
我们先看 ZIPLIST，虽然已经有 LISTPACK，但实际面试中聊得比较多的，还是 ZIPLIST。 ZIPLIST 的结构：
<zlbytes> <zltail> <zllen> <entry> <entry> .. <entry> <zlend>比如，有 3 个节点的 ZIPLIST 结构： 
各字段的含义如下。
- zlbytes：表示 ZIPLIST 一共占了多少字节，包含 zlbytes 本身占据的字节数。
- zltail：ZIPLIST 的尾巴节点（entry3）相对于 ZIPLIST 的开头（起始指针），偏移的字节数。通过这个字段可以快速定位到尾部节点。例如，有一个 ZIPLIST，变量 a 指向它的开头，如果要获取 ZIPLIST 的尾巴节点，即 ZIPLIST 里的最后一个节点，可以 a + zltail 的值定位到它。如果没有尾巴节点，就定位到 zlend。
ZIPLIST 节点结构
ZIPLIST ENTRY 定义如下：
<prevlen> <encoding> <entry-data>同样，我们来看看，各字段的含义：
- prevlen：表示上一个节点的数据长度。通过这个字段，可以定位上一个节点的起始位置，也就是 p - prevlen 可以跳到前一个节点的开头位置，实现从后往前操作，所以压缩列表可以从后往前遍历。 如果前一个节点的长度，也就是前一个 entry 的大小，小于 254 字节，那么 prevlen 属性要用 1 个字节的空间来保存这个长度值。 如果前一个节点的长度大于等于 254 字节，255 是特殊字符，被 zlend 使用了，那么 prevlen 属性要用 5 字节长的空间来保存这个长度值，注意 5 个字节中的第一个字节为 11111110，也就是 254，标志这是个 5 字节的 prevlen 的信息，剩下 4 字节来表示大小；
- encoding：编码类型。编码类型里还包含了一个 entry 的长度信息，可用于正向遍历；
- entry-data：实际的数据。
encoding 说明
encoding 字段是一个整型数据，其二进制编码由内容数据的类型和内容数据的字节长度两个部分组成，例举几种情况，如下。 字符串类型
- 编码：00pppppp；大小：1字节；类型：String 类型，且字符串长度小于 2^6，即小于等于 63
- 编码：11000000；大小：1字节；类型：2个字节的 int16 类型 注意，如果是 String 类型，那么 encoding 有两部分，一般是前几位标识类型、后几位标识长度。 但如果是 int 类型，整体 1 字节编码，就只标识了类型，为什么没有大小呢，因为 int 类型的具体类型就自带了大小，比如 int16，就是 16 为，2字节的大小，不需要 encoding 特别标识。 encoding 的编码规则比较复杂，我们其实只需要理解它的核心思想，面试中能够讲清怎么区分不同类型即可，不用背它的这些具体编码，这个很难去记，也没有必要去记。
ZIPLIST 查询数据
我们聚焦看两个关键的查询操作，来理解 ZIPLIST 是如何运作的。
查询 ZIPLIST 的数据总量
由于 ZIPLIST 的 header 定义了记录节点数量的字段 zlen，所以通常是可以在 O(1) 时间复杂度直接返回的，为什么说通常呢？因为 zllen 是 2 个字节的，当 zllen 大于 65534（2的16次方-1）时，zllen 就存不下了，此时 zllen 等于 65535，所以真实的节点数量需要遍历来得到。 这样设计的原因是 Redis 中应用 ZIPLIST 都是为了节点个数少的场景，所以将 zllen 设计得较小，节约内存空间。
查询 ZIPLIST 的指定数据节点
在 ZIPLIST 中查询指定数据的节点，需要遍历这个压缩列表，平均时间复杂度是 O(N)。
ZIPLIST 更新数据
ZIPLIST 的更新就是增加、删除数据，ZIPLIST 提供头尾增减的能力，但是操作平均时间复杂度是 O(N)，因为在头部增加一个节点会导致后面节点都往后移动。 其中要注意的是更新操作可能带来连续更新。上面所说的增加节点导致后移，不是连锁更新。连锁更新是指，新增一个节点，如果该节点长度超过 254，则后面节点的 prevlen（原本 1 个字节）就要变为 5 个字节，导致后面这个节点长度也增大了，如此连锁反应，造成连锁更新。如果新增节点长度较小，不会造成后续节点的 prevlen 变长，那么只会带来后面节点单纯的位置后移，这不叫连锁更新。 大家可能会比较担心连锁更新带来的性能问题，但在实际的业务中，很少会刚好遇到需要迭代更新超过 2 个节点的情况，所以 ZIPLIST 更新平均复杂度，还是可以看做 O(N)。不过，ZIPLIST 最大的问题还是连锁更新导致性能不稳定。 
LISTPACK 优化
连锁更新原因分析
LISTPACK 是为了解决 ZIPLIST 最大的痛点–连锁更新，我们先来看，ZIPLIST 的问题根源。 我们知道，ZIPLIST 需要支持 LIST，LIST 是一种双端访问结构，所以需要能从后往前遍历，上面有讲，ZIPLIST 的数据节点的结构是：
<prevlen> <encoding> <entry-data>其中，prevlen 就标识上一个节点的数据长度，通过这个字段可以定位上一个节点的数据，可以说，连锁更新问题，就是因为 prevlen 导致的。
解决方案
我们需要一种不记录 prevlen，并且还能找到上一个节点的起始位置的方法，Redis 用了一种很巧妙的方式。 我们直接看 LISTPACK 的节点定义：
<encoding-type> <element-data> <element-tot=len>encoding-type 是编码类型，element-data 是数据内容，element-tot-len 存储整个节点除它自身之外的长度。 找到上一个节点的秘密就藏在 element-tot-len： element-tot-len 所占用的每个字节的第一个 bit 用于标识是否结束。0 是结束，1 是继续，剩下 7 个 bit 来存储数据大小。当我们需要找到当前元素的上一个元素时，我们可以从后向前一次查找每个字节，找到上一个 Entry 的 element-tot-len 字段的结束标识，就可以算出上一个节点的首位置了。举个例子，如下图。
常见问题
ZIPLIST 有什么优点？
ZIPLIST 是怎么压缩数据的？
底层数据结构体是 ZIPLIST 的数据结构，可以双端遍历吗？
ZIPLIST 查询节点个数的时间复杂度是多少？
ZIPLIST 插入的时间复杂度是多少？
连锁更新是什么问题？
如何解决连锁更新？
