ZipList概述

1.基礎(chǔ)結(jié)構(gòu)

ZipList是一種特殊的“雙向鏈表”，但其實(shí)并不是鏈表，而是一段連續(xù)的內(nèi)存空間，可以在任意一端進(jìn)行壓入/彈出操作。并且該操作的時(shí)間復(fù)雜度是O(1)

結(jié)構(gòu)如下圖：

現(xiàn)在對(duì)每一個(gè)部分進(jìn)行解釋?zhuān)?/p>

• zlbytes:存該壓縮列表的總字節(jié)數(shù)，byte即字節(jié)
• zltail:存最后一個(gè)節(jié)點(diǎn)到壓縮列表的其實(shí)地址之間的字節(jié)數(shù)
• zllen：存的是總entry的個(gè)數(shù)
• entry：即節(jié)點(diǎn)
• zlend：壓縮列表的結(jié)束標(biāo)志，并且值是固定的：0xff

這里補(bǔ)充一點(diǎn)進(jìn)制基礎(chǔ)：

• (1) 0x表示這是16進(jìn)制數(shù)；
• (2) 16進(jìn)制的每一個(gè)16進(jìn)制位可以表示二進(jìn)制的4個(gè)比特位，8個(gè)比特位即一個(gè)字節(jié)。因?yàn)橐粋€(gè)比特位有1和0這兩種可能，4個(gè)比特位就是2的4次方，即能表示0到15這16個(gè)不同的值，剛好就是16進(jìn)制的一個(gè)16進(jìn)制位能表示的值。
• (3) 所以用16進(jìn)制來(lái)表示2進(jìn)制能使二進(jìn)制數(shù)據(jù)更緊湊。

結(jié)合下圖更容易理解：

下圖是每個(gè)部分所占字節(jié)數(shù)：

有沒(méi)有注意到一個(gè)問(wèn)題，為什么這里的entry的長(zhǎng)度是不確定的？

像數(shù)組，只要確定了數(shù)組的類(lèi)型，就能知道其每個(gè)節(jié)點(diǎn)所占字節(jié)數(shù)，為什么這里的不確定的呢？

這就需要我們來(lái)聊聊entry的結(jié)構(gòu)了 。

2.壓縮列表中entry的結(jié)構(gòu)

Ziplist的entry不像普通雙端鏈表那樣記錄前后節(jié)點(diǎn)的指針，因?yàn)橛涗?個(gè)指針要16個(gè)字節(jié)，比較浪費(fèi)內(nèi)存。

Ziplist中的entry采用的如下的結(jié)構(gòu)：

previous_entry_length:存前一個(gè)節(jié)點(diǎn)的總字節(jié)數(shù)，占1或5個(gè)字節(jié)。

• 如果前一個(gè)節(jié)點(diǎn)的長(zhǎng)度小于254字節(jié)，就采用1個(gè)字節(jié)來(lái)保存這個(gè)長(zhǎng)度值， 因?yàn)?個(gè)字節(jié)8個(gè)比特位，能表示（2的8次方-1）的值。
• 如果前一個(gè)節(jié)點(diǎn)的長(zhǎng)度大于或等于254字節(jié)，則采用5個(gè)字節(jié)來(lái)保存這個(gè)長(zhǎng) 度值，并且第一個(gè)字節(jié)是0xfe，后四個(gè)字節(jié)才是真實(shí)長(zhǎng)度數(shù)據(jù)

encoding：存該節(jié)點(diǎn)的內(nèi)容的編碼，用來(lái)區(qū)分content是（自負(fù)床還是整數(shù)），并且存了 content的長(zhǎng)度，占1，2或者5個(gè)字節(jié)稍后有詳細(xì)解釋

content：存該節(jié)點(diǎn)的數(shù)據(jù)，可以是字符串或整數(shù)。

3.壓縮列表怎么雙向遍歷？

壓縮列表的entry既然沒(méi)有存前后2個(gè)節(jié)點(diǎn)的指針，那么怎么雙向遍歷呢？

3.1 正序

先說(shuō)正序：正序時(shí)，已知當(dāng)前entry的起始地址，要知道當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，前面有提到過(guò)，壓縮列表是連續(xù)的一片內(nèi)存空間，所以只要將當(dāng)前節(jié)點(diǎn)的起始地址加上該節(jié)點(diǎn)總占字節(jié)數(shù)（）即可，那這個(gè)當(dāng)前節(jié)點(diǎn)所占字節(jié)數(shù)怎么算呢？

節(jié)點(diǎn)所占字節(jié)數(shù) = previous_entry_length所占字節(jié)數(shù) + encoding所占字節(jié)數(shù) + encoding里面的所存content的長(zhǎng)度

也就是三個(gè)部分的字節(jié)數(shù)相加，只不過(guò)content所占字節(jié)數(shù)要通過(guò)encoding里面獲取。

3.2 逆序

再說(shuō)逆序：逆序時(shí)，已知當(dāng)前entry的起始地址，只要用當(dāng)前entry的起始地址減去previous_entry_length就是前一個(gè)節(jié)點(diǎn)的起始地址了。因?yàn)?strong>previous_entry_length存的就是前一個(gè)節(jié)點(diǎn)總占字節(jié)數(shù)。

4.encoding編碼

4.1 字符串

前面2個(gè)比特位用來(lái)標(biāo)記該content是字符串，以第一種為例

00標(biāo)記該content是字符串，剩余6位存content的所占字節(jié)，2的6次方-1是63，所以content的長(zhǎng)度最大值是63個(gè)字節(jié)。

這樣說(shuō)可能不太清楚，舉例說(shuō)明：

現(xiàn)在我們要存“ab” 和 “cd”這兩個(gè)字符串，即第一個(gè)節(jié)點(diǎn)存ab，第二個(gè)節(jié)點(diǎn)存cd

首先存ab:

previous_entry_length:

• 因?yàn)檫@是第一個(gè)節(jié)點(diǎn)，所以前一個(gè)節(jié)點(diǎn)的所占字節(jié)數(shù)為0
• 所以previous_entry_length = 00000000

encoding:

• 因?yàn)閍b是字符串，并且字符串a(chǎn)b所占字節(jié)數(shù)為2，所以前2位是00，占字節(jié)數(shù)是2，
• 所以encoding =00000010

content：a的ASCII值是97，就是二進(jìn)制01100001；

• b的ASCII值是98，就是二進(jìn)制01100010.
• 所以存在entry中是這樣的

轉(zhuǎn)化成16進(jìn)制是這樣的：

然后來(lái)存cd：

previous_entry_length:

• 這是第二個(gè)節(jié)點(diǎn)，前一個(gè)節(jié)點(diǎn)的總占字節(jié)數(shù)為1+1+2=4

所以previous_entry_length = 00000101

encoding:

• 因?yàn)閏d是字符串，并且字符串cd所占字節(jié)數(shù)為2，所以前2位是00，占字節(jié)數(shù)是2，
• 所以encoding =00000010

content：

• c的ASCII值是99，就是二進(jìn)制01100010；
• d的ASCII值是100，就是二進(jìn)制01100011
• 所以存在entry中是這樣的

所以整個(gè)ziplist是這樣的

4.2 整數(shù)

如果encoding是以11開(kāi)始，就表示content存的是整數(shù)

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論