本文參考 嗨客網 Redis面試題
Redis壓縮清單
Redis 中的壓縮清單不是基礎資料結構，而是 Redis 自己設計的一種資料存儲結構。它有點兒類似數組，通過一片連續的記憶體空間，來存儲資料。不過，它跟數組不同的一點是，它允許存儲的資料大小不同。
壓縮清單詳解
說明
聽到 “壓縮” 兩個字，直覺的反應就是節省記憶體。之是以說這種存儲結構節省記憶體，是相較于數組的存儲思路而言的。我們知道，數組要求每個元素的大小相同，如果我們要存儲不同長度的字元串，那我們就需要用最大長度的字元串大小作為元素的大小(假設是 20 個位元組)。存儲小于 20 個位元組長度的字元串的時候，便會浪費部分存儲空間。
數組的優勢占用一片連續的空間可以很好的利用 CPU 緩存通路資料。如果我們想要保留這種優勢，又想節省存儲空間我們可以對數組進行壓縮。
但是這樣有一個問題，我們在周遊它的時候由于不知道每個元素的大小是多少，是以也就無法計算出下一個節點的具體位置。這個時候我們可以給每個節點增加一個 length 的屬性。
那麼，此時數組就如下圖所示：
如此。我們在周遊節點的之後就知道每個節點的長度(占用記憶體的大小)，就可以很容易計算出下一個節點再記憶體中的位置。這種結構就像一個簡單的壓縮清單了。
壓縮清單的構成
壓縮清單是 Redis 為了節約記憶體而開發的，是由一系列特殊編碼的連續記憶體塊組成的順序型(sequential)資料結枃。一個壓縮清單可以包含任意多個節點(entry)，每個節點可以儲存一個位元組數組或者一個整數值，如下圖：
zlbytes：存儲一個無符号整數，固定四個位元組長度，用于存儲壓縮清單所占用的位元組，當重新配置設定記憶體的時候使用，不需要周遊整個清單來計算記憶體大小。
zltail：存儲一個無符号整數，固定四個位元組長度，代表指向清單尾部的偏移量，偏移量是指壓縮清單的起始位置到指定清單節點的起始位置的距離。
zllen：壓縮清單包含的節點個數，固定兩個位元組長度，源碼中指出當節點個數大于 2^16-2 個數的時候，該值将無效，此時需要周遊清單來計算清單節點的個數。
entryX：清單節點區域，長度不定，由清單節點緊挨着組成。
zlend：一位元組長度固定值為 255，用于表示清單結束。
示例
如上圖，展示了一個總長為 80 位元組，包含 3 個節點的壓縮清單。如果我們有一個指向壓縮清單起始位址的指針 p，那麼表為節點的位址就是 P+60。
壓縮清單節點構成
壓縮清單的節點如下圖所示：
previous_entry_length：previous_entry_length 記錄了前一個節點的長度，程式可以通過指針運算，根據目前節點的起始位址拉算出前一個節點的其實位址。
壓縮清單從表尾向表頭的周遊就是使用這一原理實作的。
**encoding：**encoding 記錄了節點的 content 屬性所儲存的資料類型及長度。
**content：**content 負責儲存節點的值，節點值可以是一個位元組數組或者整數，值的類型和長度由 encoding 屬性決定。
連鎖更新
每個節點的 previous_entry_length 屬性都記錄了前一個節點的長度：
- 如果前一節點的長度小于 254 位元組，那麼 previous_entry_length 屬性需要用 1 位元組長的空間來儲存這個長度值。
- 如果前一節點的長度大于等于 254 位元組，那麼 previous_entry_length 屬性需要用 5 位元組長的空間來儲存這個長度值。
假設在一個壓縮清單中，有多個連續的、長度介于 250 到 253 位元組之間的節點 e1 至 eN：
因為 e1 至 eN 所有節點長度都小于 254 位元組，是以這些節點長度的 previous_entry_length 都是 1 位元組的。這時，如果在壓縮清單頭添加一個長度大于等于 254 位元組的新節點：
因為 e1 的 previous_entry_length 屬性僅長 1 位元組，無法儲存新節點的程度，是以程式将對壓縮清單進行空間重配置設定，并将 e1 的 previous_entry_length 從原來的 1 位元組長擴充為 5 位元組長。
這時 e1 的 previous_entry_length 屬性新增了四個位元組，e1 的長度大于等于 254 位元組了，這樣用 1 位元組長的 previous_entry_length 就無法儲存。
是以，e2 的 previous_entry_length 屬性也會被擴充。依次類推，後面所有節點都會被擴充，造成連鎖更新。
類似地，删除節點操作也可能會引發連鎖更新：
因為連鎖更新最壞情況下需要對壓縮清單執行 N 次空間重配置設定，而每次空間重配置設定複雜度最壞為 O(N)，是以連鎖更新最壞複雜度為 O(N^2)
盡管連鎖更新複雜度較高，但真正造成性能問題的幾率很低：
- 壓縮清單裡恰好有多個連續的、長度介于 250 到 253 位元組之間的節點。
- 即便出現連鎖更新，隻要被更新節點數目不多，影響就不大。
是以添加删除節點的操作平均複雜度僅為 O(N)。
Redis壓縮清單
壓縮清單(zip1ist)是清單和哈希的底層實作之一。
當一個清單隻包含少量清單項，并且每個清單項要麼就是小整數值，要麼就是長度比較短的字元串，那麼 Redis 就會使用壓縮清單來做清單的底層實作。
當一個哈希隻包含少量鍵值對，比且每個鍵值對的鍵和值要麼就是小整數值，要麼就是長度比較短的字元串，那麼 Redis 就會使用壓縮清單來做哈希的底層實作。
常用操作的時間複雜度
| 操作 | 時間複雜度 |
|---|---|
| 建立一個新的壓縮清單 | O(1) |
| 建立一個包含給定值的新節點,并将這個新節點添加到壓縮清單的表頭或者表尾 | 平均 O(N)，最壞O(N^2)(可能發生連鎖更新) |
| 将包含給定值的新節點插人到給定節點之後 | 平均 O(N)，最壞O(N^2)(可能發生連鎖更新) |
| 傳回壓縮清單給定索引上的節點 | O(N) |
| 在壓縮清單中査找并傳回包含了給定值的節點 | 因為節點的值可能是一個位元組數組,是以檢查節點值和給定值是否相同的複雜度為 O(N),而查找整個清單的複雜度則為(N^2) |
| 傳回給定節點的下一個節點 | O(1) |
| 傳回給定節點的前一個節點 | O(1) |
| 擷取給定節點所儲存的值 | O(1) |
| 從壓縮清單中删除給定的節點 | 平均 O(N)，最壞 O(N^2)(可能發生連鎖更新) |
| 删除壓縮清單在給定索引上的連續多個 | 平均 O(N)，最壞 O(N^2)(可能發生連鎖更新) |
| 傳回壓縮清單目前占用的記憶體位元組數 | O(1) |
| 傳回壓縮清單目前包含的節點數量 | 點數量小于 65535 時為 O(1),大于 65535 時為 O(N) |
總結
- 壓縮清單是 Redis 為節約記憶體自己設計的一種順序型資料結構。
- 壓縮清單被用作清單鍵和哈希鍵的底層實作之一。
- 壓縮清單可以包含多個節點，每個節點可以儲存一個位元組數組或者整數值。
- 添加新節點到壓縮清單，或者從壓縮清單中删除節點，可能會引發連鎖更新操作，但這種操作出現的幾率并不高。
更多
原文連結：連結
其他：目錄
更多文章，可以關注下方公衆号：