Redis系列（六）：數據結構QuickList（快速列表）源碼解析
1.介紹
Redis在3.2版本之前List的底層編碼是ZipList和LinkedList實現的
在3.2版本之後，重新引入了QuickList的數據結構，列表的底層都是QuickList實現
當List對象中元素的長度比較小或者數量比較少的時候，採用ZipList來存儲
當List對象中元素的長度比較大或者數量比較多的時候，採用LinkList來存儲
這兩種存儲方式的優缺點
LinkedList便於在表的兩端進行Push和Pop操作，在插入節點複雜度很低，但是它的記憶體開銷很大，首先，它在每個節點上除了要保存數據之外，還要額外保存兩個指針。
其次；雙向鏈表的各個節點時單獨的記憶體塊，地址不連續，節點多了容易產生記憶體碎片
ZipList存儲在一段連續的記憶體上，所以存儲效率很高，但是它不利於修改操作，插入和刪除操作需要頻繁的申請釋放記憶體。
特別是當ZipList長度很長的時候，一次Realloc可能導致大批量的數據拷貝
QuickList可以看作一個雙向列表，但是列表的每個節點都是一個ziplist，
其實就是linkedlist和ziplist的結合。quicklist中的每個節點ziplist都能夠存儲多個數據元素。
2.示意圖
3.源碼實現
typedef struct quicklist { quicklistNode *head; // 指向quicklist的頭部 quicklistNode *tail; // 指向quicklist的尾部 unsigned long count; // 列表中所有數據項的個數總和 unsigned int len; // quicklist節點的個數，即ziplist的個數 int fill : 16; // ziplist大小限定，由list-max-ziplist-size給定 unsigned int compress : 16; // 節點壓縮深度設置，由list-compress-depth給定 } quicklist;
count用來統計所有數據項的個數總和，len用來統計quicklist的節點個數， 因為每個節點ziplist都能存儲多個數據項，所以有了這兩個統計值。
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; // 編碼方式，1--ziplist，2--quicklistLZF unsigned int container : 2; // 預留欄位，存放數據的方式，1--NONE，2--ziplist unsigned int recompress : 1; // 解壓標記，當查看一個被壓縮的數據時，需要暫時解壓，標記此參數為1，之後再重新進行壓縮 unsigned int attempted_compress : 1; // 測試相關 unsigned int extra : 10; // 擴展欄位，暫時沒用 } quicklistNode;
QuickList的迭代器結構,指向迭代器節點元素
// quicklist的迭代器結構 typedef struct quicklistIter { const quicklist *quicklist; // 指向所在quicklist的指針 quicklistNode *current; // 指向當前節點的指針 unsigned char *zi; // 指向當前節點的ziplist long offset; // 當前ziplist中的偏移地址 int direction; // 迭代器的方向 } quicklistIter; // 表示quicklist節點中ziplist里的一個節點結構 typedef struct quicklistEntry { const quicklist *quicklist; // 指向所在quicklist的指針 quicklistNode *node; // 指向當前節點的指針 unsigned char *zi; // 指向當前節點的ziplist unsigned char *value; // 當前指向的ziplist中的節點的字元串值 long long longval; // 當前指向的ziplist中的節點的整型值 unsigned int sz; // 當前指向的ziplist中的節點的位元組大小 int offset; // 當前指向的ziplist中的節點相對於ziplist的偏移量 } quicklistEntry;
創建QuickList
fill:
-5: 每個quicklist節點上的ziplist大小不能超過64 Kb。（註：1kb => 1024 bytes）
-4: 每個quicklist節點上的ziplist大小不能超過32 Kb。
-3: 每個quicklist節點上的ziplist大小不能超過16 Kb。
-2: 每個quicklist節點上的ziplist大小不能超過8 Kb。（-2是Redis給出的默認值）
-1: 每個quicklist節點上的ziplist大小不能超過4 Kb。
compress:
0 特殊值，表示不壓縮
1 表示quicklist兩端各有一個節點不壓縮，中間的節點壓縮
2 表示quicklist兩端各有兩個節點不壓縮，中間的節點壓縮
3 表示quicklist兩端各有三個節點不壓縮，中間的節點壓縮
quicklist *quicklistCreate(void) { struct quicklist *quicklist; // 聲明指針 quicklist = zmalloc(sizeof(*quicklist)); // 分配記憶體 quicklist->head = quicklist->tail = NULL; // 設定頭尾指針 quicklist->len = 0; // 設定長度 quicklist->count = 0; // 設定數據項總和 quicklist->compress = 0; // 設定壓縮深度 quicklist->fill = -2; // 設定ziplist大小限定 return quicklist; }
創建QuickListNode
REDIS_STATIC quicklistNode *quicklistCreateNode(void) { quicklistNode *node; node = zmalloc(sizeof(*node)); // 申請記憶體 node->zl = NULL; // 初始化指向ziplist的指針 node->count = 0; // 初始化數據項個數 node->sz = 0; // 初始化ziplist大小 node->next = node->prev = NULL; // 初始化prev和next指針 node->encoding = QUICKLIST_NODE_ENCODING_RAW; // 初始化節點編碼方式 node->container = QUICKLIST_NODE_CONTAINER_ZIPLIST; // 初始化存放數據的方式 node->recompress = 0; // 初始化再壓縮標記 return node; }
