.. _ziplist_chapter: 压缩列表 ======================== Ziplist 是由一系列特殊编码的内存块构成的列表， 一个 ziplist 可以包含多个节点（entry）， 每个节点可以保存一个长度受限的字符数组（不以 ``\0`` 结尾的 ``char`` 数组）或者整数， 包括： - 字符数组 - 长度小于等于 ``63`` （\ :math:`2^{6}-1`\ ）字节的字符数组 - 长度小于等于 ``16383`` （\ :math:`2^{14}-1`\ ） 字节的字符数组 - 长度小于等于 ``4294967295`` （\ :math:`2^{32}-1`\ ）字节的字符数组 - 整数 - ``4`` 位长，介于 ``0`` 至 ``12`` 之间的无符号整数 - ``1`` 字节长，有符号整数 - ``3`` 字节长，有符号整数 - ``int16_t`` 类型整数 - ``int32_t`` 类型整数 - ``int64_t`` 类型整数 因为 ziplist 节约内存的性质， 哈希键、列表键和有序集合键初始化的底层实现皆采用 ziplist， 更多信息请参考《\ :ref:`hash_chapter`\ 》、《\ :ref:`list_chapter`\ 》和《\ :ref:`sorted_set_chapter`\ 》章节。 本章先介绍 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 图中各个域的作用如下： +-------------+----------------+-----------------------------------------------------------------------------------------+ | 域 | 长度/类型 | 域的值 | +=============+================+=========================================================================================+ | ``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 模块定义了以下宏： ================================== ================================================================================== ================= 宏 作用 算法复杂度 ================================== ================================================================================== ================= ``ZIPLIST_BYTES(ziplist)`` 取出 ``zlbytes`` 的值 :math:`\theta(1)` ``ZIPLIST_TAIL_OFFSET(ziplist)`` 取出 ``zltail`` 的值 :math:`\theta(1)` ``ZIPLIST_LENGTH(ziplist)`` 取出 ``zllen`` 的值 :math:`\theta(1)` ``ZIPLIST_HEADER_SIZE`` 返回 ziplist header 部分的长度，总是固定的 ``10`` 字节 :math:`\theta(1)` ``ZIPLIST_ENTRY_HEAD(ziplist)`` 返回到达 ziplist 第一个节点（表头）的地址 :math:`\theta(1)` ``ZIPLIST_ENTRY_TAIL(ziplist)`` 返回到达 ziplist 最后一个节点（表尾）的地址 :math:`\theta(1)` ``ZIPLIST_ENTRY_END(ziplist)`` 返回 ziplist 的末端，也即是 ``zlend`` 之前的地址 :math:`\theta(1)` ================================== ================================================================================== ================= 因为 ziplist header 部分的长度总是固定的（\ ``4`` 字节 + ``4`` 字节 + ``2`` 字节）， 因此将指针移动到表头节点的复杂度为常数时间； 除此之外， 因为表尾节点的地址可以通过 ``zltail`` 计算得出， 因此将指针移动到表尾节点的复杂度也为常数时间。 以下是用于操作 ziplist 的函数： ======================== ============================================================================ ===================== 函数名 作用 算法复杂度 ======================== ============================================================================ ===================== ``ziplistNew`` 创建一个新的 ziplist :math:`\theta(1)` ``ziplistResize`` 重新调整 ziplist 的内存大小 :math:`O(N)` ``ziplistPush`` 将一个包含给定值的新节点推入 ziplist 的表头或者表尾 :math:`O(N^2)` ``zipEntry`` 取出给定地址上的节点，并将它的属性保存到 ``zlentry`` 结构然后返回 :math:`\theta(1)` ``ziplistInsert`` 将一个包含给定值的新节点插入到给定地址 :math:`O(N^2)` ``ziplistDelete`` 删除给定地址上的节点 :math:`O(N^2)` ``ziplistDeleteRange`` 在给定索引上，连续进行多次删除 :math:`O(N^2)` ``ziplistFind`` 在 ziplist 中查找并返回包含给定值的节点 :math:`O(N)` ``ziplistLen`` 返回 ziplist 保存的节点数量 :math:`O(N)` ``ziplistBlobLen`` 以字节为单位，返回 ziplist 占用的内存大小 :math:`\theta(1)` ======================== ============================================================================ ===================== 因为 ziplist 由连续的内存块构成， 在最坏情况下， 当 ``ziplistPush`` 、 ``ziplistDelete`` 这类对节点进行增加或删除的函数之后， 程序需要执行一种称为连锁更新的动作来维持 ziplist 结构本身的性质， 所以这些函数的最坏复杂度都为 :math:`O(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`` 开头的字符数组的编码方式如下： ================================================ =========== ============================================================ 编码 编码长度 content 部分保存的值 ================================================ =========== ============================================================ ``00bbbbbb`` 1 byte 长度小于等于 63 字节的字符数组。 ``01bbbbbb xxxxxxxx`` 2 byte 长度小于等于 16383 字节的字符数组。 ``10____ aaaaaaaa bbbbbbbb cccccccc dddddddd`` 5 byte 长度小于等于 4294967295 的字符数组。 ================================================ =========== ============================================================ 表格中的下划线 ``_`` 表示留空，而变量 ``b`` 、 ``x`` 等则代表实际的二进制数据。为了方便阅读，多个字节之间用空格隔开。 ``11`` 开头的整数编码如下： ==================== ============== ============================================================ 编码 编码长度 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`` 部分用十进制而不是二进制表示）。 创建新 ziplist -------------------- 函数 ``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 之后， 就可以往里面添加新节点了， 根据新节点添加位置的不同， 这个工作可以分为两类来进行： 1. 将节点添加到 ziplist 末端：在这种情况下，新节点的后面没有任何节点。 2. 将节点添加到某个/某些节点的前面：在这种情况下，新节点的后面有至少一个节点。 以下两个小节分别讨论这两种情况。 将节点添加到末端 ------------------------------ 将新节点添加到 ziplist 的末端需要执行以下三个步骤： 1. 记录到达 ziplist 末端所需的偏移量（因为之后的内存重分配可能会改变 ziplist 的地址，因此记录偏移量而不是保存指针） 2. 根据新节点要保存的值，计算出编码这个值所需的空间大小，以及编码它前一个节点的长度所需的空间大小，然后对 ziplist 进行内存重分配。 3. 设置新节点的各项属性： ``pre_entry_length`` 、 ``encoding`` 、 ``length`` 和 ``content`` 。 4. 更新 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`` ， 而其余 6 bit 则保存字符数组长度 ``11`` 的二进制 ``001011`` 。 另外，节点还需要 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 到这一步，添加新节点到表尾的工作正式完成。 .. note:: 这里没有演示往空 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`` 域里， 这里会出现三种可能： 1. ``next`` 的 ``pre_entry_length`` 域的长度正好能够编码 ``new`` 的长度（都是 1 字节或者都是 5 字节） 2. ``next`` 的 ``pre_entry_length`` 只有 1 字节长，但编码 ``new`` 的长度需要 5 字节 3. ``next`` 的 ``pre_entry_length`` 有 5 字节长，但编码 ``new`` 的长度只需要 1 字节 对于情况 1 和 3 ， 程序直接更新 ``next`` 的 ``pre_entry_length`` 域。 如果是第二种情况， 那么程序必须对 ziplist 进行内存重分配， 从而扩展 ``next`` 的空间。 然而，因为 ``next`` 的空间长度改变了， 所以程序又必须检查 ``next`` 的后继节点 —— ``next+1`` ， 看它的 ``pre_entry_length`` 能否编码 ``next`` 的新长度， 如果不能的话，程序又需要继续对 ``next+1`` 进行扩容。。。 这就是说， 在某个/某些节点的前面添加新节点之后， 程序必须沿着路径挨个检查后续的节点，是否满足新长度的编码要求， 直到遇到一个能满足要求的节点（如果有一个能满足，则这个节点之后的其他节点也满足）， 或者到达 ziplist 的末端 ``zlend`` 为止， 这种检查操作的复杂度为 :math:`O(N^2)` 。 不过，因为只有在新添加节点的后面有连续多个长度接近 254 的节点时， 这种连锁更新才会发生， 所以可以普遍地认为， 这种连锁更新发生的概率非常小， 在一般情况下， 将添加操作看成是 :math:`O(N)` 复杂度也是可以的。 执行完这三种情况的其中一种后， 程序更新 ziplist 的各项属性， 至此，添加操作完成。 .. note:: 在第三种情况中，程序实际上是可以执行类似于情况二的动作的： 它可以挨个地检查新节点之后的节点， 尝试收缩它们的空间长度， 不过 Redis 决定不这么做， 因为在一些情况下，比如前面提到的，有连续多个长度接近 254 的节点时， 可能会出现重复的扩展——收缩——再扩展——再收缩的抖动（flapping）效果， 这会让操作的性能变得非常差。 删除节点 ------------- 删除节点和添加操作的步骤类似。 1\) 定位目标节点，并计算节点的空间长度 ``target-size`` ： :: target start here | V +----------+----------+----------+----------+----------+----------+ | | | | | | | | prev | target | next | next + 1 | next + 2 | ... | | | | | | | | +----------+----------+----------+----------+----------+----------+ |<-------->| target-size 2\) 进行内存移位，覆盖 ``target`` 原本的数据，然后通过内存重分配，收缩多余空间： :: target start here | V +----------+----------+----------+----------+----------+ | | | | | | | prev | next | next + 1 | next + 2 | ... | | | | | | | +----------+----------+----------+----------+----------+ | <------------------------------------------ memmove 3\) 检查 ``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 节点有可能会引起连锁更新，因此，添加和删除操作的最坏复杂度为 :math:`O(N^2)` ，不过，因为连锁更新的出现概率并不高，所以一般可以将添加和删除操作的复杂度视为 :math:`O(N)` 。