前言

Ziplist 是一种内存紧凑型，经过特殊编码的双向链表，用来取代常规的双向链表。可以存储字符和整数，并且提供了双向的 push 和 pop 操作。但是，每一次的 push 和 pop 都需要重新分配内存，如果 Ziplist 本身占用的内存很大，那么 push 和 pop 操作也会消耗较大的 CPU 资源。

压缩链表最大的特点就是设计成了内存紧凑型，可以充分利用 CPU 高速缓存，并且可以给不同的数据类型进行编码，节省内存。

但是压缩链表也有缺点：

保存的元素过多，查询会变慢。
插入或者删除一个元素时，需要重新分配内存。而且有可能会引发连锁更新。

List 会使用压缩链表和常规链表作为底层数据结构。当链表元素小于 512 个，并且每一个元素的大小小于 64 byte，才会使用压缩链表。否则直接使用常规链表。

结构

Ziplist

压缩链表是内存连续的，它占用一片连续的内存空间。

压缩链表在头部有3个字段，在尾部有1个字段

zlbytes，表示使用了多少内存，最大值为 2^32 – 1。
zltail，表示最后一个 entry 的偏移量，通过这个字段可以找到最后一个元素。主要用于从后往前遍历。
zllen，表示有多少个元素 entry。但是不代表只能存储 2^16 -1 个元素，在元素数量超过 2^16 – 2 的时候，就会使用 2^16 -1 表示，如果需要获取元素数量，那么就会使用遍历。
zlend，表示 ziplist 的结束符，使用 255 表示。

entry

prevlen，记录前一个元素的长度。搭配 zltail 可以实现从后往前遍历。
encoding，编码，跟 data 的内存有关。
data，记录实际的数据。

prevlen

prevlen 记录的是前一个元素的长度。

当前一个元素的长度小于 254 byte，使用 1 个字节进行记录，此时 prevlen 占用 1 个字节。

当前一个元素的长度大于等于 254 byte，使用 5 个字节进行记录，第 1 个字节为 254，后面 4 个字节记录长度。第 1 个字节记录的 254 主要用于标识。

encoding

encoding 字段是对 data 的编码，用于区分字符和整数，同时记录他们占用的长度。

当 data 为字符串时，encoding 的结构如下：

00xxxxxx，占用 1 byte，高 2 位为 00，字符串的长度小于等于 63 byte，低 6 位记录字符串的长度。
01xxxxxx xxxxxxxx，占用 2 byte，高 2 位为 01，字符串的长度小于等于 16383 byte，低 14 记录字符串的长度。
10000000 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 占用 5 byte，高 8 为 10000000，字符串长度大于等于 16384 byte，低 32 位记录字符串的长度。

当 data 为整数时，encoding 的结构如下：

11000000，表示 16 位的整数，整数范围 0 至 2^16 – 1
11010000，表示 32 位的整数，整数范围 0 至 2^32 – 1
11100000，表示 64 位的整数，整数范围 0 至 2^64 – 1
11110000，表示 24 位的整数，整数范围 0 至 2^24 – 1
11111110，表示 8 位的整数，整数范围 0 至 2^8 – 1
1111xxxx，如果 xxxx 在 0001 – 1101 之间，那么低 4 位表示 0 – 12 的整数。此时不再有 data 字段。最大值为 12 是因为 1110 已经被表示为 8 位的整数，不能使用。1111 也被 zlend 字段所使用。

当高 2 位为 11 时，就是表示整数，否则表示字符串。