[[360732]]

 本文轉(zhuǎn)載自微信公眾號(hào)「Java極客技術(shù)」，作者鴨血粉絲 。轉(zhuǎn)載本文請(qǐng)聯(lián)系Java極客技術(shù)公眾號(hào)。   

Hello，大家好，我是阿粉~

上次我們分享 Redis 字符串的底層原理，今天我們?cè)賮砜聪?Redis List 列表的底層原理。

Redis List 命令

Redis List 列表支持的相關(guān)指令比較多，比如單個(gè)元素增加、刪除操作，也支持多個(gè)元素范圍操作。

Redis List 列表支持列表表頭元素插入/彈出(「LPUSH/LPOP」)，也支持表尾元素插入/彈出(「RPUSH/RPOP」)。

另外 Redis List 列表還支持根據(jù)下標(biāo)(「LINDEX」 )獲取元素，也支持根據(jù)根據(jù)下標(biāo)覆蓋相應(yīng)的元素(「LSET」 )。

除此之外，Redis List 列表還支持的范圍操作，比如獲取指定范圍內(nèi)全部元素(「LRANGE」 )，移除指定范圍內(nèi)的全部元素(「LTRIM」 )。

了解完的 Redis 相關(guān)指令，我們來看下 Redis List 列表底層實(shí)現(xiàn)方式，使用兩種數(shù)據(jù)結(jié)構(gòu)：

• 壓縮列表(ziplist)
• 雙向列表(linkedlist)

 

ps:本篇文章基于 Redis 3.2 開始進(jìn)行講解

雙向列表(linkedlist)

上面我們知道了List 列表支持表頭/表尾元素的插入/彈出，這類操作使用鏈表那就非常高效，時(shí)間復(fù)雜度為 O(1)。

Redis 雙向列表(linkedlist) 由兩個(gè)結(jié)構(gòu)構(gòu)成：

• list
• listnode

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

 

list 結(jié)構(gòu)體中保存了表頭節(jié)點(diǎn)，表尾節(jié)點(diǎn)以及鏈表包含的節(jié)點(diǎn)的數(shù)量，正因?yàn)槿绱瞬僮鞅眍^/表尾元素的插入/彈出，鏈表長(zhǎng)度的計(jì)算將會(huì)非常高效，時(shí)間復(fù)雜度為「O(1)」。

listnode結(jié)構(gòu)體中除了保存節(jié)點(diǎn)的值以外，還會(huì)保存前后節(jié)點(diǎn)的指針，這樣如果需要獲取某個(gè)節(jié)點(diǎn)的前置節(jié)點(diǎn)與后置節(jié)點(diǎn)也會(huì)非常高效，時(shí)間復(fù)雜度為「O(1)」。

另外如果需要指定位置插入/刪除元素，那么只需要變動(dòng)當(dāng)前位置節(jié)點(diǎn)前后指針即可，這個(gè)插入/刪除操作復(fù)雜度為「O(1)」。

不過需要注意了，插入/刪除動(dòng)作前提我們需要找到這個(gè)指定位置，這個(gè)查找動(dòng)作我們只能遍歷鏈表，復(fù)雜度為「O(N)」，所以插入/刪除的復(fù)雜度為「O(N)」。

雙向列表(linkedlist)除了用作在列表鍵以外，還廣泛用于發(fā)布/訂閱，慢查詢等內(nèi)部操作。

既然雙向列表(linkedlist)可以滿足列表鍵的操作，那為什么 Redis 列表還采用其他的數(shù)據(jù)結(jié)構(gòu)?

其實(shí)主要是因?yàn)閮?nèi)存占用問題，雙向鏈表由于使用兩個(gè)結(jié)構(gòu)體，而這兩個(gè)結(jié)構(gòu)體都需要保存一些必要信息，這必然將會(huì)占用部分內(nèi)存。

而當(dāng)元素很少的時(shí)候，如果直接使用雙向鏈表，內(nèi)存還是比較浪費(fèi)的。所以 Redis 引入壓縮列表。

壓縮列表

壓縮列表是 Redis 為了節(jié)約內(nèi)存而開發(fā)，它由一系列的特殊編碼的的「連續(xù)內(nèi)存塊」組成的順序型數(shù)據(jù)結(jié)構(gòu)，整體結(jié)構(gòu)如下：

 

從上面結(jié)構(gòu)可以看出來，壓縮列表實(shí)際上類似與我們使用的數(shù)組，數(shù)組中每一個(gè)元素保存一個(gè)數(shù)據(jù)。

不過與數(shù)組不同的是，壓縮列表的表頭存在三個(gè)字段

• zlbytes 代表列表長(zhǎng)度
• zltail代表列表尾節(jié)點(diǎn)距離壓縮列表起始地址的偏移量
• zllen代表壓縮列表的節(jié)點(diǎn)的個(gè)數(shù)

另外壓縮列表的表尾還有一個(gè)字段，zlend里面保存一個(gè)特殊的值， OXFE，用于標(biāo)記壓縮列表的末端。

一個(gè)壓縮列表可以由多個(gè)節(jié)點(diǎn)構(gòu)成，每個(gè)節(jié)點(diǎn)可以保存整數(shù)值或字節(jié)數(shù)組，結(jié)構(gòu)如下：

 

使用壓縮列表，如果查找定位表頭元素，我們只需要使用壓縮列表起始地址加上表頭三個(gè)字段長(zhǎng)度就可以直接點(diǎn)位，查找非?？?，復(fù)雜度是 O(1)。

而壓縮列表的最后一個(gè)元素，查找起來也非常輕松，我們使用壓縮列表起始地址加上zltail包含的長(zhǎng)度就可以直接點(diǎn)位，查找也非?？?，復(fù)雜度是 O(1)。

至于列表中的其他元素，就沒有這么好運(yùn)了，我們只能從第一個(gè)元素或者最后一個(gè)元素，遍歷列表查找，此時(shí)的復(fù)雜度就是 O(N) 了。

另外壓縮列表的新增、刪除元素，都將會(huì)導(dǎo)致重新分配內(nèi)存，效率不高，平均復(fù)雜度為 O(N)，最壞福復(fù)雜度為 O(N^2)。

編碼轉(zhuǎn)換

當(dāng)我們創(chuàng)建一個(gè) Redis 列表鍵，如果同時(shí)滿足以下兩個(gè)條件，列表對(duì)象將會(huì)使用壓縮列表作為底層數(shù)據(jù)結(jié)構(gòu)

列表對(duì)象保存的所有字符串元素的長(zhǎng)度都小于 64 字節(jié)

列表對(duì)象中保存的元素?cái)?shù)量小于 512 個(gè)

如果不能同時(shí)滿足這兩個(gè)條件，那么默認(rèn)將會(huì)使用雙向列表作為底層數(shù)據(jù)結(jié)構(gòu)。

小結(jié)

Redis 列表底層使用兩種數(shù)據(jù)結(jié)構(gòu)，壓縮列表與雙向鏈表。

壓縮列表由于使用了連續(xù)內(nèi)存塊，內(nèi)存占用少，并且內(nèi)存利用率高，但是新增、刪除由于涉及重新分配內(nèi)存，效率不高。

雙向列表呢，新增、刪除元素非常方便，但是由于每個(gè)節(jié)點(diǎn)都是獨(dú)立的內(nèi)存快，內(nèi)存占用比較高，且內(nèi)存碎片化嚴(yán)重。

這兩種數(shù)據(jù)結(jié)構(gòu)在表頭/表尾插入與刪除元素，都十分高效。但是其他操作，可能就效率較低。

所以我們使用 Redis 列表，一定要因地制宜，可以將其當(dāng)做 FIFO 隊(duì)列，這樣僅使用 POP/PUSH ，效率將會(huì)很高。

 

參考資料

Redis 設(shè)計(jì)與實(shí)現(xiàn)