[[360732]]

 本文轉載自微信公眾號「Java極客技術」，作者鴨血粉絲 。轉載本文請聯系Java極客技術公眾號。   

Hello，大家好，我是阿粉~

上次我們分享 Redis 字符串的底層原理，今天我們再來看下 Redis List 列表的底層原理。

Redis List 命令

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

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

另外 Redis List 列表還支持根據下標(「LINDEX」 )獲取元素，也支持根據根據下標覆蓋相應的元素(「LSET」 )。

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

了解完的 Redis 相關指令，我們來看下 Redis List 列表底層實現方式，使用兩種數據結構：

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

 

ps:本篇文章基于 Redis 3.2 開始進行講解

雙向列表(linkedlist)

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

Redis 雙向列表(linkedlist) 由兩個結構構成：

• list
• listnode

結構如下：

 

list 結構體中保存了表頭節點，表尾節點以及鏈表包含的節點的數量，正因為如此操作表頭/表尾元素的插入/彈出，鏈表長度的計算將會非常高效，時間復雜度為「O(1)」。

listnode結構體中除了保存節點的值以外，還會保存前后節點的指針，這樣如果需要獲取某個節點的前置節點與后置節點也會非常高效，時間復雜度為「O(1)」。

另外如果需要指定位置插入/刪除元素，那么只需要變動當前位置節點前后指針即可，這個插入/刪除操作復雜度為「O(1)」。

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

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

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

其實主要是因為內存占用問題，雙向鏈表由于使用兩個結構體，而這兩個結構體都需要保存一些必要信息，這必然將會占用部分內存。

而當元素很少的時候，如果直接使用雙向鏈表，內存還是比較浪費的。所以 Redis 引入壓縮列表。

壓縮列表

壓縮列表是 Redis 為了節約內存而開發，它由一系列的特殊編碼的的「連續內存塊」組成的順序型數據結構，整體結構如下：

 

從上面結構可以看出來，壓縮列表實際上類似與我們使用的數組，數組中每一個元素保存一個數據。

不過與數組不同的是，壓縮列表的表頭存在三個字段

• zlbytes 代表列表長度
• zltail代表列表尾節點距離壓縮列表起始地址的偏移量
• zllen代表壓縮列表的節點的個數

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

一個壓縮列表可以由多個節點構成，每個節點可以保存整數值或字節數組，結構如下：

 

使用壓縮列表，如果查找定位表頭元素，我們只需要使用壓縮列表起始地址加上表頭三個字段長度就可以直接點位，查找非常快，復雜度是 O(1)。

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

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

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

編碼轉換

當我們創建一個 Redis 列表鍵，如果同時滿足以下兩個條件，列表對象將會使用壓縮列表作為底層數據結構

列表對象保存的所有字符串元素的長度都小于 64 字節

列表對象中保存的元素數量小于 512 個

如果不能同時滿足這兩個條件，那么默認將會使用雙向列表作為底層數據結構。

小結

Redis 列表底層使用兩種數據結構，壓縮列表與雙向鏈表。

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

雙向列表呢，新增、刪除元素非常方便，但是由于每個節點都是獨立的內存快，內存占用比較高，且內存碎片化嚴重。

這兩種數據結構在表頭/表尾插入與刪除元素，都十分高效。但是其他操作，可能就效率較低。

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

 

參考資料

Redis 設計與實現