压缩列表 | Redis 设计与实现（第一版）

# 压缩列表 [TOC=2,3] 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 的构成下图展示了一个 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` 的值 | \(\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 的函数： | 函数名 | 作用 | 算法复杂度 | |-----|-----|-----| | `ziplistNew` | 创建一个新的 ziplist | \(\theta(1)\) | | `ziplistResize` | 重新调整 ziplist 的内存大小 | \(O(N)\) | | `ziplistPush` | 将一个包含给定值的新节点推入 ziplist 的表头或者表尾 | \(O(N^2)\) | | `zipEntry` | 取出给定地址上的节点，并将它的属性保存到 `zlentry` 结构然后返回 | \(\theta(1)\) | | `ziplistInsert` | 将一个包含给定值的新节点插入到给定地址 | \(O(N^2)\) | | `ziplistDelete` | 删除给定地址上的节点 | \(O(N^2)\) | | `ziplistDeleteRange` | 在给定索引上，连续进行多次删除 | \(O(N^2)\) | | `ziplistFind` | 在 ziplist 中查找并返回包含给定值的节点 | \(O(N)\) | | `ziplistLen` | 返回 ziplist 保存的节点数量 | \(O(N)\) | | `ziplistBlobLen` | 以字节为单位，返回 ziplist 占用的内存大小 | \(\theta(1)\) | 因为 ziplist 由连续的内存块构成，在最坏情况下，当 `ziplistPush` 、 `ziplistDelete` 这类对节点进行增加或删除的函数之后，程序需要执行一种称为连锁更新的动作来维持 ziplist 结构本身的性质，所以这些函数的最坏复杂度都为 \(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 末端：在这种情况下，新节点的后面没有任何节点。 1. 将节点添加到某个/某些节点的前面：在这种情况下，新节点的后面有至少一个节点。以下两个小节分别讨论这两种情况。 ### 将节点添加到末端将新节点添加到 ziplist 的末端需要执行以下三个步骤： 1. 记录到达 ziplist 末端所需的偏移量（因为之后的内存重分配可能会改变 ziplist 的地址，因此记录偏移量而不是保存指针） 1. 根据新节点要保存的值，计算出编码这个值所需的空间大小，以及编码它前一个节点的长度所需的空间大小，然后对 ziplist 进行内存重分配。 1. 设置新节点的各项属性： `pre_entry_length` 、 `encoding` 、 `length` 和 `content` 。 1. 更新 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 字节） 1. `next` 的 `pre_entry_length` 只有 1 字节长，但编码 `new` 的长度需要 5 字节 1. `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` 为止，这种检查操作的复杂度为 \(O(N^2)\) 。不过，因为只有在新添加节点的后面有连续多个长度接近 254 的节点时，这种连锁更新才会发生，所以可以普遍地认为，这种连锁更新发生的概率非常小，在一般情况下，将添加操作看成是 \(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 节点有可能会引起连锁更新，因此，添加和删除操作的最坏复杂度为 \(O(N^2)\) ，不过，因为连锁更新的出现概率并不高，所以一般可以将添加和删除操作的复杂度视为 \(O(N)\) 。