[TOC] ## 概述 Redis中的List是一個有序（按加入的時序排序）的數據結構，一般有序我們會采用數組或者是雙向鏈表，其中雙向鏈表由于有前后指針實際上會很浪費內存。3.2版本之前采用兩種數據結構作為底層實現： * 壓縮列表ziplist * 雙向鏈表linkedlist ## ziplist的結構 ziplist的數據結構及解釋如下：  `ziplist`的節點信息如下： ``` typedef struct zlentry { // prevrawlen ：前置節點的長度 // prevrawlensize ：編碼 prevrawlen 所需的字節大小,有1字節和5個字節兩種。 unsigned int prevrawlensize, prevrawlen; // len ：當前節點值的長度 // lensize ：編碼 len 所需的字節大小 unsigned int lensize, len; // 當前節點 header 的大小 // 等于 prevrawlensize + lensize unsigned int headersize; // 當前節點值所使用的編碼類型 unsigned char encoding; // 指向當前節點的指針 unsigned char *p; } zlentry; ``` 返回一個zlenrty ``` static zlentry zipEntry(unsigned char *p) { zlentry e; // e.prevrawlensize 保存著編碼前一個節點的長度所需的字節數 // e.prevrawlen 保存著前一個節點的長度 // T = O(1) ZIP_DECODE_PREVLEN(p, e.prevrawlensize, e.prevrawlen); // p + e.prevrawlensize 將指針移動到列表節點本身 // e.encoding 保存著節點值的編碼類型 // e.lensize 保存著編碼節點值長度所需的字節數 // e.len 保存著節點值的長度 // T = O(1) ZIP_DECODE_LENGTH(p + e.prevrawlensize, e.encoding, e.lensize, e.len); // 計算頭結點的字節數 e.headersize = e.prevrawlensize + e.lensize; // 記錄指針 e.p = p; return e; } ``` ## ziplist的原理 ziplist是使用連續的內存塊存儲的： * zlbytes：表示整個ziplist占用的字節數，一般用于內存重分配或者計算列表尾端 * zltail：到達列表最后一個節點的偏移量，方便直接找到尾部節點 * zllen：列表節點的數量 * entryX：列表中的各節點 * zlend：作用就是用來標記列表尾端，占用一個字節 >注意zllen用16個比特位存儲，也就是說起長度最大表示65535，所以如果長度超過這個值，只能夠通過節點遍歷來確定列表元素數量 每個節點`zlentry`是如何存儲的，完整的`zlentry`由以下幾個部分組成： * `prevrawlen`： 記錄前一個節點所占內存的字節數，方便查找上一個元素地址 * `unsigned int lensize, len`： lensize表示編碼 len 所需的字節大小，len表示當前節點值的長度 * `unsigned int headersize`： 當前節點 header 的大小，等于 prevrawlensize + lensize * `unsigned char encoding`： 當前節點值所使用的編碼類型 >ziplist數據結構中`prevrawlen`是變長編碼的，如果上一個節點長度小于254個字節，則只是用一個字節存儲prevrawlen，如果大于等于254，那么第一個字節用254標記，后面四個字節表示上一個節點長度 ## ziplist 的優缺點 * `ziplist`存儲在一段連續的內存上，所以存儲效率很高。但是，它不利于修改操作，插入和刪除操作需要頻繁的申請和釋放內存。特別是當`ziplist`長度很長的時候，一次`realloc`可能會導致大批量的數據拷貝。 * 雙向鏈表`linkedlist`便于在表的兩端進行`push`和`pop`操作，在插入節點上復雜度很低，但是它的內存開銷比較大。首先，它在每個節點上除了要保存數據之外，還要額外保存兩個指針；其次，雙向鏈表的各個節點是單獨的內存塊，地址不連續，節點多了容易產生內存碎片。 ziplist 最大的確定就是*連鎖更新問題* 因為在`ziplist`中，每個`zlentry`都存儲著前一個節點所占的字節數，而這個數值又是變長編碼的。假設存在一個壓縮列表，其包含 e1、e2、e3、e4.....，e1 節點的大小為 253 字節，那么 e2.prevrawlen 的大小為 1 字節，如果此時在 e2 與 e1 之間插入了一個新節點 e，e 編碼后的整體長度（包含 e1 的長度）為 254 字節，此時 e2.prevrawlen 就需要擴充為 5 字節；如果 e2 的整體長度變化又引起了 e3.prevrawlen 的存儲長度變化，那么 e3 也需要擴.......如此遞歸直到表尾節點或者某一個節點的 prevrawlen 本身長度可以容納前一個節點的變化。其中每一次擴充都需要進行空間再分配操作。刪除節點亦是如此，只要引起了操作節點之后的節點的 prevrawlen 的變化，都可能引起連鎖更新，引發內存 realloc。 連鎖更新在最壞情況下需要進行 N 次空間再分配，而每次空間再分配的最壞時間復雜度為 O(N)，因此連鎖更新的總體時間復雜度是 O(N^2)。 基于上述來看ziplist的缺點大于優點，所以*3.2版本之后采用了另外一個數據結構為quicklist* ## 應用場景 * 壓縮列表（ziplist）是列表鍵和哈希鍵的底層實現之一。當一個列表鍵只包含少量列表項，并且每個列表項要么就是小整數值，要么就是長度比較短的字符串，那么Redis就會使用壓縮列表來做列表鍵的底層實現。redis數據列表`list`操作，在列表中添加一個或多個值`RPUSH`: ``` redis>?RPUSH?lst?1?3?5?10086?"hello"?"world" (integer)6 redis>?OBJECT?ENCODING?lst "ziplist" ``` * 當一個哈希鍵只包含少量鍵值對，比且每個鍵值對的鍵和值要么就是小整數值，要么就是長度比較短的字符串，那么Redis就會使用壓縮列表來做哈希鍵的底層實現。 ``` redis>?HMSET?profile?"name"?"Jack"?"age"?28?"job"?"Programmer" OK redis>?OBJECT?ENCODING?profile "ziplist" ``` >哈希鍵里面包含的所有鍵和值都是小整數值或者短字符串 ps: 以上截圖來自《Redis設計與實現一書》