壓縮清單ziplist
- 1、壓縮清單的構成
- 2、壓縮清單節點的構成
-
- 2.1 previous_entry_length
- 2.2 encoding
- 2.3 content
- 3、連鎖更新
壓縮清單（ziplist）是清單鍵和哈希鍵的底層實作之一。
當一個 清單鍵隻包含少量清單項，并且每個清單項要麼就是 最小值，要麼就是長度比較短的字元串，那麼Redis就會使用壓縮清單來做清單鍵的底層實作
當一個 哈希鍵隻包含少量鍵值對，并且每個鍵值對的鍵和值要麼就是 小整數值，要麼就是長度比較短的字元串，那麼Redis就會使用壓縮清單來做哈希鍵的底層實作。
1、壓縮清單的構成
壓縮清單是Redis為了節約記憶體而開發的，是由一系列特殊編碼的連續記憶體塊組成的順序型（sequential）資料結構。
一個壓縮清單可以包含任意多個節點（entry），每個節點可以儲存一個位元組數組或者一個整數值。元素之間緊挨着存儲，沒有任何備援空隙。
2、壓縮清單節點的構成
2.1 previous_entry_length
因為節點的previous_entry_length屬性記錄了前一個節點的長度，是以程式可以通過指針運算，根據目前節點的起始位址來計算出前一個節點的起始位址。
2.2 encoding
節點的encoding屬性記錄了節點的content屬性所儲存資料的類型以及長度：
2.3 content
3、連鎖更新
在特殊情況下産生的連續多次空間擴充操作稱之為“連續更新”。
因為連鎖更新在最壞情況下需要對壓縮清單執行N次空間重配置設定操作，而每次空間重配置設定的最壞複雜度為O(N)，是以連鎖更新的最壞複雜度為O(N*N)
要注意的是，盡管連鎖更新的複雜度較高，但它真正造成性能問題的幾率是很低的：
首先，壓縮清單裡要恰好有多個連續的，長度介于250位元組至253位元組之間的節點，連鎖更新才有可能被引發，在實際中，這種情況并不多見；
其次，即使出現連鎖更新，但隻要被更新的節點不多，就不會對性能造成任何影響。
因為以上原因，ziplistPush等指令的平均複雜度僅為O(N)，在實際中，我們可以放心地使用這些函數，而不必擔心連鎖更新會影響壓縮清單的性能。
參考：
《Redis設計與實作》第七章 壓縮清單