壓縮列表（ziplist）是列表和哈希鍵的底層實現(xiàn)之一。
1 壓縮列表的構(gòu)成
??壓縮列表是Redis節(jié)約成本而開發(fā)，是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)。一個壓縮列表可以包含任意多個節(jié)點，每個節(jié)點可以保存一個字節(jié)數(shù)組或一個整數(shù)值。
??下圖表示壓縮的各個組成部分及含義
??下圖表示一個包含三個節(jié)點的壓縮列表，列表的起始地址的指針為p，那么列表表尾節(jié)點的地址就是p加上zltail的值，即p+60。
2 壓縮列表節(jié)點的構(gòu)成
??每個壓縮列表節(jié)點可以保存一個字節(jié)數(shù)組或者一個整數(shù)值。下圖表示壓縮列表的組成部分及含義。
??2.1 previous_entry_length
??節(jié)點的previous_entry_length屬性以字節(jié)為單位，長度為1字節(jié)或5字節(jié)，記錄壓縮列表前一個節(jié)點的長度。
(1) 如果前一個節(jié)點的長度小于254字節(jié)，那么previous_entry_length屬性長度為1字節(jié)。
(2) 如果前一個節(jié)點的長度大于等于254字節(jié)，那么previous_entry_length屬性長度為5字節(jié)。
??因為節(jié)點的previous_entry_length記錄了前一個節(jié)點的長度，所以程序可以通過指針運(yùn)算，根據(jù)當(dāng)前節(jié)點的起始地址來計算出前一個節(jié)點的起始地址。壓縮列表的從表尾向表頭遍歷操作就是通過這一原理實現(xiàn)的。只要擁有了一個指向某個節(jié)點起始地址的指針，就可以通過這個指針和這個節(jié)點的previous_entry_length屬性，一個一個向前遍歷，最終達(dá)到列表的表頭節(jié)點。
??2.2 encoding
??節(jié)點的encoding屬性記錄了節(jié)點的content屬性所保存數(shù)據(jù)的類型和長度：
(1) 如果是一個字節(jié)長，值的最高位是11開頭的是整數(shù)編碼，表示content保存的是整數(shù)值。
(2) 如果是一個字節(jié)、兩個字節(jié)或者五個字節(jié)長，值的最高位為00、01或10的是字節(jié)數(shù)組編碼，表示content保存的是字節(jié)數(shù)組。
??2.3 content
??節(jié)點的content屬性負(fù)責(zé)保存的值，節(jié)點值可以是一個字節(jié)數(shù)組或者整數(shù)，值的類型和長度由節(jié)點的encoding屬性決定。
??如下圖，表示一個保存字節(jié)數(shù)組的列表節(jié)點，encoding屬性的最高兩個二進(jìn)制位00表示節(jié)點保存的是一個字節(jié)數(shù)組。后六個二進(jìn)制位001011表示字節(jié)數(shù)組的長度，即“hello world”的長度。
??如下圖，表示一個保存整數(shù)值的列表節(jié)點，encoding屬性的最高兩個二進(jìn)制位11表示節(jié)點保存的是一個整數(shù)值，content屬性保存節(jié)點的值10086。
3 連鎖更新
??前面說過，previous_entry_length屬性的長度是1個字節(jié)或5個字節(jié)，如果前一個節(jié)點的長度小于254字節(jié)，就使用1個字節(jié)保存這個長度值，反之使用5個字節(jié)保存這個長度值。
??假設(shè)在壓縮列表中，有多個連續(xù)的、長度介于250字節(jié)到253字節(jié)之間的節(jié)點e1至eN，如下圖所示：
??由于每個節(jié)點的長度均小于254，所以每個節(jié)點的previous_entry_length屬性所需的長度都是1個字節(jié)。
??此時，在表頭插入一個新節(jié)點，這個節(jié)點的長度大于254，由于 e1的previous_entry_length屬性僅長1字節(jié)，沒有辦法保存新節(jié)點的長度，所以長須需要將e1節(jié)點的previous_entry_length屬性從原來的1個字節(jié)擴(kuò)展為5個字節(jié)長。
??由于e1的previous_entry_length屬性添加了4個字節(jié)，導(dǎo)致e1節(jié)點的長度也大于254，所以導(dǎo)致e2節(jié)點previous_entry_length屬性也要從原來的1個字節(jié)擴(kuò)展為5個字節(jié)長...直到eN為止。
??Redis在特殊情況下產(chǎn)生連續(xù)多次空間擴(kuò)展操作稱之為“連鎖更新”（cascade update），下圖表示了這一過程。
??除了新添加節(jié)點會造成連鎖跟新之外，刪除節(jié)點也可能引發(fā)連鎖更新。
??如下圖所示的壓縮列表，e1至eN都是大小介于250字節(jié)到253字節(jié)的節(jié)點，big節(jié)點時長度大于254的節(jié)點，small節(jié)點也是小于254字節(jié)的節(jié)點。small節(jié)點使用5個字節(jié)保存big節(jié)點的長度，如果此時將small節(jié)點刪除，那么需要e1節(jié)點保存big節(jié)點的長度，但是e1節(jié)點的previous_entry_length屬性是1個字節(jié)，需要擴(kuò)展...，導(dǎo)致的情況和插入的情況一致。
??因為連鎖更新在最壞的情況下需要對壓縮列表執(zhí)行N次空間重分配操作，而每次空間分配的最壞復(fù)雜度為O(N)，所以連鎖更新的最壞復(fù)雜度為O(N2)。
??但是，要造成連鎖更新的可能性非常小。首先需要多個連續(xù)的、長度均介于250字節(jié)至253字節(jié)的節(jié)點，這種情況實際上并不多見。同時，即使出現(xiàn)了連鎖更新，但是只要被更新的節(jié)點數(shù)量不多，就不會對性能造成任何影響。
4 小結(jié)
(1) 壓縮列表是一種為節(jié)約內(nèi)存而開發(fā)的順序型數(shù)據(jù)結(jié)構(gòu)，被作為列表鍵和哈希鍵的底層實現(xiàn)。
(2) 壓縮節(jié)點可以包含任意個節(jié)點，每個節(jié)點可以保存一個字節(jié)數(shù)據(jù)或整數(shù)值。
(3) 添加新節(jié)點到壓縮列表，或者從壓縮列表中刪除節(jié)點，可能引發(fā)連鎖更新操作，但是這操作出現(xiàn)的幾率并不高。
??本文完
??注：本文參考《Redis設(shè)計與實現(xiàn)》，如發(fā)現(xiàn)錯誤，請指正！
