壓縮清單

Ziplist 是由一系列特殊編碼的記憶體塊構成的清單，一個 ziplist 可以包含多個節點（entry），每個節點可以儲存一個長度受限的字元數組（不以 \0 結尾的 char 數組）或者整數，包括：

字元數組
- 長度小于等于 63 （）位元組的字元數組
- 長度小于等于 16383 （）位元組的字元數組
- 長度小于等于 4294967295 （）位元組的字元數組
整數
- 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 的值
ZIPLIST_TAIL_OFFSET(ziplist)	取出 zltail 的值
ZIPLIST_LENGTH(ziplist)	取出 zllen 的值
ZIPLIST_HEADER_SIZE	傳回 ziplist header 部分的長度，總是固定的 10 位元組
ZIPLIST_ENTRY_HEAD(ziplist)	傳回到達 ziplist 第一個節點（表頭）的位址
ZIPLIST_ENTRY_TAIL(ziplist)	傳回到達 ziplist 最後一個節點（表尾）的位址
ZIPLIST_ENTRY_END(ziplist)	傳回 ziplist 的末端，也即是 zlend 之前的位址

因為 ziplist header 部分的長度總是固定的（4 位元組 + 4 位元組 + 2 位元組），是以将指針移動到表頭節點的複雜度為常數時間；除此之外，因為表尾節點的位址可以通過 zltail 計算得出，是以将指針移動到表尾節點的複雜度也為常數時間。

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

函數名	作用	算法複雜度
ziplistNew	建立一個新的 ziplist
ziplistResize	重新調整 ziplist 的記憶體大小
ziplistPush	将一個包含給定值的新節點推入 ziplist 的表頭或者表尾
zipEntry	取出給定位址上的節點，并将它的屬性儲存到 zlentry 結構然後傳回
ziplistInsert	将一個包含給定值的新節點插入到給定位址
ziplistDelete	删除給定位址上的節點
ziplistDeleteRange	在給定索引上，連續進行多次删除
ziplistFind	在 ziplist 中查找并傳回包含給定值的節點
ziplistLen	傳回 ziplist 儲存的節點數量
ziplistBlobLen	以位元組為機關，傳回 ziplist 占用的記憶體大小

因為 ziplist 由連續的記憶體塊構成，在最壞情況下，當 ziplistPush 、 ziplistDelete 這類對節點進行增加或删除的函數之後，程式需要執行一種稱為連鎖更新的動作來維持 ziplist 結構本身的性質，是以這些函數的最壞複雜度都為。不過，因為這種最壞情況出現的機率并不高，是以大可以放心使用 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 之後，就可以往裡面添加新節點了，根據新節點添加位置的不同，這個工作可以分為兩類來進行：

将節點添加到 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 ，而其餘 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

到這一步，添加新節點到表尾的工作正式完成。

注解

這裡沒有示範往空 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 隻有 1 位元組長，但編碼 new 的長度需要 5 位元組
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 為止，這種檢查操作的複雜度為。

不過，因為隻有在新添加節點的後面有連續多個長度接近 254 的節點時，這種連鎖更新才會發生，是以可以普遍地認為，這種連鎖更新發生的機率非常小，在一般情況下，将添加操作看成是複雜度也是可以的。

執行完這三種情況的其中一種後，程式更新 ziplist 的各項屬性，至此，添加操作完成。

注解

在第三種情況中，程式實際上是可以執行類似于情況二的動作的：它可以挨個地檢查新節點之後的節點，嘗試收縮它們的空間長度，不過 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 節點有可能會引起連鎖更新，是以，添加和删除操作的最壞複雜度為，不過，因為連鎖更新的出現機率并不高，是以一般可以将添加和删除操作的複雜度視為。

redis 壓縮清單壓縮清單

壓縮清單

ziplist 的構成

節點的構成

pre_entry_length

encoding 和 length

content

建立新 ziplist

将節點添加到末端

将節點添加到某個/某些節點的前面

删除節點

周遊

查找元素、根據值定位節點

小結

繼續閱讀

秒懂JVM的三大參數類型，就靠這十個小實驗了初級—中級—進階三個級别的大廠面試真題阿裡雲——Java 實習生/初級美團——Java 中級螞蟻金服——Java 進階基礎篇JVM 篇MySQL 篇Redis 篇

CentOs7 安裝redis4.0 遇到的坑一、CentOs7連接配接網絡二、make檔案的時候出錯三、安裝ruby的redis插件時候報錯最後

docker 搭建Redis 問題解決

如何解決Redis緩存擊穿、雪崩、穿透問題

java 版本的redis-stat不能運作在背景和daemon

redis管理常用指令

django短信驗證碼的後端實作

Redis訂閱了一段時間後訂閱失效了（ redisTemplate.convertAndSend）

2022秋招面試總結（cpp+java+測開）百度測開一面位元組後端一面蝦皮後端一面蝦皮後端二面

資料遷移方法資料遷移原則資料遷移之雙寫方案資料遷移之級聯同步方案

微服務-性能壓測\緩存redis和分布式鎖redisson和SpringCache

Nacos 2.0 更新前後性能對比壓測

Spring資料和Redis

redis叢集資料一緻性_RedisRaft為Redis叢集帶來強大的資料一緻性

supervisor 管理redis 和httpd 環境centos7

Redis簡介一(單機版)發展曆程Redis