Redis資料結構——quicklist

Redis資料結構——quicklist

之前的文章我們曾總結到了Redis資料結構——連結清單和Redis資料結構——壓縮清單這兩種資料結構，他們是Redis List(清單)對象的底層實作方式。但是考慮到連結清單的附加空間相對太高，prev 和 next 指針就要占去 16 個位元組 (64bit 系統的指針是 8 個位元組)，另外每個節點的記憶體都是單獨配置設定，會加劇記憶體的碎片化，影響記憶體管理效率。是以Redis3.2版本開始對清單資料結構進行了改造，使用 quicklist 代替了 ziplist 和 linkedlist.

一、基本結構#

quicklist 實際上是 zipList 和 linkedList 的混合體，它将 linkedList 按段切分，每一段使用 zipList 來緊湊存儲，多個 zipList 之間使用雙向指針串接起來。

Copy

typedef struct quicklistNode {

struct quicklistNode *prev; //上一個node節點
struct quicklistNode *next; //下一個node
unsigned char *zl;            //儲存的資料 壓縮前ziplist 壓縮後壓縮的資料
unsigned int sz;             /* ziplist size in bytes */
unsigned int count : 16;     /* count of items in ziplist */
unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
unsigned int recompress : 1; /* was this node previous compressed? */
unsigned int attempted_compress : 1; /* node can't compress; too small */
unsigned int extra : 10; /* more bits to steal for future usage */           

} quicklistNode;

prev: 指向連結清單前一個節點的指針。

next: 指向連結清單後一個節點的指針。

zl: 資料指針。如果目前節點的資料沒有壓縮，那麼它指向一個ziplist結構；否則，它指向一個quicklistLZF結構。

sz: 表示zl指向的ziplist的總大小（包括zlbytes, zltail, zllen, zlend和各個資料項）。需要注意的是：如果ziplist被壓縮了，那麼這個sz的值仍然是壓縮前的ziplist大小。

count: 表示ziplist裡面包含的資料項個數。這個字段隻有16bit。稍後我們會一起計算一下這16bit是否夠用。

encoding: 表示ziplist是否壓縮了（以及用了哪個壓縮算法）。目前隻有兩種取值：2表示被壓縮了（而且用的是LZF壓縮算法），1表示沒有壓縮。

container: 是一個預留字段。本來設計是用來表明一個quicklist節點下面是直接存資料，還是使用ziplist存資料，或者用其它的結構來存資料（用作一個資料容器，是以叫container）。但是，在目前的實作中，這個值是一個固定的值2，表示使用ziplist作為資料容器。

recompress: 當我們使用類似lindex這樣的指令檢視了某一項本來壓縮的資料時，需要把資料暫時解壓，這時就設定recompress=1做一個标記，等有機會再把資料重新壓縮。

attempted_compress: 這個值隻對Redis的自動化測試程式有用。我們不用管它。

extra: 其它擴充字段。目前Redis的實作裡也沒用上。

typedef struct quicklistLZF {

unsigned int sz; /* LZF size in bytes*/
char compressed[];           

} quicklistLZF;

quicklistLZF結構表示一個被壓縮過的ziplist。其中：

sz: 表示壓縮後的ziplist大小。

compressed: 是個柔性數組（flexible array member），存放壓縮後的ziplist位元組數組。

typedef struct quicklist {

quicklistNode *head;
quicklistNode *tail;
unsigned long count;        /* total count of all entries in all ziplists */
unsigned long len;          /* number of quicklistNodes */
int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
unsigned int bookmark_count: QL_BM_BITS;
quicklistBookmark bookmarks[];           

} quicklist;

head: 指向頭節點（左側第一個節點）的指針。

tail: 指向尾節點（右側第一個節點）的指針。

count: 所有ziplist資料項的個數總和。

len: quicklist節點的個數。

fill: 16bit，ziplist大小設定，存放list-max-ziplist-size參數的值。

compress: 16bit，節點壓縮深度設定，存放list-compress-depth參數的值。

二、常用操作#

2.1 插入#

quicklist可以選擇在頭部或者尾部進行插入(quicklistPushHead和quicklistPushTail)，而不管是在頭部還是尾部插入資料，都包含兩種情況：

如果頭節點（或尾節點）上ziplist大小沒有超過限制（即_quicklistNodeAllowInsert傳回1），那麼新資料被直接插入到ziplist中（調用ziplistPush）。

如果頭節點（或尾節點）上ziplist太大了，那麼新建立一個quicklistNode節點（對應地也會新建立一個ziplist），然後把這個新建立的節點插入到quicklist雙向連結清單中。

也可以從任意指定的位置插入。quicklistInsertAfter和quicklistInsertBefore就是分别在指定位置後面和前面插入資料項。這種在任意指定位置插入資料的操作，要比在頭部和尾部的進行插入要複雜一些。

當插入位置所在的ziplist大小沒有超過限制時，直接插入到ziplist中就好了；

當插入位置所在的ziplist大小超過了限制，但插入的位置位于ziplist兩端，并且相鄰的quicklist連結清單節點的ziplist大小沒有超過限制，那麼就轉而插入到相鄰的那個quicklist連結清單節點的ziplist中；

當插入位置所在的ziplist大小超過了限制，但插入的位置位于ziplist兩端，并且相鄰的quicklist連結清單節點的ziplist大小也超過限制，這時需要新建立一個quicklist連結清單節點插入。

對于插入位置所在的ziplist大小超過了限制的其它情況（主要對應于在ziplist中間插入資料的情況），則需要把目前ziplist分裂為兩個節點，然後再其中一個節點上插入資料。

2.2 查找#

list的查找操作主要是對index的我們的quicklist的節點是由一個一個的ziplist構成的每個ziplist都有大小。是以我們就隻需要先根據我們每個node的個數，進而找到對應的ziplist，調用ziplist的index就能成功找到。

2.3 删除#

區間元素删除的函數是 quicklistDelRange

quicklist 在區間删除時，會先找到 start 所在的 quicklistNode，計算删除的元素是否小于要删除的 count，如果不滿足删除的個數，則會移動至下一個 quicklistNode 繼續删除，依次循環直到删除完成為止。

quicklistDelRange 函數的傳回值為 int 類型，當傳回 1 時表示成功的删除了指定區間的元素，傳回 0 時表示沒有删除任何元素。

2.4 其它#

除了上面介紹的基本操作之外還有一些其它操作，大家可以嘗試着根據連結清單和壓縮清單的資料結構來分析一些quicklist這些操作的時間複雜度。

操作 時間複雜度

quicklistCreate:建立 quicklist ？

quicklistInsertAfter：在某個元素的後面添加資料 ？

quicklistInsertBefore：在某個元素的前面添加資料 ？

quicklistReplaceAtIndex：替換某個元素 ？

quicklistDelEntry：删除單個元素 ？

quicklistDelRange：删除區間元素 ？

quicklistPushHead:頭部插入元素 ？

quicklistPushTail:尾部插入元素 ？

小結#

Redis quicklist是Redis 3.2版本以後針對連結清單和壓縮清單進行改造的一種資料結構，是 zipList 和 linkedList 的混合體，相對于連結清單它壓縮了記憶體。進一步的提高了效率。

如果你有什麼疑問，歡迎在評論區給我留言和分享，我會第一時間回報！我們一起共同學習與進步！

參考#

《Redis設計與實作》

《Redis開發與運維》

《Redis官方文檔》

-----END-----#

作者： 老於`

出處：

https://www.cnblogs.com/hunternet/p/12624691.html