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命令,請查閱 官方檔案
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/496936.html
標籤：.NET Core
下一篇：Redis 原理 - Hash