壓縮列表 · 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)\) 。