Redis學習筆記（五） 壓縮列表

壓縮列表是列表鍵與哈希鍵的底層實現之一。當一個列表鍵只包含少量的列表項，並且每個列表項要麼就是小整數值，要麼就是長度較短的字元串，那麼Redis就會使用壓縮列表來做列表鍵的底層實現。

壓縮列表是為了節約記憶體而開發的，是由一系列特殊編碼的連續記憶體塊組成的順序型數據結構。一個壓縮列表可以包含任意多的節點，每個節點可以保存一個位元組數組或一個整數值。

壓縮表可以包含：

1、長度小於等於63位元組的位元組數組

2、長度小於16383位元組的位元組數組

3、長度小於等於4294967295位元組的位元組數組

4、4位長度的無符號整數

5、1位元組長度有符號整數

6、3位元組長的有符號整數

7、int16類型的整數

8、int32類型的整數

9、int64類型的整數

每個壓縮列表節點都由previous_entry_length、encoding、content三部分組成

說明：previous_entry_length 保存前一節點的長度，如果前一個節點長度小於254節點，那麼previous_entry_length屬性需要1位元組長的空間來保存這個長度值；如果超度254則需要5個位元組長的空間來保存這個長度。

連鎖更新

由於是連續的記憶體片段，當在中間插入一個元素時，

e1節點的 previous_entry_length屬性僅長1位元組，當將new節點設置為前置節點時，由於e1的previous_entry_length 長度為1無法保存new節點的長度，所以需要將長度擴展到5個位元組空間，因此需要對列表進行空間重新分配操作。同理，如果引發了對e2、e3.。。。的擴展，這種操作稱為連鎖更新。

連鎖更新在最壞的情況下需要對壓縮列表執行n次空間的重分配操作，每次空間重分配的最壞複雜度為O(N)，所以連鎖更新最壞的的複雜度為O(N²)。

-------- end --------

每天學一點，總會有收穫。

說明：尊重作者知識產權，文中內容參考《Redis設計與實現》，僅在此做學習與大家分享。