List 數據結構

1. Redis 3.2 前,使用 壓縮列表zipList 或 雙向鏈表linkedList
   當同時滿足下面兩個條件時,使用zipList存儲數據

   • list保存的每個元素長度小于64字節
   • 列表中數據個數少于512個

2. Redis 3.2 及之后的底層實現方式: quickList
   quickList 是一個基于 zipList 的雙向鏈表, quickList 的每個節點都是一個 zipList , 結合了雙向鏈表和 zipList 的優點

雙向鏈表就不多說了,就是基礎的數據結構

壓縮列表(zipList)

struct ziplist<T> {
    int32 zlbytes; // 整個壓縮列表占用字節數
    int32 zltail_offset; // 最后一個元素距離壓縮列表起始位置的偏移量，用于快速定位到最后一個節點
    int16 zllength; // 元素個數
    T[] entries; // 元素內容列表，挨個挨個緊湊存儲
    int8 zlend; // 標志壓縮列表的結束，值恒為 0xFF
}

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

• 優勢: 內存連續,高效順序訪問,減少內存碎片.
• 劣勢: 當數據量過大時,zipList就不那么好用了. 因為為了保證它存儲內容在內存中的連續性,插入的復雜度為O(N),而且如果超出zipList內存大小,還會做重新分配的內存空間,并將內容復制到新的地址. 如果數量大的話,重新分配內存和拷貝內存會消耗大量時間. 所以不適合大型字符串,也不適合存儲量多的元素..

適用場景: 少量數據, 讀遠大于寫,提供高效的讀取操作

快速列表(quickList)

是zipList和linkedList的結合體,是將linkedList按段切分,每一段用zipList來緊湊存儲

typedef struct quicklist {
    quicklistNode *head; // 指向quicklist的頭節點
    quicklistNode *tail; // 指向quicklist的尾節點
    unsigned long count; // 壓縮列表中總元素數量
    unsigned int len; //鏈表節點的個數 quicklistNode
    int fill : 16; // ziplist大小限定，由list-max-ziplist-size給定
    unsigned int compress : 16; // 節點壓縮深度設置，由list-compress-depth給定
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev; // 指向上一個ziplist節點
    struct quicklistNode *next; // 指向下一個ziplist節點
    unsigned char *zl; // 數據指針，如果沒有被壓縮，就指向ziplist結構，反之指向quicklistLZF結構
    unsigned int sz; // 指向的ziplist的字節數
    unsigned int count : 16; // 指向的ziplist的元素個數
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  // 預留字段，存放數據的方式，1--NONE，2--ziplist
    unsigned int recompress : 1;     // 解壓標記，當查看一個被壓縮的數據時，需要暫時解壓，標記此參數為1，之后再重新進行壓縮
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; // 擴展字段
} quicklistNode;

typedef struct quicklistLZF {
    unsigned int sz; // LZF壓縮后占用的字節數
    char compressed[]; // 柔性數組，存放壓縮后的ziplist字節數組
} quicklistLZF;

在向quicklist添加一個元素的時候，不會像普通的鏈表那樣，直接新建一個鏈表節點。而是會檢查插入位置的 ziplist 是否能容納該元素，如果能夠容納，那么就直接保存到ziplist，如果不能容納，才會新建一個Node節點,并保存到新的 ziplist 中。

總結

quickList 結合了 ziplist 和 雙向鏈表的優點, 相當于把 雙向鏈表 拆分為 一段段的 ziplist , 每一段的 ziplist 是連續存儲的, 可以做到高效的順序訪問,有利于減少內存碎片.

List的常用命令

• LPUSH key element ... 向列表的左側插入一個或多個元素
• RPUSH key element ... 向列表的右側插入一個或多個元素
• LPOP key 移除并返回列表左側的第一個元素
• RPOP key 移除并返回列表右側的第一個元素
• LRANGE key start stop 返回索引范圍內的所有元素
• BLPOP key timeout 移除并返回列表左側的第一個元素,沒有元素時會阻塞等待指定的時間
• BRPOP key timeout 移除并返回列表右側的第一個元素,沒有元素時會阻塞等待指定的時間
• 更多的List命令,請查閱 官方文檔