ZipList概述

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

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

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

現(xiàn)在對每一個部分進行解釋：

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

這里補充一點進制基礎(chǔ)：

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

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

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

有沒有注意到一個問題，為什么這里的entry的長度是不確定的？

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

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

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

Ziplist的entry不像普通雙端鏈表那樣記錄前后節(jié)點的指針，因為記錄2個指針要16個字節(jié)，比較浪費內(nèi)存。

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

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

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

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

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

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

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

3.1 正序

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

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

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

3.2 逆序

再說逆序：逆序時，已知當前entry的起始地址，只要用當前entry的起始地址減去previous_entry_length就是前一個節(jié)點的起始地址了。因為previous_entry_length存的就是前一個節(jié)點總占字節(jié)數(shù)。

4.encoding編碼

4.1 字符串

前面2個比特位用來標記該content是字符串，以第一種為例

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

這樣說可能不太清楚，舉例說明：

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

首先存ab:

previous_entry_length:

• 因為這是第一個節(jié)點，所以前一個節(jié)點的所占字節(jié)數(shù)為0
• 所以previous_entry_length = 00000000

encoding:

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

content：a的ASCII值是97，就是二進制01100001；

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

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

然后來存cd：

previous_entry_length:

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

所以previous_entry_length = 00000101

encoding:

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

content：

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

所以整個ziplist是這樣的

4.2 整數(shù)

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

總結(jié)

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

最新評論