Redis 壓縮列表
壓縮列表
Ziplist 是由一系列特殊編碼的內(nèi)存塊構(gòu)成的列表，一個 ziplist 可以包含多個節(jié)點（entry），每個節(jié)點可以保存一個長度受限的字符數(shù)組（不以 \0 結(jié)尾的 char 數(shù)組）或者整數(shù)，包括：
-
字符數(shù)組
- 長度小于等于
63（(2^{6}-1)）字節(jié)的字符數(shù)組 - 長度小于等于
16383（(2^{14}-1)） 字節(jié)的字符數(shù)組 -
長度小于等于
4294967295（(2^{32}-1)）字節(jié)的字符數(shù)組 -
整數(shù)
4位長，介于0至12之間的無符號整數(shù)1字節(jié)長，有符號整數(shù)3字節(jié)長，有符號整數(shù)int16_t類型整數(shù)int32_t類型整數(shù)int64_t類型整數(shù)
因為 ziplist 節(jié)約內(nèi)存的性質(zhì)，哈希鍵、列表鍵和有序集合鍵初始化的底層實現(xiàn)皆采用 ziplist，更多信息請參考《哈希表》、《列表》和《有序集》章節(jié)。
本章先介紹 ziplist 的組成結(jié)構(gòu)，以及 ziplist 節(jié)點的編碼方式。再介紹 ziplist 的添加操作和刪除操作的執(zhí)行過程，以及這兩種操作可能引起的連鎖更新現(xiàn)象。最后介紹 ziplist 的遍歷方法和節(jié)點查找方式。
ziplist 的構(gòu)成
下圖展示了一個 ziplist 的典型分布結(jié)構(gòu)：
area |<---- ziplist header ---->|<----------- entries ------------->|<-end->|
size 4 bytes 4 bytes 2 bytes ? ? ? ? 1 byte
+---------+--------+-------+--------+--------+--------+--------+-------+
component | zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend |
+---------+--------+-------+--------+--------+--------+--------+-------+
^ ^ ^
address | | |
ZIPLIST_ENTRY_HEAD | ZIPLIST_ENTRY_END
|
ZIPLIST_ENTRY_TAIL
圖中各個域的作用如下：
| 域 | 長度/類型 | 域的值 |
|---|---|---|
zlbytes |
uint32_t |
整個 ziplist 占用的內(nèi)存字節(jié)數(shù)，對 ziplist 進行內(nèi)存重分配，或者計算末端時使用。 |
zltail |
uint32_t |
到達 ziplist 表尾節(jié)點的偏移量。通過這個偏移量，可以在不遍歷整個 ziplist 的前提下，彈出表尾節(jié)點。 |
zllen |
uint16_t |
ziplist 中節(jié)點的數(shù)量。當這個值小于 UINT16_MAX （65535）時，這個值就是 ziplist 中節(jié)點的數(shù)量；當這個值等于 UINT16_MAX 時，節(jié)點的數(shù)量需要遍歷整個 ziplist 才能計算得出。 |
entryX |
? |
ziplist 所保存的節(jié)點，各個節(jié)點的長度根據(jù)內(nèi)容而定。 |
zlend |
uint8_t |
255 的二進制值 1111 1111 （UINT8_MAX） ，用于標記 ziplist 的末端。 |
為了方便地取出 ziplist 的各個域以及一些指針地址， ziplist 模塊定義了以下宏：
| 宏 | 作用 | 算法復(fù)雜度 |
|---|---|---|
ZIPLIST_BYTES(ziplist) |
取出 zlbytes 的值 |
(\theta(1)) |
ZIPLIST_TAIL_OFFSET(ziplist) |
取出 zltail 的值 |
(\theta(1)) |
ZIPLIST_LENGTH(ziplist) |
取出 zllen 的值 |
(\theta(1)) |
ZIPLIST_HEADER_SIZE |
返回 ziplist header 部分的長度，總是固定的 10 字節(jié) |
(\theta(1)) |
ZIPLIST_ENTRY_HEAD(ziplist) |
返回到達 ziplist 第一個節(jié)點（表頭）的地址 | (\theta(1)) |
ZIPLIST_ENTRY_TAIL(ziplist) |
返回到達 ziplist 最后一個節(jié)點（表尾）的地址 | (\theta(1)) |
ZIPLIST_ENTRY_END(ziplist) |
返回 ziplist 的末端，也即是 zlend 之前的地址 |
(\theta(1)) |
因為 ziplist header 部分的長度總是固定的（4 字節(jié) + 4 字節(jié) + 2 字節(jié)），因此將指針移動到表頭節(jié)點的復(fù)雜度為常數(shù)時間；除此之外，因為表尾節(jié)點的地址可以通過 zltail 計算得出，因此將指針移動到表尾節(jié)點的復(fù)雜度也為常數(shù)時間。
以下是用于操作 ziplist 的函數(shù)：
| 函數(shù)名 | 作用 | 算法復(fù)雜度 |
|---|---|---|
ziplistNew |
創(chuàng)建一個新的 ziplist | (\theta(1)) |
ziplistResize |
重新調(diào)整 ziplist 的內(nèi)存大小 | (O(N)) |
ziplistPush |
將一個包含給定值的新節(jié)點推入 ziplist 的表頭或者表尾 | (O(N^2)) |
zipEntry |
取出給定地址上的節(jié)點，并將它的屬性保存到 zlentry 結(jié)構(gòu)然后返回 |
(\theta(1)) |
ziplistInsert |
將一個包含給定值的新節(jié)點插入到給定地址 | (O(N^2)) |
ziplistDelete |
刪除給定地址上的節(jié)點 | (O(N^2)) |
ziplistDeleteRange |
在給定索引上，連續(xù)進行多次刪除 | (O(N^2)) |
ziplistFind |
在 ziplist 中查找并返回包含給定值的節(jié)點 | (O(N)) |
ziplistLen |
返回 ziplist 保存的節(jié)點數(shù)量 | (O(N)) |
ziplistBlobLen |
以字節(jié)為單位，返回 ziplist 占用的內(nèi)存大小 | (\theta(1)) |
因為 ziplist 由連續(xù)的內(nèi)存塊構(gòu)成，在最壞情況下，當 ziplistPush 、 ziplistDelete 這類對節(jié)點進行增加或刪除的函數(shù)之后，程序需要執(zhí)行一種稱為連鎖更新的動作來維持 ziplist 結(jié)構(gòu)本身的性質(zhì)，所以這些函數(shù)的最壞復(fù)雜度都為 (O(N^2)) 。不過，因為這種最壞情況出現(xiàn)的概率并不高，所以大可以放心使用 ziplist ，而不必太擔心出現(xiàn)最壞情況。
節(jié)點的構(gòu)成
一個 ziplist 可以包含多個節(jié)點，每個節(jié)點可以劃分為以下幾個部分：
area |<------------------- entry -------------------->|
+------------------+----------+--------+---------+
component | pre_entry_length | encoding | length | content |
+------------------+----------+--------+---------+
以下幾個小節(jié)將分別對這個四個部分進行介紹。
pre_entry_length
pre_entry_length 記錄了前一個節(jié)點的長度，通過這個值，可以進行指針計算，從而跳轉(zhuǎn)到上一個節(jié)點。
area |<---- previous entry --->|<--------------- current entry ---------------->|
size 5 bytes 1 byte ? ? ?
+-------------------------+-----------------------------+--------+---------+
component | ... | pre_entry_length | encoding | length | content |
| | | | | |
value | | 0000 0101 | ? | ? | ? |
+-------------------------+-----------------------------+--------+---------+
^ ^
address | |
p = e - 5 e
上圖展示了如何通過一個節(jié)點向前跳轉(zhuǎn)到另一個節(jié)點：用指向當前節(jié)點的指針 e ，減去 pre_entry_length 的值（0000 0101 的十進制值， 5），得出的結(jié)果就是指向前一個節(jié)點的地址 p 。
根據(jù)編碼方式的不同， pre_entry_length 域可能占用 1 字節(jié)或者 5 字節(jié)：
1字節(jié)：如果前一節(jié)點的長度小于254字節(jié)，便使用一個字節(jié)保存它的值。5字節(jié)：如果前一節(jié)點的長度大于等于254字節(jié)，那么將第1個字節(jié)的值設(shè)為254，然后用接下來的4個字節(jié)保存實際長度。
作為例子，以下是個長度為 1 字節(jié)的 pre_entry_length 域，域的值為 128 （二進制為 1000 0000 ）：
area |<------------------- entry -------------------->|
size 1 byte ? ? ?
+------------------+----------+--------+---------+
component | pre_entry_length | encoding | length | content |
| | | | |
value | 1000 0000 | | | |
+------------------+----------+--------+---------+
而以下則是個長度為 5 字節(jié)的 pre_entry_length 域，域的第一個字節(jié)被設(shè)為 254 的二進制 1111 1110 ，而之后的四個字節(jié)則被設(shè)置為 10086 的二進制 10 0111 0110 0110 （多余的高位用 0 補完）：
area |<------------------------------ entry ---------------------------------->|
size 5 bytes ? ? ?
+-------------------------------------------+----------+--------+---------+
component | pre_entry_length | encoding | length | content |
| | | | |
| 11111110 00000000000000000010011101100110 | ? | ? | ? |
+-------------------------------------------+----------+--------+---------+
|<------->|<------------------------------->|
1 byte 4 bytes
encoding 和 length
encoding 和 length 兩部分一起決定了 content 部分所保存的數(shù)據(jù)的類型（以及長度）。
其中， encoding 域的長度為兩個 bit ，它的值可以是 00 、 01 、 10 和 11 ：
00、01和10表示content部分保存著字符數(shù)組。11表示content部分保存著整數(shù)。
以 00 、 01 和 10 開頭的字符數(shù)組的編碼方式如下：
| 編碼 | 編碼長度 | content 部分保存的值 |
|---|---|---|
00bbbbbb |
1 byte | 長度小于等于 63 字節(jié)的字符數(shù)組。 |
01bbbbbb xxxxxxxx |
2 byte | 長度小于等于 16383 字節(jié)的字符數(shù)組。 |
10____ aaaaaaaa bbbbbbbb cccccccc dddddddd |
5 byte | 長度小于等于 4294967295 的字符數(shù)組。 |
表格中的下劃線 _ 表示留空，而變量 b 、 x 等則代表實際的二進制數(shù)據(jù)。為了方便閱讀，多個字節(jié)之間用空格隔開。
11 開頭的整數(shù)編碼如下：
| 編碼 | 編碼長度 | content 部分保存的值 |
|---|---|---|
11000000 |
1 byte | int16_t 類型的整數(shù) |
11010000 |
1 byte | int32_t 類型的整數(shù) |
11100000 |
1 byte | int64_t 類型的整數(shù) |
11110000 |
1 byte | 24 bit 有符號整數(shù) |
11111110 |
1 byte | 8 bit 有符號整數(shù) |
1111xxxx |
1 byte | 4 bit 無符號整數(shù)，介于 0 至 12 之間 |
content
content 部分保存著節(jié)點的內(nèi)容，類型和長度由 encoding 和 length 決定。
以下是一個保存著字符數(shù)組 hello world 的節(jié)點的例子：
area |<---------------------- entry ----------------------->|
size ? 2 bit 6 bit 11 byte
+------------------+----------+--------+---------------+
component | pre_entry_length | encoding | length | content |
| | | | |
value | ? | 00 | 001011 | hello world |
+------------------+----------+--------+---------------+
encoding 域的值 00 表示節(jié)點保存著一個長度小于等于 63 字節(jié)的字符數(shù)組，length 域給出了這個字符數(shù)組的準確長度 —— 11 字節(jié)（的二進制 001011），content 則保存著字符數(shù)組值 hello world 本身（為了方便表示， content 部分使用字符而不是二進制表示）。
以下是另一個節(jié)點，它保存著整數(shù) 10086 ：
area |<---------------------- entry ----------------------->|
size ? 2 bit 6 bit 2 bytes
+------------------+----------+--------+---------------+
component | pre_entry_length | encoding | length | content |
| | | | |
value | ? | 11 | 000000 | 10086 |
+------------------+----------+--------+---------------+
encoding 域的值 11 表示節(jié)點保存的是一個整數(shù)；而 length 域的值 000000 表示這個節(jié)點的值的類型為 int16_t ；最后， content 保存著整數(shù)值 10086 本身（為了方便表示， content 部分用十進制而不是二進制表示）。
創(chuàng)建新 ziplist
函數(shù) ziplistNew 用于創(chuàng)建一個新的空白 ziplist ，這個 ziplist 可以表示為下圖：
area |<---- ziplist header ---->|<-- end -->|
size 4 bytes 4 bytes 2 bytes 1 byte
+---------+--------+-------+-----------+
component | zlbytes | zltail | zllen | zlend |
| | | | |
value | 1011 | 1010 | 0 | 1111 1111 |
+---------+--------+-------+-----------+
^
|
ZIPLIST_ENTRY_HEAD
&
address ZIPLIST_ENTRY_TAIL
&
ZIPLIST_ENTRY_END
空白 ziplist 的表頭、表尾和末端處于同一地址。
創(chuàng)建了 ziplist 之后，就可以往里面添加新節(jié)點了，根據(jù)新節(jié)點添加位置的不同，這個工作可以分為兩類來進行：
- 將節(jié)點添加到 ziplist 末端：在這種情況下，新節(jié)點的后面沒有任何節(jié)點。
- 將節(jié)點添加到某個/某些節(jié)點的前面：在這種情況下，新節(jié)點的后面有至少一個節(jié)點。
以下兩個小節(jié)分別討論這兩種情況。
將節(jié)點添加到末端
將新節(jié)點添加到 ziplist 的末端需要執(zhí)行以下三個步驟：
- 記錄到達 ziplist 末端所需的偏移量（因為之后的內(nèi)存重分配可能會改變 ziplist 的地址，因此記錄偏移量而不是保存指針）
- 根據(jù)新節(jié)點要保存的值，計算出編碼這個值所需的空間大小，以及編碼它前一個節(jié)點的長度所需的空間大小，然后對 ziplist 進行內(nèi)存重分配。
- 設(shè)置新節(jié)點的各項屬性：
pre_entry_length、encoding、length和content。 - 更新 ziplist 的各項屬性，比如記錄空間占用的
zlbytes，到達表尾節(jié)點的偏移量zltail，以及記錄節(jié)點數(shù)量的zllen。
舉個例子，假設(shè)現(xiàn)在要將一個新節(jié)點添加到只含有一個節(jié)點的 ziplist 上，程序首先要執(zhí)行步驟 1 ，定位 ziplist 的末端：
area |<---- ziplist header ---->|<--- entries -->|<-- end -->|
size 4 bytes 4 bytes 2 bytes 5 bytes 1 bytes
+---------+--------+-------+----------------+-----------+
component | zlbytes | zltail | zllen | entry 1 | zlend |
| | | | | |
value | 10000 | 1010 | 1 | ? | 1111 1111 |
+---------+--------+-------+----------------+-----------+
^ ^
| |
address ZIPLIST_ENTRY_HEAD ZIPLIST_ENTRY_END
&
ZIPLIST_ENTRY_TAIL
然后執(zhí)行步驟 2 ，程序需要計算新節(jié)點所需的空間：
假設(shè)我們要添加到節(jié)點里的值為字符數(shù)組 hello world ，那么保存這個值共需要 12 字節(jié)的空間：
- 11 字節(jié)用于保存字符數(shù)組本身；
- 另外 1 字節(jié)中的 2 bit 用于保存類型編碼
00， 而其余 6 bit 則保存字符數(shù)組長度11的二進制001011。
另外，節(jié)點還需要 1 字節(jié)，用于保存前一個節(jié)點的長度 5 （二進制 101 ）。
合算起來，為了添加新節(jié)點， ziplist 總共需要多分配 13 字節(jié)空間。以下是分配完成之后， ziplist 的樣子：
area |<---- ziplist header ---->|<------------ entries ------------>|<-- end -->|
size 4 bytes 4 bytes 2 bytes 5 bytes 13 bytes 1 bytes
+---------+--------+-------+----------------+------------------+-----------+
component | zlbytes | zltail | zllen | entry 1 | entry 2 | zlend |
| | | | | | |
value | 10000 | 1010 | 1 | ? | pre_entry_length | 1111 1111 |
| | | | | ? | |
| | | | | | |
| | | | | encoding | |
| | | | | ? | |
| | | | | | |
| | | | | length | |
| | | | | ? | |
| | | | | | |
| | | | | content | |
| | | | | ? | |
| | | | | | |
+---------+--------+-------+----------------+------------------+-----------+
^ ^
| |
address ZIPLIST_ENTRY_HEAD ZIPLIST_ENTRY_END
&
ZIPLIST_ENTRY_TAIL
步驟三，更新新節(jié)點的各項屬性（為了方便表示， content 的內(nèi)容使用字符而不是二進制來表示）：
area |<---- ziplist header ---->|<------------ entries ------------>|<-- end -->|
size 4 bytes 4 bytes 2 bytes 5 bytes 13 bytes 1 bytes
+---------+--------+-------+----------------+------------------+-----------+
component | zlbytes | zltail | zllen | entry 1 | entry 2 | zlend |
| | | | | | |
value | 10000 | 1010 | 1 | ? | pre_entry_length | 1111 1111 |
| | | | | 101 | |
| | | | | | |
| | | | | encoding | |
| | | | | 00 | |
| | | | | | |
| | | | | length | |
| | | | | 001011 | |
| | | | | | |
| | | | | content | |
| | | | | hello world | |
| | | | | | |
+---------+--------+-------+----------------+------------------+-----------+
^ ^
| |
address ZIPLIST_ENTRY_HEAD ZIPLIST_ENTRY_END
&
ZIPLIST_ENTRY_TAIL
最后一步，更新 ziplist 的 zlbytes 、 zltail 和 zllen 屬性：
area |<---- ziplist header ---->|<------------ entries ------------>|<-- end -->|
size 4 bytes 4 bytes 2 bytes 5 bytes 13 bytes 1 bytes
+---------+--------+-------+----------------+------------------+-----------+
component | zlbytes | zltail | zllen | entry 1 | entry 2 | zlend |
| | | | | | |
value | 11101 | 1111 | 10 | ? | pre_entry_length | 1111 1111 |
| | | | | 101 | |
| | | | | | |
| | | | | encoding | |
| | | | | 00 | |
| | | | | | |
| | | | | length | |
| | | | | 001011 | |
| | | | | | |
| | | | | content | |
| | | | | hello world | |
| | | | | | |
+---------+--------+-------+----------------+------------------+-----------+
^ ^ ^
| | |
address | ZIPLIST_ENTRY_TAIL ZIPLIST_ENTRY_END
|
ZIPLIST_ENTRY_HEAD
到這一步，添加新節(jié)點到表尾的工作正式完成。
Note
這里沒有演示往空 ziplist 添加第一個節(jié)點的過程，因為這個過程和上面演示的添加第二個節(jié)點的過程類似；而且因為第一個節(jié)點的存在，添加第二個節(jié)點的過程可以更好地展示“將節(jié)點添加到表尾”這一操作的一般性。
將節(jié)點添加到某個/某些節(jié)點的前面
比起將新節(jié)點添加到 ziplist 的末端，將一個新節(jié)點添加到某個/某些節(jié)點的前面要復(fù)雜得多，因為這種操作除了將新節(jié)點添加到 ziplist 以外，還可能引起后續(xù)一系列節(jié)點的改變。
舉個例子，假設(shè)我們要將一個新節(jié)點 new 添加到節(jié)點 prev 和 next 之間：
add new entry here
|
V
+----------+----------+----------+----------+----------+
| | | | | |
| prev | next | next + 1 | next + 2 | ... |
| | | | | |
+----------+----------+----------+----------+----------+
程序首先為新節(jié)點擴大 ziplist 的空間：
+----------+----------+----------+----------+----------+----------+
| | | | | | |
| prev | ??? | next | next + 1 | next + 2 | ... |
| | | | | | |
+----------+----------+----------+----------+----------+----------+
|<-------->|
expand
space
然后設(shè)置 new 節(jié)點的各項值 ——到目前為止，一切都和前面介紹的添加操作一樣：
set value,
property,
length,
etc.
|
v
+----------+----------+----------+----------+----------+----------+
| | | | | | |
| prev | new | next | next + 1 | next + 2 | ... |
| | | | | | |
+----------+----------+----------+----------+----------+----------+
現(xiàn)在，新的 new 節(jié)點取代原來的 prev 節(jié)點，成為了 next 節(jié)點的新前驅(qū)節(jié)點，不過，因為這時 next 節(jié)點的 pre_entry_length 域編碼的仍然是 prev 節(jié)點的長度，所以程序需要將 new 節(jié)點的長度編碼進 next 節(jié)點的 pre_entry_length 域里，這里會出現(xiàn)三種可能：
next的pre_entry_length域的長度正好能夠編碼new的長度（都是 1 字節(jié)或者都是 5 字節(jié)）next的pre_entry_length只有 1 字節(jié)長，但編碼new的長度需要 5 字節(jié)next的pre_entry_length有 5 字節(jié)長，但編碼new的長度只需要 1 字節(jié)
對于情況 1 和 3 ，程序直接更新 next 的 pre_entry_length 域。
如果是第二種情況，那么程序必須對 ziplist 進行內(nèi)存重分配，從而擴展 next 的空間。然而，因為 next 的空間長度改變了，所以程序又必須檢查 next 的后繼節(jié)點 —— next+1 ，看它的 pre_entry_length 能否編碼 next 的新長度，如果不能的話，程序又需要繼續(xù)對 next+1 進行擴容。。。
這就是說，在某個/某些節(jié)點的前面添加新節(jié)點之后，程序必須沿著路徑挨個檢查后續(xù)的節(jié)點，是否滿足新長度的編碼要求，直到遇到一個能滿足要求的節(jié)點（如果有一個能滿足，則這個節(jié)點之后的其他節(jié)點也滿足），或者到達 ziplist 的末端 zlend 為止，這種檢查操作的復(fù)雜度為 (O(N^2)) 。
不過，因為只有在新添加節(jié)點的后面有連續(xù)多個長度接近 254 的節(jié)點時，這種連鎖更新才會發(fā)生，所以可以普遍地認為，這種連鎖更新發(fā)生的概率非常小，在一般情況下，將添加操作看成是 (O(N)) 復(fù)雜度也是可以的。
執(zhí)行完這三種情況的其中一種后，程序更新 ziplist 的各項屬性，至此，添加操作完成。
Note
在第三種情況中，程序?qū)嶋H上是可以執(zhí)行類似于情況二的動作的：它可以挨個地檢查新節(jié)點之后的節(jié)點，嘗試收縮它們的空間長度，不過 Redis 決定不這么做，因為在一些情況下，比如前面提到的，有連續(xù)多個長度接近 254 的節(jié)點時，可能會出現(xiàn)重復(fù)的擴展——收縮——再擴展——再收縮的抖動（flapping）效果，這會讓操作的性能變得非常差。
刪除節(jié)點
刪除節(jié)點和添加操作的步驟類似。
1) 定位目標節(jié)點，并計算節(jié)點的空間長度 target-size ：
target start here
|
V
+----------+----------+----------+----------+----------+----------+
| | | | | | |
| prev | target | next | next + 1 | next + 2 | ... |
| | | | | | |
+----------+----------+----------+----------+----------+----------+
|<-------->|
target-size
2) 進行內(nèi)存移位，覆蓋 target 原本的數(shù)據(jù)，然后通過內(nèi)存重分配，收縮多余空間：
target start here
|
V
+----------+----------+----------+----------+----------+
| | | | | |
| prev | next | next + 1 | next + 2 | ... |
| | | | | |
+----------+----------+----------+----------+----------+
| <------------------------------------------ memmove
3) 檢查 next 、 next+1 等后續(xù)節(jié)點能否滿足新前驅(qū)節(jié)點的編碼。和添加操作一樣，刪除操作也可能會引起連鎖更新。
遍歷
可以對 ziplist 進行從前向后的遍歷，或者從后先前的遍歷。
當進行從前向后的遍歷時，程序從指向節(jié)點 e1 的指針 p 開始，計算節(jié)點 e1 的長度（e1-size），然后將 p 加上 e1-size ，就將指針后移到了下一個節(jié)點 e2 。。。如此反覆，直到 p 遇到 ZIPLIST_ENTRY_END 為止，這樣整個 ziplist 就遍歷完了：
p + e1-size + e2-size
p + e1-size |
p | |
| | |
V V V
+----------+----------+----------+----------+----------+----------+----------+
| ZIPLIST | | | | | | ZIPLIST |
| ENTRY | e1 | e2 | e3 | e4 | ... | ENTRY |
| HEAD | | | | | | END |
+----------+----------+----------+----------+----------+----------+----------+
|<-------->|<-------->|
e1-size e2-size
當進行從后往前遍歷的時候，程序從指向節(jié)點 eN 的指針 p 出發(fā)，取出 eN 的 pre_entry_length 值，然后用 p 減去 pre_entry_length ，這就將指針移動到了前一個節(jié)點 eN-1 。。。如此反覆，直到 p 遇到 ZIPLIST_ENTRY_HEAD 為止，這樣整個 ziplist 就遍歷完了。
p - eN.pre_entry_length
|
| p
| |
V V
+----------+----------+----------+----------+----------+----------+----------+
| ZIPLIST | | | | | | ZIPLIST |
| ENTRY | e1 | e2 | ... | eN-1 | eN | ENTRY |
| HEAD | | | | | | END |
+----------+----------+----------+----------+----------+----------+----------+
查找元素、根據(jù)值定位節(jié)點
這兩個操作和遍歷的原理基本相同，不再贅述。
小結(jié)
-
ziplist 是由一系列特殊編碼的內(nèi)存塊構(gòu)成的列表，可以保存字符數(shù)組或整數(shù)值，同時是哈希鍵、列表鍵和有序集合鍵的底層實現(xiàn)之一。
-
ziplist 典型分布結(jié)構(gòu)如下：
area |<---- ziplist header ---->|<----------- entries ------------->|<-end->|
size 4 bytes 4 bytes 2 bytes ? ? ? ? 1 byte
+---------+--------+-------+--------+--------+--------+--------+-------+
component | zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend |
+---------+--------+-------+--------+--------+--------+--------+-------+
^ ^ ^
address | | |
ZIPLIST_ENTRY_HEAD | ZIPLIST_ENTRY_END
|
ZIPLIST_ENTRY_TAIL
-
ziplist 節(jié)點的分布結(jié)構(gòu)如下：
area |<------------------- entry -------------------->|
+------------------+----------+--------+---------+
component | pre_entry_length | encoding | length | content |
+------------------+----------+--------+---------+
-
添加和刪除 ziplist 節(jié)點有可能會引起連鎖更新，因此，添加和刪除操作的最壞復(fù)雜度為 (O(N^2)) ，不過，因為連鎖更新的出現(xiàn)概率并不高，所以一般可以將添加和刪除操作的復(fù)雜度視為 (O(N)) 。
掃描二維碼
下載編程獅App
編程獅公眾號
更多建議：