压缩列表

构成
- 节点
创建
添加
- 将节点添加到末端
- 将节点添加到某个/某些节点的前面
删除
遍历
查找
总结

ziplist 是由一系列特殊编码的内存块构成的列表，一个 ziplist 可以包含多个节点 entry ，每个节点可以保存一个长度受限的字符数组（ 不以 \0 结尾 的 char 数组）或者整数，包括：

字符数组
- 长度小于等于 63 \((2^{6} - 1)\) 字节的字符数组
- 长度小于等于 16383 \((2^{14} - 1)\) 字节的字符数组
- 长度小于等于 4294967295 \((2^{32} - 1)\) 字节的字符数组
整数
- 4 位长，介于 0 至 12 之间的无符号整数
- 1 字节长，有符号整数
- 3 字节长，有符号整数
- int16_t 类型整数
- int32_t 类型整数
- int64_t 类型整数

因为 ziplist 节约内存 的性质，哈希键、列表键和有序集合键初始化的底层实现皆采用 ziplist

更多信息请参考《哈希表》、《列表》和《有序集》

接下来先介绍 ziplist 的组成结构， 以及 ziplist 节点的编码方式

再介绍 ziplist 的添加操作和删除操作的执行过程， 以及这两种操作可能引起的连锁更新现象

最后介绍 ziplist 的遍历方法和节点查找方式

构成

下图展示了一个 ziplist 的典型分布结构：

area        |<---- ziplist header ---->|<----------- entries ------------->|<-end->|

size          4 bytes  4 bytes  2 bytes    ?        ?        ?        ?     1 byte
	    +---------+--------+-------+--------+--------+--------+--------+-------+
component   | zlbytes | zltail | zllen | entry1 | entry2 |  ...   | entryN | zlend |
	    +---------+--------+-------+--------+--------+--------+--------+-------+
				       ^                          ^        ^
address                                |                          |        |
				ZIPLIST_ENTRY_HEAD                |   ZIPLIST_ENTRY_END
								  |
							 ZIPLIST_ENTRY_TAIL

各个域的作用如下：

Table 1: fields of ziplist
域	长度/类型	域的值
zlbytes	uint32_t	整个 ziplist 占用的内存字节数，对 ziplist 进行内存重分配，或者计算末端时使用
zltail	uint32_t	到达 ziplist 表尾节点的偏移量。通过这个偏移量，可以在不遍历整个 ziplist 的前提下，弹出表尾节点
zllen	uint16_t	ziplist 中节点的数量。当这个值小于 UINT16_MAX （65535）时，这个值就是 ziplist 中节点的数量；当这个值等于 UINT16_MAX 时，节点的数量需要遍历整个 ziplist 才能计算得出。
entryX	? ziplist	所保存的节点，各个节点的长度根据内容而定
zlend	uint8_t	255 的二进制值 1111 1111 （UINT8_MAX），用于标记 ziplist 的末端

为了方便地取出 ziplist 的各个域以及一些指针地址， ziplist 模块定义了以下宏：

Table 2: macro of ziplist
宏	作用	算法复杂度
ZIPLIST_BYTES(ziplist)	取出 zlbytes 的值	\(\theta(1)\)
ZIPLIST_TAIL_OFFSET(ziplist)	取出 zltail 的值	\(\theta(1)\)
ZIPLIST_LENGTH(ziplist)	取出 zllen 的值	\(\theta(1)\)
ZIPLIST_HEADER_SIZE	返回 ziplist header 部分的长度，总是固定的 10 字节	\(\theta(1)\)
ZIPLIST_ENTRY_HEAD(ziplist)	返回到达 ziplist 第一个节点（表头）的地址	\(\theta(1)\)
ZIPLIST_ENTRY_TAIL(ziplist)	返回到达 ziplist 最后一个节点（表尾）的地址	\(\theta(1)\)
ZIPLIST_ENTRY_END(ziplist)	返回 ziplist 的末端，也即是 zlend 之前的地址	\(\theta(1)\)

ziplist header 部分的长度总是固定的（4 字节 + 4 字节 + 2 字节），因此将指针移动到表头节点的复杂度为常数时间
表尾节点的地址可以通过 zltail 计算得出，因此将指针移动到表尾节点的复杂度也为常数时间

以下是用于操作 ziplist 的函数：

Table 3: function of ziplist
函数名	作用	算法复杂度
ziplistNew	创建一个新的 ziplist	\(\theta(1)\)
ziplistResize	重新调整 ziplist 的内存大小	\(\theta(N)\)
ziplistPush	将一个包含给定值的新节点推入 ziplist 的表头或者表尾	\(\theta(N^{2})\)
zipEntry	取出给定地址上的节点，并将它的属性保存到 zlentry 结构然后返回	\(\theta(1)\)
ziplistInsert	将一个包含给定值的新节点插入到给定地址	\(\theta(N^{2})\)
ziplistDelete	删除给定地址上的节点	\(\theta(N^{2})\)
ziplistDeleteRange	在给定索引上，连续进行多次删除	\(\theta(N^{2})\)
ziplistFind	在 ziplist 中查找并返回包含给定值的节点	\(\theta(N)\)
ziplistLen	返回 ziplist 保存的节点数量	\(\theta(N)\)
ziplistBlobLen	以字节为单位，返回 ziplist 占用的内存大小	\(\theta(1)\)

因为 ziplist 由连续的内存块构成，在最坏情况下，当 ziplistPush 、 ziplistDelete 这类对节点进行增加或删除的函数之后，程序需要执行一种称为 连锁更新 的动作来维持 ziplist 结构本身的性质，所以这些函数的最坏复杂度都为 \(\theta(N^{2})\)

因为这种最坏情况出现的概率并不高， 所以大可以放心使用 ziplist ， 而不必太担心出现最坏情况

节点

一个 ziplist 可以包含多个节点，每个节点可以划分为以下几个部分：

area        |<------------------- entry -------------------->|

	    +------------------+----------+--------+---------+
component   | pre_entry_length | encoding | length | content |
	    +------------------+----------+--------+---------+

以下几个小节将分别对这个四个部分进行介绍

pre_entry_length

pre_entry_length 记录了 前一个节点的长度 ，通过这个值，可以进行指针计算，从而跳转到上一个节点。

area        |<---- previous entry --->|<--------------- current entry ---------------->|

size          5 bytes                   1 byte             ?          ?        ?
	    +-------------------------+-----------------------------+--------+---------+
component   | ...                     | pre_entry_length | encoding | length | content |
	    |                         |                  |          |        |         |
value       |                         | 0000 0101        |    ?     |   ?    |    ?    |
	    +-------------------------+-----------------------------+--------+---------+
	    ^                         ^
address     |                         |
	    p = e - 5                 e

上图展示了如何通过一个节点向前跳转到另一个节点

用指向当前节点的指针 e ， 减去 pre_entry_length 的值（0000 0101 的十进制值， 5）

得出的结果就是指向前一个节点的地址 p

根据编码方式的不同， pre_entry_length 域可能占用 1 字节或者 5 字节：

1 字节：如果前一节点的长度小于 254 字节，便使用一个字节保存它的值
5 字节：如果前一节点的长度大于等于 254 字节，那么将第 1 个字节的值设为 254 ，然后用接下来的 4 个字节保存实际长度

作为例子，以下是个长度为 1 字节的 pre_entry_length 域，域的值为 128 （二进制为 1000 0000 ）

area        |<------------------- entry -------------------->|

size          1 byte             ?          ?        ?
	    +------------------+----------+--------+---------+
component   | pre_entry_length | encoding | length | content |
	    |                  |          |        |         |
value       | 1000 0000        |          |        |         |
	    +------------------+----------+--------+---------+

而以下则是个长度为 5 字节的 pre_entry_length 域，域的第一个字节被设为 254 的二进制 1111 1110 ，而之后的四个字节则被设置为 10086 的二进制 10 0111 0110 0110 （多余的高位用 0 补完）：

area        |<------------------------------ entry ---------------------------------->|

size          5 bytes                                     ?          ?        ?
	    +-------------------------------------------+----------+--------+---------+
component   | pre_entry_length                          | encoding | length | content |
	    |                                           |          |        |         |
	    | 11111110 00000000000000000010011101100110 | ?        | ?      | ?       |
	    +-------------------------------------------+----------+--------+---------+
	    |<------->|<------------------------------->|
	      1 byte       4 bytes

encoding 和 length

encoding 和 length 两部分一起决定了 content 部分所保存的数据的类型（以及长度）。其中， encoding 域的长度为两个 bit ，它的值可以是 00 、 01 、 10 和 11 ：

00, 01 和 10 表示 content 部分保存着字符数组
11 表示 content 部分保存着整数

以 00 、 01 和 10 开头的字符数组的编码方式如下：

Table 4: encoding and length field for node of char array
编码	编码长度	content 部分保存的值
00bbbbbb	1 byte	长度小于等于 63 字节的字符数组
01bbbbbb xxxxxxxx	2 byte	长度小于等于 16383 字节的字符数组
10____ aaaaaaaa bbbbbbbb cccccccc dddddddd	5 byte	长度小于等于 4294967295 的字符数组

表格中的下划线 _ 表示留空，变量 b 、 x 等则代表实际的二进制数据

为了方便阅读，多个字节之间用空格隔开

11 开头的整数编码如下：

Table 5: encoding and length field for node of integer
编码	编码长度	content 部分保存的值
11000000	1 byte	int16_t 类型的整数
11010000	1 byte	int32_t 类型的整数
11100000	1 byte	int64_t 类型的整数
11110000	1 byte	24 bit 有符号整数
11111110	1 byte	8 bit 有符号整数
1111xxxx	1 byte	4 bit 无符号整数，介于 0 至 12 之间

content

content 部分保存着节点的内容，类型和长度由 encoding 和 length 决定。以下是一个保存着字符数组 hello world 的节点的例子：

area      |<---------------------- entry ----------------------->|

size        ?                  2 bit      6 bit    11 byte
	  +------------------+----------+--------+---------------+
component | pre_entry_length | encoding | length | content       |
	  |                  |          |        |               |
value     | ?                |    00    | 001011 | hello world   |
	  +------------------+----------+--------+---------------+

encoding 域的值 00 表示节点保存着一个长度小于等于 63 字节的字符数组
length 域给出了这个字符数组的准确长度 11 字节（的二进制 001011）
content 则保存着字符数组值 hello world 本身（为了方便表示， content 部分使用字符而不是二进制表示）

以下是另一个节点，它保存着整数 10086 ：

area      |<---------------------- entry ----------------------->|

size        ?                  2 bit      6 bit    2 bytes
	  +------------------+----------+--------+---------------+
component | pre_entry_length | encoding | length | content       |
	  |                  |          |        |               |
value     | ?                |    11    | 000000 | 10086         |
	  +------------------+----------+--------+---------------+

encoding 域的值 11 表示节点保存的是一个整数
而 length 域的值 000000 表示这个节点的值的类型为 int16_t
最后， content 保存着整数值 10086 本身（为了方便表示， content 部分用十进制而不是二进制表示）

创建

函数 ziplistNew 用于创建一个新的空白 ziplist ，这个 ziplist 可以表示为下图：

area        |<---- ziplist header ---->|<-- end -->|

size          4 bytes   4 bytes 2 bytes  1 byte
	    +---------+--------+-------+-----------+
component   | zlbytes | zltail | zllen | zlend     |
	    |         |        |       |           |
value       |  1011   |  1010  |   0   | 1111 1111 |
	    +---------+--------+-------+-----------+
				       ^
				       |
			       ZIPLIST_ENTRY_HEAD
				       &
address                        ZIPLIST_ENTRY_TAIL
				       &
			       ZIPLIST_ENTRY_END

空白 ziplist 的表头、表尾和末端处于同一地址。创建了 ziplist 之后，就可以往里面添加新节点了，根据新节点添加位置的不同，这个工作可以分为两类来进行：

将节点添加到 ziplist 末端：在这种情况下，新节点的后面没有任何节点
将节点添加到某个/某些节点的前面：在这种情况下，新节点的后面有至少一个节点

以下分别讨论这两种情况

添加

将节点添加到末端

将新节点添加到 ziplist 的末端需要执行以下步骤：

记录到达 ziplist 末端所需的偏移量（因为之后的内存重分配可能会改变 ziplist 的地址，因此记录偏移量而不是保存指针）
根据新节点要保存的值，计算出编码这个值所需的空间大小，以及编码它前一个节点的长度所需的空间大小，然后对 ziplist 进行内存重分配
设置新节点的各项属性： pre_entry_length 、 encoding 、 length 和 content
更新 ziplist 的各项属性，比如记录空间占用的 zlbytes ，到达表尾节点的偏移量 zltail ，以及记录节点数量的 zllen 。

举个例子，假设现在要将一个新节点添加到只含有一个节点的 ziplist 上，程序首先要执行步骤 1 ，定位 ziplist 的末端：

area        |<---- ziplist header ---->|<--- entries -->|<-- end -->|

size          4 bytes  4 bytes  2 bytes  5 bytes          1 bytes
	    +---------+--------+-------+----------------+-----------+
component   | zlbytes | zltail | zllen | entry 1        | zlend     |
	    |         |        |       |                |           |
value       |  10000  |  1010  |   1   | ?              | 1111 1111 |
	    +---------+--------+-------+----------------+-----------+
				       ^                ^
				       |                |
address                         ZIPLIST_ENTRY_HEAD   ZIPLIST_ENTRY_END
				       &
				ZIPLIST_ENTRY_TAIL

然后执行步骤 2 ，程序需要计算新节点所需的空间。假设要添加到节点里的值为字符数组 hello world

那么保存这个值共需要 12 字节的空间：
- 11 字节用于保存字符数组本身；
- 另外 1 字节中的 2 bit 用于保存类型编码 00 (encoding)，而其余 6 bit 则保存字符数组长度 11 的二进制 001011 (length)
还需要 1 字节，用于保存前一个节点的长度 5 （二进制 101）

合算起来，为了添加新节点， ziplist 总共需要多分配 13 字节空间。以下是分配完成之后， ziplist 的样子：

area        |<---- ziplist header ---->|<------------ entries ------------>|<-- end -->|

size          4 bytes  4 bytes  2 bytes  5 bytes          13 bytes           1 bytes
	    +---------+--------+-------+----------------+------------------+-----------+
component   | zlbytes | zltail | zllen | entry 1        | entry 2          | zlend     |
	    |         |        |       |                |                  |           |
value       |  10000  |  1010  |   1   | ?              | pre_entry_length | 1111 1111 |
	    |         |        |       |                | ?                |           |
	    |         |        |       |                |                  |           |
	    |         |        |       |                | encoding         |           |
	    |         |        |       |                | ?                |           |
	    |         |        |       |                |                  |           |
	    |         |        |       |                | length           |           |
	    |         |        |       |                | ?                |           |
	    |         |        |       |                |                  |           |
	    |         |        |       |                | content          |           |
	    |         |        |       |                | ?                |           |
	    |         |        |       |                |                  |           |
	    +---------+--------+-------+----------------+------------------+-----------+
				       ^                ^
				       |                |
address                       ZIPLIST_ENTRY_HEAD   ZIPLIST_ENTRY_END
				       &
			      ZIPLIST_ENTRY_TAIL

步骤三，更新新节点的各项属性（为了方便表示， content 的内容使用字符而不是二进制来表示）：

area        |<---- ziplist header ---->|<------------ entries ------------>|<-- end -->|

size          4 bytes  4 bytes  2 bytes  5 bytes          13 bytes           1 bytes
	    +---------+--------+-------+----------------+------------------+-----------+
component   | zlbytes | zltail | zllen | entry 1        | entry 2          | zlend     |
	    |         |        |       |                |                  |           |
value       |  10000  |  1010  |   1   | ?              | pre_entry_length | 1111 1111 |
	    |         |        |       |                | 101              |           |
	    |         |        |       |                |                  |           |
	    |         |        |       |                | encoding         |           |
	    |         |        |       |                | 00               |           |
	    |         |        |       |                |                  |           |
	    |         |        |       |                | length           |           |
	    |         |        |       |                | 001011           |           |
	    |         |        |       |                |                  |           |
	    |         |        |       |                | content          |           |
	    |         |        |       |                | hello world      |           |
	    |         |        |       |                |                  |           |
	    +---------+--------+-------+----------------+------------------+-----------+
				       ^                ^
				       |                |
address                       ZIPLIST_ENTRY_HEAD   ZIPLIST_ENTRY_END
				       &
			      ZIPLIST_ENTRY_TAIL

最后一步，更新 ziplist 的 zlbytes 、 zltail 和 zllen 属性：

area        |<---- ziplist header ---->|<------------ entries ------------>|<-- end -->|

size          4 bytes  4 bytes  2 bytes  5 bytes          13 bytes           1 bytes
	    +---------+--------+-------+----------------+------------------+-----------+
component   | zlbytes | zltail | zllen | entry 1        | entry 2          | zlend     |
	    |         |        |       |                |                  |           |
value       |  11101  |  1111  |  10   | ?              | pre_entry_length | 1111 1111 |
	    |         |        |       |                | 101              |           |
	    |         |        |       |                |                  |           |
	    |         |        |       |                | encoding         |           |
	    |         |        |       |                | 00               |           |
	    |         |        |       |                |                  |           |
	    |         |        |       |                | length           |           |
	    |         |        |       |                | 001011           |           |
	    |         |        |       |                |                  |           |
	    |         |        |       |                | content          |           |
	    |         |        |       |                | hello world      |           |
	    |         |        |       |                |                  |           |
	    +---------+--------+-------+----------------+------------------+-----------+
				       ^                ^                  ^
				       |                |                  |
address                                |          ZIPLIST_ENTRY_TAIL   ZIPLIST_ENTRY_END
				       |
			       ZIPLIST_ENTRY_HEAD

到这一步，添加新节点到表尾的工作正式完成

这里没有演示往空 ziplist 添加第一个节点的过程， 因为这个过程和上面演示的添加第二个节点的过程类似

而且因为第一个节点的存在， 添加第二个节点的过程可以更好地展示“将节点添加到表尾”这一操作的一般性

将节点添加到某个/某些节点的前面

比起将新节点添加到 ziplist 的末端，将一个新节点添加到某个/某些节点的前面要复杂得多，因为这种操作除了将新节点添加到 ziplist 以外，还可能引起后续一系列节点的改变。举个例子，假设要将一个新节点 new 添加到节点 prev 和 next 之间：

   add new entry here
	   |
	   V
+----------+----------+----------+----------+----------+
|          |          |          |          |          |
|   prev   |   next   | next + 1 | next + 2 |   ...    |
|          |          |          |          |          |

程序首先为新节点扩大 ziplist 的空间：

+----------+----------+----------+----------+----------+----------+
|          |          |          |          |          |          |
|   prev   |   ???    |   next   | next + 1 | next + 2 |   ...    |
|          |          |          |          |          |          |
+----------+----------+----------+----------+----------+----------+

	   |<-------->|
	      expand
	      space

然后设置 new 节点的各项值（到目前为止，一切都和前面介绍的添加操作一样）

	     set value,
	     property,
	     length,
	     etc.
		|
		v
+----------+----------+----------+----------+----------+----------+
|          |          |          |          |          |          |
|   prev   |   new    |   next   | next + 1 | next + 2 |   ...    |
|          |          |          |          |          |          |
+----------+----------+----------+----------+----------+----------+

现在，新的 new 节点取代原来的 prev 节点，成为了 next 节点的新前驱节点，不过，因为这时 next 节点的 pre_entry_length 域编码的仍然是 prev 节点的长度，所以程序需要将 new 节点的长度编码进 next 节点的 pre_entry_length 域里，这里会出现三种可能：

next 的 pre_entry_length 域的长度正好能够编码 new 的长度（都是 1 字节或者都是 5 字节）：程序直接更新 next 的 pre_entry_length 域

next 的 pre_entry_length 只有 1 字节长，但编码 new 的长度需要 5 字节：

如果是第二种情况， 那么程序必须对 ziplist 进行内存重分配， 从而扩展 next 的空间

然而，因为 next 的空间长度改变了， 所以程序又必须检查 next 的后继节点 next+1

看它的 pre_entry_length 能否编码 next 的新长度， 如果不能的话，程序又需要继续对 next+1 进行扩容。。。

next 的 pre_entry_length 有 5 字节长，但编码 new 的长度只需要 1 字节：程序直接更新 next 的 pre_entry_length 域

在某个/某些节点的前面添加新节点之后，程序必须沿着路径挨个检查后续的节点，是否满足新长度的编码要求，直到遇到一个能满足要求的节点（如果有一个能满足，则这个节点之后的其他节点也满足），或者到达 ziplist 的末端 zlend 为止，这种检查操作的复杂度为 \(\theta(N^{2})\)

不过，因为只有在新添加节点的后面有连续多个长度接近 254 的节点时， 这种连锁更新才会发生

所以可以普遍地认为， 这种连锁更新发生的概率非常小， 在一般情况下， 将添加操作看成是 O(N) 复杂度也是可以的

执行完这三种情况的其中一种后，程序更新 ziplist 的各项属性，至此，添加操作完成

在第三种情况中，程序实际上是可以执行类似于情况二的动作的： 它可以挨个地检查新节点之后的节点， 尝试收缩它们的空间长度

不过 Redis 决定不这么做， 因为在一些情况下，比如前面提到的，有连续多个长度接近 254 的节点时

可能会出现重复的扩展，收缩再扩展，再收缩的抖动效果， 这会让操作的性能变得非常差

删除

删除节点和添加操作的步骤类似：

定位目标节点，并计算节点的空间长度 target - size：

   target start here
	   |
	   V
+----------+----------+----------+----------+----------+----------+
|          |          |          |          |          |          |
|   prev   |  target  |   next   | next + 1 | next + 2 |   ...    |
|          |          |          |          |          |          |
+----------+----------+----------+----------+----------+----------+

	   |<-------->|
	    target-size

进行内存移位，覆盖 target 原本的数据，然后通过内存重分配，收缩多余空间：

   target start here
	   |
	   V
+----------+----------+----------+----------+----------+
|          |          |          |          |          |
|   prev   |   next   | next + 1 | next + 2 |   ...    |
|          |          |          |          |          |
+----------+----------+----------+----------+----------+

	   | <------------------------------------------ memmove

检查 next 、 next+1 等后续节点能否满足新前驱节点的编码
```
和添加操作一样，删除操作也可能会引起连锁更新
```

遍历

可以对 ziplist 进行从前向后的遍历，或者从后先前的遍历

当进行从前向后的遍历时，程序从指向节点 e1 的指针 p 开始，计算节点 e1 的长度 e1 - size ，然后将 p 加上 e1 - size ，就将指针后移到了下一个节点 e2 。。。如此反覆，直到 p 遇到 ZIPLIST_ENTRY_END 为止，这样整个 ziplist 就遍历完了：

			       p + e1-size + e2-size
		 p + e1-size     |
	   p          |          |
	   |          |          |
	   V          V          V
+----------+----------+----------+----------+----------+----------+----------+
| ZIPLIST  |          |          |          |          |          | ZIPLIST  |
| ENTRY    |    e1    |    e2    |    e3    |    e4    |   ...    | ENTRY    |
| HEAD     |          |          |          |          |          | END      |
+----------+----------+----------+----------+----------+----------+----------+

	   |<-------->|<-------->|
	     e1-size    e2-size

当进行从后往前遍历的时候，程序从指向节点 eN 的指针 p 出发，取出 eN 的 pre_entry_length 值，然后用 p - pre_entry_length ，这就将指针移动到了前一个节点 eN-1 。。。如此反覆，直到 p 遇到 ZIPLIST_ENTRY_HEAD 为止，这样整个 ziplist 就遍历完了：

					 p - eN.pre_entry_length
					    |
					    |          p
					    |          |
					    V          V
+----------+----------+----------+----------+----------+----------+----------+
| ZIPLIST  |          |          |          |          |          | ZIPLIST  |
| ENTRY    |    e1    |    e2    |   ...    |   eN-1   |    eN    | ENTRY    |
| HEAD     |          |          |          |          |          | END      |

查找

查找元素、根据值定位节点，这两个操作和遍历的原理基本相同，不再赘述

总结

ziplist 是由一系列特殊编码的内存块构成的列表，可以保存字符数组或整数值，同时是哈希键、列表键和有序集合键的底层实现之一

ziplist 典型分布结构如下：

area        |<---- ziplist header ---->|<----------- entries ------------->|<-end->|

size          4 bytes  4 bytes  2 bytes    ?        ?        ?        ?     1 byte
	    +---------+--------+-------+--------+--------+--------+--------+-------+
component   | zlbytes | zltail | zllen | entry1 | entry2 |  ...   | entryN | zlend |
	    +---------+--------+-------+--------+--------+--------+--------+-------+
				       ^                          ^        ^
address                                |                          |        |
				ZIPLIST_ENTRY_HEAD                |   ZIPLIST_ENTRY_END
								  |
							 ZIPLIST_ENTRY_TAIL

ziplist 节点的分布结构如下：

area        |<------------------- entry -------------------->|

	    +------------------+----------+--------+---------+
component   | pre_entry_length | encoding | length | content |
	    +------------------+----------+--------+---------+

添加和删除 ziplist 节点有可能会引起连锁更新，因此，添加和删除操作的最坏复杂度为 \(\theta(N^2)\)
```
不过，因为连锁更新的出现概率并不高，所以一般可以将添加和删除操作的复杂度视为 O(N) 
```
Previous：整数集合 Home：内存映射数据结构