壓縮列表是列表鍵和哈希鍵的底層實現之一。當一個列表鍵只包含少量列表項，并且每個列表項要么就是小整數，要么就是長度比較短的字符串，redis就會使用壓縮列表來做列表鍵的底層實現

當一個哈希鍵只包含少量鍵值對，并且每個鍵值對的鍵和值要么就是小整數值，要么就是長度比較短的字符串，那么Redis就會使用壓縮列表來做哈希鍵的底層實現。

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

ziplist 數據結構：壓縮列表各個組成部分

壓縮列表各個組成部分詳細說明：

壓縮列表節點的構成：

每個壓縮列表節點可以保存一個字節數組或者一個整數值，其中字節數組可以是以下三種長度的其中一種

長度小于等于63字節的字節數組

長度小于等于16383字節的字節數組

長度小于等于4294967295字節的字節數組

數值則可以是以下六種長度的其中一種：

• 1: ?4位長介于0至12之間的無符號整數
• 2：1字節長的有符號整數
• 3: 3字節長的有符號整數
• 4：int16類型整數
• 5：int32類型整數
• 6 : int64類型整數

壓縮列表的數據結構：

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

創建一個空的ziplist：

/*
?* 新創建一個空 ziplist
?*?
?* 復雜度：O(1)
?*
?* 返回值：新創建的 ziplist
?*/
unsigned char *ziplistNew(void) {
? ? // 分配 2 個 32 bit，一個 16 bit，以及一個 8 bit
? ? // 分別用于  和 
? ? unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
? ? unsigned char *zl = zmalloc(bytes);

? ? // 設置長度
? ? ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);

? ? // 設置表尾偏移量
? ? ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);

? ? // 設置列表項數量
? ? ZIPLIST_LENGTH(zl) = 0;

? ? // 設置表尾標識
? ? zl[bytes-1] = ZIP_END;

? ? return zl;
}

壓縮列表包含任意多個壓縮列表節點，每個節點可以保存一個字節數組或者一個整數值。

壓縮列表組成部分：

• zlbytes：記錄整個壓縮列表占用的內存字節數
• zltail：記錄壓縮列表表尾節點距離壓縮列表的起始地址的字節數
• entryX：列表節點
• zlend：用于標記壓縮列表的末端

壓縮列表節點的構成：

• preivous_entry_length：記錄壓縮列表中前一個節點的長度
• encoding：記錄節點content屬性保存數據的類型以及長度
• content：負責保存節點的值，值的類型和長度由節點的encoding屬性決定。

當我們知道一個指向某個節點起始地址的指針，那么通過這個指針以及這個節點的preivous_entry_length屬性，我們可以一直向前一個節點回溯，最終到達壓縮列表的表頭節點。

連鎖更新：

每個節點的preivous_entry_length屬性記錄前一個節點的長度

如果前一個節點長度小于254字節，preivous_entry_length屬性需要用1字節長的空間來保存這個長度值

如果前一個節點長度大于等于254字節，preivous_entry_length屬性需要用5字節長的空間來保存這個長度值

如果前一個節點長度變大，這個節點的preivous_entry_length就要擴展，這個節點的擴展引起下一個節點的擴展，這就是連鎖更新

redis將這種在特殊情況下產生的連續多次空間擴展操作稱之為連鎖更新

在添加新節點和刪除節點都可能引發連鎖更新。

連鎖更新最壞情況下需要對壓縮列表進行N次空間重分配操作，每次空間重分配的最壞復雜度為O(N)，所以連鎖更新的最壞復雜度為O(N的平方)，平均復雜度為O(N)

總結：

壓縮列表是為了節約內存而開發的順序型數據結構，它是列表鍵和哈希鍵的底層實現之一，壓縮列表可以包含多個節點，每個節點可以保存一個字節數組或整數值，添加新節點或刪除節點可能引發連鎖更新操作，這種操作出現幾率不高。