壓縮列表

概述

壓縮列表(ziplist)是列表鍵和哈希鍵的底層實(shí)現(xiàn)之一。當(dāng)一個(gè)列表鍵只包含少量列表項(xiàng)，并且每個(gè)列表項(xiàng)要么就是小整數(shù)值，要么就是長(zhǎng)度比較短的字符串，那么Redis就會(huì)使用壓縮列表來(lái)做列表鍵的底層實(shí)現(xiàn)。

例子

• 例如，執(zhí)行以下命令將創(chuàng)建一個(gè)壓縮列表實(shí)現(xiàn)的列表鍵，列表鍵里面包含的都是1、3、5、10086這樣的小整數(shù)值，以及"hello"、"world"這樣的短字符串。另外，當(dāng)一個(gè)哈希鍵只包含少量鍵值對(duì)，并且每個(gè)鍵值對(duì)的鍵和值要么就是小整數(shù)值，要么就是長(zhǎng)度比較短的字符串，那么Redis就會(huì)使用壓縮列表來(lái)做哈希鍵的底層實(shí)現(xiàn)。

127.0.0.1:6379> RPUSH lst 1 3 5 10086 "hello" "world"
(integer) 6
127.0.0.1:6379> OBJECT ENCODING lst
"ziplist"
127.0.0.1:6379>

• 舉個(gè)例子，執(zhí)行以下命令將創(chuàng)建一個(gè)壓縮列表實(shí)現(xiàn)的哈希鍵:
  哈希鍵里面包含的所有鍵和值都是小整數(shù)值或者短字符串。

127.0.0.1:6379> HMSET profile  "name" "VinPink" "age" 28 "job" "Programmer"
OK
127.0.0.1:6379> OBJECT ENCODING profile
"ziplist"
127.0.0.1:6379>

壓縮列表的構(gòu)成

壓縮列表是Redis為了節(jié)約內(nèi)存而開(kāi)發(fā)的，是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型(sequential)數(shù)據(jù)結(jié)構(gòu)。一個(gè)壓縮列表可以包含任意多個(gè)節(jié)點(diǎn)(entry)，每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值。

例子

• 1.列表zlbytes屬性的值為0x50(十進(jìn)制80)，表示壓縮列表的總長(zhǎng)為80字節(jié)
• 2列表zltail屬性的值為0x3c(十進(jìn)制60)，這表示如果我們有一個(gè)指向壓縮
  列表起始地址的指針P,那么只要用指針P加上偏移量60，就可以計(jì)算出表尾節(jié)點(diǎn)entry3的地址
• 3.列表zllen屬性為0x3(十進(jìn)制3)，表示壓縮列表包含三個(gè)節(jié)點(diǎn)
  
• 1.列表zlbytes屬性的值為0xd2(十進(jìn)制210),這表示壓縮列表的總長(zhǎng)為210字節(jié)
• 2.列表zltail屬性的值為0xb3(十進(jìn)制179)，這表示如果我們有一個(gè)指向壓縮列表起始地址的P，那么只要用指針P加上偏移量179，就可以計(jì)算出表尾節(jié)點(diǎn)entry5的地址
• 3.列表zllen屬性的值為0x5(十進(jìn)制5)，表示壓縮列表包含五個(gè)節(jié)點(diǎn)

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

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

• 1.長(zhǎng)度小于等于63(2 ^ 6 - 1)字節(jié)的字節(jié)數(shù)組
• 2.長(zhǎng)度小于等于16383(2 ^ 14 - 1)字節(jié)的字節(jié)數(shù)組
• 3.長(zhǎng)度小于等于4294967295(2 ^ 32 - 1)字節(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類(lèi)型整數(shù)
• 5.int32_t類(lèi)型整數(shù)
• 6.int64_t類(lèi)型整數(shù)
  每個(gè)壓縮列表節(jié)點(diǎn)都由previous_entry_length、encoding、content三個(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é):
1.如果前一節(jié)點(diǎn)的長(zhǎng)度小于254字節(jié)，那么previous_entry_length屬性的長(zhǎng)度為1字節(jié)：前一節(jié)點(diǎn)的長(zhǎng)度保存在這一個(gè)字節(jié)里面
2.如果潛移節(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)度

因?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)的起始地址

例子

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-840439.html

• 圖中展示了一個(gè)包含一字節(jié)長(zhǎng)previous_entry_length屬性的壓縮列表節(jié)點(diǎn)，屬性 的值為0x05，表示前一節(jié)點(diǎn)的長(zhǎng)度為5字節(jié)
  
• 圖中展示了一個(gè)包含五字節(jié)長(zhǎng)previous_entry_length屬性的壓縮節(jié)點(diǎn)，屬性的值為0xFE00002766,其中值的最高位0xFE表示這是一個(gè)五字節(jié)長(zhǎng)的previous_entry_length屬性，而之后的四字節(jié)0x00002766(十進(jìn)制10086)才是前一節(jié)點(diǎn)的實(shí)際長(zhǎng)度
  
• 舉個(gè)例子，如果有一個(gè)指針當(dāng)前節(jié)點(diǎn)的起始地址的指針c,那么只要用指針c減去當(dāng)前節(jié)點(diǎn)previous_entry_length屬性的值，就可以得出一個(gè)指向前一個(gè)節(jié)點(diǎn)起始地址的指針p,如圖所示
  
• 壓縮列表的從表尾向表頭遍歷操作就是使用這一原理實(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)。
  1.首先，擁有指向壓縮列表表尾節(jié)點(diǎn)entry4起始地址的指針p1(指向表尾節(jié)點(diǎn)的指針可以通過(guò)指向壓縮列表起始地址的指針加上zltai屬性的值得出)
  2.通過(guò)p1減去entry4節(jié)點(diǎn)previous_entry_length屬性的值，得到一個(gè)指向entry4前一個(gè)節(jié)點(diǎn)entry3起始地址的指針p2
  3.通過(guò)p2減去entry3節(jié)點(diǎn)previous_entry_length屬性的值，得到一個(gè)指向entry3前一節(jié)點(diǎn)entry2起始地址的指針p3
  4.通過(guò)用p3減去entry2節(jié)點(diǎn)previous_entry_length屬性的值，得到一個(gè)指向entry2前一節(jié)點(diǎn)最終，從表尾節(jié)點(diǎn)向表頭節(jié)點(diǎn)遍歷了整個(gè)列表

到了這里，關(guān)于Redis核心數(shù)據(jù)結(jié)構(gòu)之壓縮列表(一)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！