List 數據結構 Redis 3.2 前,使用 壓縮列表zipList 或 雙向鏈表linkedList 當同時滿足下麵兩個條件時,使用zipList存儲數據 list保存的每個元素長度小於64位元組 列表中數據個數少於512個 Redis 3.2 及之後的底層實現方式: quickList qui ...
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就不那麼好用了. 因為為了保證它存儲內容在記憶體中的連續性,插入的複雜度為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命令,請查閱 官方文檔
