List 資料結構

Redis 3.2 前,使用壓縮串列zipList 或雙向鏈表linkedList
當同時滿足下面兩個條件時,使用zipList存盤資料
- list保存的每個元素長度小于64位元組
- 串列中資料個數少于512個
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記憶體布局.png

優勢: 記憶體連續,高效順序訪問,減少記憶體碎片.
劣勢: 當資料量過大時,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結構圖.png

在向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命令,請查閱官方檔案

轉載請註明出處，本文鏈接：https://www.uj5u.com/net/497008.html

標籤：.NET技术

上一篇：Redis 原理 - String

下一篇：3. Caller 服務呼叫 - dapr

Redis 原理 - List

List 資料結構

壓縮串列(zipList)

快速串列(quickList)

總結

List的常用命令