壓縮列表（ziplist）是列表和哈希鍵的底層實現(xiàn)之一储耐。
1 壓縮列表的構(gòu)成
??壓縮列表是Redis節(jié)約成本而開發(fā)，是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)滨溉。一個壓縮列表可以包含任意多個節(jié)點(diǎn)什湘，每個節(jié)點(diǎn)可以保存一個字節(jié)數(shù)組或一個整數(shù)值。
??下圖表示壓縮的各個組成部分及含義
??下圖表示一個包含三個節(jié)點(diǎn)的壓縮列表晦攒，列表的起始地址的指針為p闽撤，那么列表表尾節(jié)點(diǎn)的地址就是p加上zltail的值，即p+60脯颜。
2 壓縮列表節(jié)點(diǎn)的構(gòu)成
??每個壓縮列表節(jié)點(diǎn)可以保存一個字節(jié)數(shù)組或者一個整數(shù)值哟旗。下圖表示壓縮列表的組成部分及含義。
??2.1 previous_entry_length
??節(jié)點(diǎn)的previous_entry_length屬性以字節(jié)為單位栋操，長度為1字節(jié)或5字節(jié)闸餐，記錄壓縮列表前一個節(jié)點(diǎn)的長度。
(1) 如果前一個節(jié)點(diǎn)的長度小于254字節(jié)矾芙，那么previous_entry_length屬性長度為1字節(jié)舍沙。
(2) 如果前一個節(jié)點(diǎn)的長度大于等于254字節(jié)，那么previous_entry_length屬性長度為5字節(jié)剔宪。
??因為節(jié)點(diǎn)的previous_entry_length記錄了前一個節(jié)點(diǎn)的長度拂铡，所以程序可以通過指針運(yùn)算壹无，根據(jù)當(dāng)前節(jié)點(diǎn)的起始地址來計算出前一個節(jié)點(diǎn)的起始地址。壓縮列表的從表尾向表頭遍歷操作就是通過這一原理實現(xiàn)的和媳。只要擁有了一個指向某個節(jié)點(diǎn)起始地址的指針格遭，就可以通過這個指針和這個節(jié)點(diǎn)的previous_entry_length屬性，一個一個向前遍歷留瞳，最終達(dá)到列表的表頭節(jié)點(diǎn)拒迅。
??2.2 encoding
??節(jié)點(diǎn)的encoding屬性記錄了節(jié)點(diǎn)的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é)點(diǎn)的content屬性負(fù)責(zé)保存的值屹电，節(jié)點(diǎn)值可以是一個字節(jié)數(shù)組或者整數(shù)，值的類型和長度由節(jié)點(diǎn)的encoding屬性決定跃巡。
??如下圖危号，表示一個保存字節(jié)數(shù)組的列表節(jié)點(diǎn)，encoding屬性的最高兩個二進(jìn)制位00表示節(jié)點(diǎn)保存的是一個字節(jié)數(shù)組素邪。后六個二進(jìn)制位001011表示字節(jié)數(shù)組的長度外莲，即“hello world”的長度。
??如下圖兔朦，表示一個保存整數(shù)值的列表節(jié)點(diǎn)偷线，encoding屬性的最高兩個二進(jìn)制位11表示節(jié)點(diǎn)保存的是一個整數(shù)值，content屬性保存節(jié)點(diǎn)的值10086沽甥。
3 連鎖更新
??前面說過声邦，previous_entry_length屬性的長度是1個字節(jié)或5個字節(jié)，如果前一個節(jié)點(diǎn)的長度小于254字節(jié)安接，就使用1個字節(jié)保存這個長度值翔忽，反之使用5個字節(jié)保存這個長度值。
??假設(shè)在壓縮列表中盏檐，有多個連續(xù)的歇式、長度介于250字節(jié)到253字節(jié)之間的節(jié)點(diǎn)e1至eN，如下圖所示：
??由于每個節(jié)點(diǎn)的長度均小于254胡野，所以每個節(jié)點(diǎn)的previous_entry_length屬性所需的長度都是1個字節(jié)材失。
??此時，在表頭插入一個新節(jié)點(diǎn)硫豆，這個節(jié)點(diǎn)的長度大于254龙巨，由于 e1的previous_entry_length屬性僅長1字節(jié)笼呆，沒有辦法保存新節(jié)點(diǎn)的長度，所以長須需要將e1節(jié)點(diǎn)的previous_entry_length屬性從原來的1個字節(jié)擴(kuò)展為5個字節(jié)長旨别。
??由于e1的previous_entry_length屬性添加了4個字節(jié)诗赌，導(dǎo)致e1節(jié)點(diǎn)的長度也大于254，所以導(dǎo)致e2節(jié)點(diǎn)previous_entry_length屬性也要從原來的1個字節(jié)擴(kuò)展為5個字節(jié)長...直到eN為止秸弛。
??Redis在特殊情況下產(chǎn)生連續(xù)多次空間擴(kuò)展操作稱之為“連鎖更新”（cascade update）铭若，下圖表示了這一過程。
??除了新添加節(jié)點(diǎn)會造成連鎖跟新之外递览，刪除節(jié)點(diǎn)也可能引發(fā)連鎖更新叼屠。
??如下圖所示的壓縮列表，e1至eN都是大小介于250字節(jié)到253字節(jié)的節(jié)點(diǎn)绞铃，big節(jié)點(diǎn)時長度大于254的節(jié)點(diǎn)镜雨，small節(jié)點(diǎn)也是小于254字節(jié)的節(jié)點(diǎn)。small節(jié)點(diǎn)使用5個字節(jié)保存big節(jié)點(diǎn)的長度儿捧，如果此時將small節(jié)點(diǎn)刪除荚坞，那么需要e1節(jié)點(diǎn)保存big節(jié)點(diǎn)的長度，但是e1節(jié)點(diǎn)的previous_entry_length屬性是1個字節(jié)菲盾，需要擴(kuò)展...西剥，導(dǎo)致的情況和插入的情況一致。
??因為連鎖更新在最壞的情況下需要對壓縮列表執(zhí)行N次空間重分配操作亿汞，而每次空間分配的最壞復(fù)雜度為O(N)，所以連鎖更新的最壞復(fù)雜度為O(N2)揪阿。
??但是疗我，要造成連鎖更新的可能性非常小。首先需要多個連續(xù)的南捂、長度均介于250字節(jié)至253字節(jié)的節(jié)點(diǎn)吴裤，這種情況實際上并不多見。同時溺健，即使出現(xiàn)了連鎖更新麦牺，但是只要被更新的節(jié)點(diǎn)數(shù)量不多，就不會對性能造成任何影響鞭缭。
4 小結(jié)
(1) 壓縮列表是一種為節(jié)約內(nèi)存而開發(fā)的順序型數(shù)據(jù)結(jié)構(gòu)剖膳，被作為列表鍵和哈希鍵的底層實現(xiàn)。
(2) 壓縮節(jié)點(diǎn)可以包含任意個節(jié)點(diǎn)岭辣，每個節(jié)點(diǎn)可以保存一個字節(jié)數(shù)據(jù)或整數(shù)值吱晒。
(3) 添加新節(jié)點(diǎn)到壓縮列表，或者從壓縮列表中刪除節(jié)點(diǎn)沦童，可能引發(fā)連鎖更新操作仑濒，但是這操作出現(xiàn)的幾率并不高叹话。
??本文完
??注：本文參考《Redis設(shè)計與實現(xiàn)》，如發(fā)現(xiàn)錯誤墩瞳，請指正驼壶！
