Redis 壓縮列表節(jié)點(diǎn)的構(gòu)成

每個(gè)壓縮列表節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值， 其中， 字節(jié)數(shù)組可以是以下三種長(zhǎng)度的其中一種：

1. 長(zhǎng)度小于等于 63 （）字節(jié)的字節(jié)數(shù)組；
2. 長(zhǎng)度小于等于 16383 （） 字節(jié)的字節(jié)數(shù)組；
3. 長(zhǎng)度小于等于 4294967295 （）字節(jié)的字節(jié)數(shù)組；

而整數(shù)值則可以是以下六種長(zhǎng)度的其中一種：

1. 4 位長(zhǎng)，介于 0 至 12 之間的無(wú)符號(hào)整數(shù)；
2. 1 字節(jié)長(zhǎng)的有符號(hào)整數(shù)；
3. 3 字節(jié)長(zhǎng)的有符號(hào)整數(shù)；
4. int16_t 類型整數(shù)；
5. int32_t 類型整數(shù)；
6. int64_t 類型整數(shù)。

每個(gè)壓縮列表節(jié)點(diǎn)都由 previous_entry_length 、 encoding 、 content 三個(gè)部分組成， 如圖 7-4 所示。

接下來(lái)的內(nèi)容將分別介紹這三個(gè)組成部分。

previous_entry_length

節(jié)點(diǎn)的 previous_entry_length 屬性以字節(jié)為單位， 記錄了壓縮列表中前一個(gè)節(jié)點(diǎn)的長(zhǎng)度。

previous_entry_length 屬性的長(zhǎng)度可以是 1 字節(jié)或者 5 字節(jié)：

• 如果前一節(jié)點(diǎn)的長(zhǎng)度小于 254 字節(jié)， 那么 previous_entry_length 屬性的長(zhǎng)度為 1 字節(jié)： 前一節(jié)點(diǎn)的長(zhǎng)度就保存在這一個(gè)字節(jié)里面。
• 如果前一節(jié)點(diǎn)的長(zhǎng)度大于等于 254 字節(jié)， 那么 previous_entry_length 屬性的長(zhǎng)度為 5 字節(jié)： 其中屬性的第一字節(jié)會(huì)被設(shè)置為 0xFE（十進(jìn)制值 254）， 而之后的四個(gè)字節(jié)則用于保存前一節(jié)點(diǎn)的長(zhǎng)度。

圖 7-5 展示了一個(gè)包含一字節(jié)長(zhǎng) previous_entry_length 屬性的壓縮列表節(jié)點(diǎn)， 屬性的值為 0x05 ， 表示前一節(jié)點(diǎn)的長(zhǎng)度為 5 字節(jié)。

圖 7-6 展示了一個(gè)包含五字節(jié)長(zhǎng) previous_entry_length 屬性的壓縮節(jié)點(diǎn)， 屬性的值為 0xFE00002766 ， 其中值的最高位字節(jié) 0xFE 表示這是一個(gè)五字節(jié)長(zhǎng)的 previous_entry_length 屬性， 而之后的四字節(jié) 0x00002766 （十進(jìn)制值 10086 ）才是前一節(jié)點(diǎn)的實(shí)際長(zhǎng)度。

因?yàn)楣?jié)點(diǎn)的 previous_entry_length 屬性記錄了前一個(gè)節(jié)點(diǎn)的長(zhǎng)度， 所以程序可以通過(guò)指針運(yùn)算， 根據(jù)當(dāng)前節(jié)點(diǎn)的起始地址來(lái)計(jì)算出前一個(gè)節(jié)點(diǎn)的起始地址。

舉個(gè)例子， 如果我們有一個(gè)指向當(dāng)前節(jié)點(diǎn)起始地址的指針 c ， 那么我們只要用指針 c 減去當(dāng)前節(jié)點(diǎn) previous_entry_length 屬性的值， 就可以得出一個(gè)指向前一個(gè)節(jié)點(diǎn)起始地址的指針 p ， 如圖 7-7 所示。

壓縮列表的從表尾向表頭遍歷操作就是使用這一原理實(shí)現(xiàn)的： 只要我們擁有了一個(gè)指向某個(gè)節(jié)點(diǎn)起始地址的指針， 那么通過(guò)這個(gè)指針以及這個(gè)節(jié)點(diǎn)的 previous_entry_length 屬性， 程序就可以一直向前一個(gè)節(jié)點(diǎn)回溯， 最終到達(dá)壓縮列表的表頭節(jié)點(diǎn)。

圖 7-8 展示了一個(gè)從表尾節(jié)點(diǎn)向表頭節(jié)點(diǎn)進(jìn)行遍歷的完整過(guò)程：

• 首先，我們擁有指向壓縮列表表尾節(jié)點(diǎn) entry4 起始地址的指針 p1 （指向表尾節(jié)點(diǎn)的指針可以通過(guò)指向壓縮列表起始地址的指針加上zltail 屬性的值得出）；
• 通過(guò)用 p1 減去 entry4 節(jié)點(diǎn) previous_entry_length 屬性的值， 我們得到一個(gè)指向 entry4 前一節(jié)點(diǎn) entry3 起始地址的指針 p2 ；
• 通過(guò)用 p2 減去 entry3 節(jié)點(diǎn) previous_entry_length 屬性的值， 我們得到一個(gè)指向 entry3 前一節(jié)點(diǎn) entry2 起始地址的指針 p3 ；
• 通過(guò)用 p3 減去 entry2 節(jié)點(diǎn) previous_entry_length 屬性的值， 我們得到一個(gè)指向 entry2 前一節(jié)點(diǎn) entry1 起始地址的指針 p4 ， entry1為壓縮列表的表頭節(jié)點(diǎn)；
• 最終， 我們從表尾節(jié)點(diǎn)向表頭節(jié)點(diǎn)遍歷了整個(gè)列表。

encoding

節(jié)點(diǎn)的 encoding 屬性記錄了節(jié)點(diǎn)的 content 屬性所保存數(shù)據(jù)的類型以及長(zhǎng)度：

• 一字節(jié)、兩字節(jié)或者五字節(jié)長(zhǎng)， 值的最高位為 00 、 01 或者 10 的是字節(jié)數(shù)組編碼： 這種編碼表示節(jié)點(diǎn)的 content 屬性保存著字節(jié)數(shù)組， 數(shù)組的長(zhǎng)度由編碼除去最高兩位之后的其他位記錄；
• 一字節(jié)長(zhǎng)， 值的最高位以 11 開(kāi)頭的是整數(shù)編碼： 這種編碼表示節(jié)點(diǎn)的 content 屬性保存著整數(shù)值， 整數(shù)值的類型和長(zhǎng)度由編碼除去最高兩位之后的其他位記錄；

表 7-2 記錄了所有可用的字節(jié)數(shù)組編碼， 而表 7-3 則記錄了所有可用的整數(shù)編碼。 表格中的下劃線 _ 表示留空， 而 b 、 x 等變量則代表實(shí)際的二進(jìn)制數(shù)據(jù)， 為了方便閱讀， 多個(gè)字節(jié)之間用空格隔開(kāi)。

表 7-2 字節(jié)數(shù)組編碼

表 7-3 整數(shù)編碼

content

節(jié)點(diǎn)的 content 屬性負(fù)責(zé)保存節(jié)點(diǎn)的值， 節(jié)點(diǎn)值可以是一個(gè)字節(jié)數(shù)組或者整數(shù)， 值的類型和長(zhǎng)度由節(jié)點(diǎn)的 encoding 屬性決定。

圖 7-9 展示了一個(gè)保存字節(jié)數(shù)組的節(jié)點(diǎn)示例：

• 編碼的最高兩位 00 表示節(jié)點(diǎn)保存的是一個(gè)字節(jié)數(shù)組；
• 編碼的后六位 001011 記錄了字節(jié)數(shù)組的長(zhǎng)度 11 ；
• content 屬性保存著節(jié)點(diǎn)的值 "hello world" 。

圖 7-10 展示了一個(gè)保存整數(shù)值的節(jié)點(diǎn)示例：

• 編碼 11000000 表示節(jié)點(diǎn)保存的是一個(gè) int16_t 類型的整數(shù)值；
• content 屬性保存著節(jié)點(diǎn)的值 10086 。