摘要：前言在上一章中我們介紹了的一些內部原理在這一章中我們再來討論在五種數據結構中的基本使用和一些內部實現基本介紹的呢相當于中的也是雙向鏈表具有一些和同樣的特征比如插入和刪除一條很快時間復雜度為獲取頭結點和尾節點也很快時間復雜度也為隨機讀取則相對

在上一章中我們介紹了 String 的一些內部原理,在這一章中我們再來討論在五種數據結構中 List 的基本使用和一些內部實現.

Redis的List 呢相當于 Java 中的 LinkedList,也是雙向鏈表.具有一些和 LinkedList 同樣的特征,比如插入和刪除一條很快,時間復雜度為 O(1),獲取頭結點和尾節點也很快,時間復雜度也為 O(1),隨機讀取則相對較慢時間復雜度為 O(n).常用作消息隊列.

當做隊列使用時,遵循先進先出原則:

> rpush books python java golang
(integer) 3
> lpop books
"python"
> lpop books
"java"

當做棧使用時,遵循先進后出原則:

> rpush books python java golang
(integer) 3
> rpop books
"golang"
> rpop books
"java"

同時還可以通過 get(index)的方法獲取:

> rpush books python java golang
(integer) 3
> lindex books 0
"python"
> lindex books -1
"golang"

index從 0 開始,可以為負數 -1 代表倒數第一個元素

上述部分我們把 Redis 中的 List當做 Java 中的 LinkedList 操作,因為有很多相同的部分.但實際上在 Redis 中鏈表的內部實現可不是一個簡單的雙向鏈表.在數據量較少的時候它的底層存儲結構為一塊連續內存,稱之為ziplist(壓縮列表).當數據量較多的時候將會變成鏈表的結構.后來因為鏈表需要 prev 和 next 兩個指針占用內存很多,改用 ziplist+鏈表的混合結構,稱之為 quicklist(快速鏈表).在新的版本中 Redis 鏈表統一使用 quicklist來存儲.下面我們就來詳細介紹這種數據結構.

先來看看 ziplist 的數據結構:

struct ziplist{
    int32 zlbytes;            //壓縮列表占用字節數
    int32 zltail_offset;    //最后一個元素距離起始位置的偏移量,用于快速定位到最后一個節點
    int16 zllength;            //元素個數
    T[] entries;            //元素內容
    int8 zlend;                //結束位 0xFF
}

如圖所示:

有了 ztail_offset 就可以快速的定位到最后一個節點,這樣就可以倒序遍歷了.也就是說 ziplist支持雙向遍歷.

下面再來看下 entry 的內部實現:

struct entry{
    int prevlen;            //前一個 entry 的長度
    int encoding;            //元素類型編碼
    optional byte[] content;    //元素內容
}

當 ziplist 倒序遍歷的時候,就是通過這個pervlen定位到前一個元素位置的.

encoding 保存了 content 的編碼類型.

content 則是保存的元素內容,它是optional 類型表示是這個字段是可選的.當content 是很小的整數時,他會內聯到 encoding 字段的尾部.

quicklist 是 ziplist 和鏈表的混合體.下面是 quicklist和 node 的部分數據結構:

struct quicklist{
    quicklistNode* head;    //指向頭結點
    quicklistNode* tail;    //指向尾節點
    long count;                //元素總數
    int nodes;                //quicklistNode節點的個數
    int compressDepth;        //壓縮算法深度
    ...
}

為了節約空間 Redis 還會對 ziplist 使用 LZF 算法進行壓縮,可以選擇壓縮深度.我們待會在說.

如上圖所示,quicklist含有兩個 quicklistNode 代表頭結點和尾節點,其中每個head 和 tail 之間是雙向鏈表.每個quicklistNode指向一個 ziplist.

struct quicklistNode{
    quicklistNode* prev;    //前一個節點
    quicklistNode* next;    //后一個節點
    ziplist* zl;            //壓縮列表
    int32 size;                //ziplist大小
    int16 count;            //ziplist 中元素數量
    int2 encoding;            //編碼形式 存儲 ziplist 還是進行 LZF 壓縮儲存
    ...
}

在 quicklist 中每個 ziplist 默認大小是 8kb,超出這個字節就會增加一個 ziplist.這個默認大小是可配置的,由list-max-ziplist-size決定.

上面說到 ziplist 可以使用 LZF 算法壓縮,通過list-compress-depth配置.默認情況下quicklist 的壓縮深度是 0,也就是不壓縮.配置為 1 的話代表從頭/尾開始第 1 個ziplsit 進行壓縮.

下章預告,Redis 數據結構之 Hash