概述
- 壓縮列表是列表、哈希的底層實(shí)現(xiàn)之一
- 當(dāng)列表只包含少量列表項(xiàng)，并且要么是小整數(shù)值、短字符串時(shí)，采用壓縮列表
- 哈希表只包含少量鍵值對(duì)，鍵值對(duì)的鍵和值要么都是小整數(shù)、短字符串，采用壓縮列表實(shí)現(xiàn)哈希
<zlbytes> 是一個(gè)無(wú)符號(hào)整數(shù)，保存著 ziplist 使用的內(nèi)存數(shù)量。
通過(guò)這個(gè)值，程序可以直接對(duì) ziplist 的內(nèi)存大小進(jìn)行調(diào)整，
而無(wú)須為了計(jì)算 ziplist 的內(nèi)存大小而遍歷整個(gè)列表。
<zltail> is the offset to the last entry in the list. This allows a pop
operation on the far side of the list without the need for full traversal.
<zltail> 保存著到達(dá)列表中最后一個(gè)節(jié)點(diǎn)的偏移量。
這個(gè)偏移量使得對(duì)表尾的 pop 操作可以在無(wú)須遍歷整個(gè)列表的情況下進(jìn)行。
<zllen> is the number of entries.When this value is larger than 2**16-2,
we need to traverse the entire list to know how many items it holds.
<zllen> 保存著列表中的節(jié)點(diǎn)數(shù)量。
當(dāng) zllen 保存的值大于 2**16-2 時(shí)，
程序需要遍歷整個(gè)列表才能知道列表實(shí)際包含了多少個(gè)節(jié)點(diǎn)。
<zlend> is a single byte special value, equal to 255, which indicates the
end of the list.
<zlend> 的長(zhǎng)度為 1 字節(jié)，值為 255 ，標(biāo)識(shí)列表的末尾。
- 每個(gè) ziplist 節(jié)點(diǎn)的前面都帶有一個(gè) header ，這個(gè) header 包含兩部分信息：
- 前置節(jié)點(diǎn)的長(zhǎng)度，在程序從后向前遍歷時(shí)使用。
- 當(dāng)前節(jié)點(diǎn)所保存的值的類型和長(zhǎng)度。
編碼前置節(jié)點(diǎn)的長(zhǎng)度的方法如下：
如果前置節(jié)點(diǎn)的長(zhǎng)度小于 254 字節(jié)，那么程序?qū)⑹褂?1 個(gè)字節(jié)來(lái)保存這個(gè)長(zhǎng)度值。
-
如果前置節(jié)點(diǎn)的長(zhǎng)度大于等于 254 字節(jié)，那么程序?qū)⑹褂?5 個(gè)字節(jié)來(lái)保存這個(gè)長(zhǎng)度值：
- 第 1 個(gè)字節(jié)的值將被設(shè)為 254 ，用于標(biāo)識(shí)這是一個(gè) 5 字節(jié)長(zhǎng)的長(zhǎng)度值。
- 之后的 4 個(gè)字節(jié)則用于保存前置節(jié)點(diǎn)的實(shí)際長(zhǎng)度。
header 另一部分的內(nèi)容和節(jié)點(diǎn)所保存的值有關(guān)。
- 如果節(jié)點(diǎn)保存的是字符串值，
那么這部分 header 的頭 2 個(gè)位將保存編碼字符串長(zhǎng)度所使用的類型，
而之后跟著的內(nèi)容則是字符串的實(shí)際長(zhǎng)度。
- |00pppppp| - 1 byte
String value with length less than or equal to 63 bytes (6 bits).
字符串的長(zhǎng)度小于或等于 63 字節(jié)。 - |01pppppp|qqqqqqqq| - 2 bytes
String value with length less than or equal to 16383 bytes (14 bits).
字符串的長(zhǎng)度小于或等于 16383 字節(jié)。 - |10______|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes
String value with length greater than or equal to 16384 bytes.
字符串的長(zhǎng)度大于或等于 16384 字節(jié)。
- 如果節(jié)點(diǎn)保存的是整數(shù)值，
那么這部分 header 的頭 2 位都將被設(shè)置為 1 ，
而之后跟著的 2 位則用于標(biāo)識(shí)節(jié)點(diǎn)所保存的整數(shù)的類型。
- |11000000| - 1 byte
Integer encoded as int16_t (2 bytes).
節(jié)點(diǎn)的值為 int16_t 類型的整數(shù)，長(zhǎng)度為 2 字節(jié)。 - |11010000| - 1 byte
Integer encoded as int32_t (4 bytes).
節(jié)點(diǎn)的值為 int32_t 類型的整數(shù)，長(zhǎng)度為 4 字節(jié)。 - |11100000| - 1 byte
Integer encoded as int64_t (8 bytes).
節(jié)點(diǎn)的值為 int64_t 類型的整數(shù)，長(zhǎng)度為 8 字節(jié)。 - |11110000| - 1 byte
Integer encoded as 24 bit signed (3 bytes).
節(jié)點(diǎn)的值為 24 位（3 字節(jié)）長(zhǎng)的整數(shù)。 - |11111110| - 1 byte
Integer encoded as 8 bit signed (1 byte).
節(jié)點(diǎn)的值為 8 位（1 字節(jié)）長(zhǎng)的整數(shù)。 - |1111xxxx| - (with xxxx between 0000 and 1101) immediate 4 bit integer.
Unsigned integer from 0 to 12. The encoded value is actually from
1 to 13 because 0000 and 1111 can not be used, so 1 should be
subtracted from the encoded 4 bit value to obtain the right value.
節(jié)點(diǎn)的值為介于 0 至 12 之間的無(wú)符號(hào)整數(shù)。
因?yàn)?0000 和 1111 都不能使用，所以位的實(shí)際值將是 1 至 13 。
程序在取得這 4 個(gè)位的值之后，還需要減去 1 ，才能計(jì)算出正確的值。
比如說(shuō)，如果位的值為 0001 = 1 ，那么程序返回的值將是 1 - 1 = 0 。 - |11111111| - End of ziplist.
ziplist 的結(jié)尾標(biāo)識(shí)
所有整數(shù)都表示為小端字節(jié)序。
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 示例圖
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
*/
