壓縮列表是列表鍵和哈希鍵的底層實(shí)現(xiàn)之一。當(dāng)一個(gè)列表鍵只包含少量列表項(xiàng)，并且每個(gè)列表項(xiàng)要么就是小整數(shù)，要么就是長度比較短的字符串，redis就會使用壓縮列表來做列表鍵的底層實(shí)現(xiàn)

當(dāng)一個(gè)哈希鍵只包含少量鍵值對，并且每個(gè)鍵值對的鍵和值要么就是小整數(shù)值，要么就是長度比較短的字符串，那么Redis就會使用壓縮列表來做哈希鍵的底層實(shí)現(xiàn)。

壓縮列表是Redis為了節(jié)約內(nèi)存而開發(fā)的是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)，一個(gè)壓縮列表可以包含任意多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值

ziplist 數(shù)據(jù)結(jié)構(gòu)：壓縮列表各個(gè)組成部分

壓縮列表各個(gè)組成部分詳細(xì)說明：

壓縮列表節(jié)點(diǎn)的構(gòu)成：

每個(gè)壓縮列表節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值，其中字節(jié)數(shù)組可以是以下三種長度的其中一種

長度小于等于63字節(jié)的字節(jié)數(shù)組

長度小于等于16383字節(jié)的字節(jié)數(shù)組

長度小于等于4294967295字節(jié)的字節(jié)數(shù)組

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

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

壓縮列表的數(shù)據(jù)結(jié)構(gòu)：

壓縮列表是redis為了節(jié)約內(nèi)存而開發(fā)的，由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)。一個(gè)壓縮列表可以包含任意多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值。

創(chuàng)建一個(gè)空的ziplist：

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

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

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

? ? // 設(shè)置列表項(xiàng)數(shù)量
? ? ZIPLIST_LENGTH(zl) = 0;

? ? // 設(shè)置表尾標(biāo)識
? ? zl[bytes-1] = ZIP_END;

? ? return zl;
}

壓縮列表包含任意多個(gè)壓縮列表節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值。

壓縮列表組成部分：

• zlbytes：記錄整個(gè)壓縮列表占用的內(nèi)存字節(jié)數(shù)
• zltail：記錄壓縮列表表尾節(jié)點(diǎn)距離壓縮列表的起始地址的字節(jié)數(shù)
• entryX：列表節(jié)點(diǎn)
• zlend：用于標(biāo)記壓縮列表的末端

壓縮列表節(jié)點(diǎn)的構(gòu)成：

• preivous_entry_length：記錄壓縮列表中前一個(gè)節(jié)點(diǎn)的長度
• encoding：記錄節(jié)點(diǎn)content屬性保存數(shù)據(jù)的類型以及長度
• content：負(fù)責(zé)保存節(jié)點(diǎn)的值，值的類型和長度由節(jié)點(diǎn)的encoding屬性決定。

當(dāng)我們知道一個(gè)指向某個(gè)節(jié)點(diǎn)起始地址的指針，那么通過這個(gè)指針以及這個(gè)節(jié)點(diǎn)的preivous_entry_length屬性，我們可以一直向前一個(gè)節(jié)點(diǎn)回溯，最終到達(dá)壓縮列表的表頭節(jié)點(diǎn)。

連鎖更新：

每個(gè)節(jié)點(diǎn)的preivous_entry_length屬性記錄前一個(gè)節(jié)點(diǎn)的長度

如果前一個(gè)節(jié)點(diǎn)長度小于254字節(jié)，preivous_entry_length屬性需要用1字節(jié)長的空間來保存這個(gè)長度值

如果前一個(gè)節(jié)點(diǎn)長度大于等于254字節(jié)，preivous_entry_length屬性需要用5字節(jié)長的空間來保存這個(gè)長度值

如果前一個(gè)節(jié)點(diǎn)長度變大，這個(gè)節(jié)點(diǎn)的preivous_entry_length就要擴(kuò)展，這個(gè)節(jié)點(diǎn)的擴(kuò)展引起下一個(gè)節(jié)點(diǎn)的擴(kuò)展，這就是連鎖更新

redis將這種在特殊情況下產(chǎn)生的連續(xù)多次空間擴(kuò)展操作稱之為連鎖更新

在添加新節(jié)點(diǎn)和刪除節(jié)點(diǎn)都可能引發(fā)連鎖更新。

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

總結(jié)：

壓縮列表是為了節(jié)約內(nèi)存而開發(fā)的順序型數(shù)據(jù)結(jié)構(gòu)，它是列表鍵和哈希鍵的底層實(shí)現(xiàn)之一，壓縮列表可以包含多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或整數(shù)值，添加新節(jié)點(diǎn)或刪除節(jié)點(diǎn)可能引發(fā)連鎖更新操作，這種操作出現(xiàn)幾率不高。