列表對象是 Redis 中 5 種基礎數據類型之一，在 Redis 3.2 版本之前，列表對象底層存儲結構有兩種：linkedlist（雙端列表）和 ziplist（壓縮列表），而在 Redis 3.2 版本之后，列表對象底層存儲結構只有一種：quicklist（快速列表），難道通過精心設計的 ziplist 最終被 Redis 拋棄了嗎？
同字符串對象一樣，列表對象到底使用哪一種數據結構來進行存儲也是通過編碼來進行區(qū)分：
| 編碼屬性 | 描述 | object encoding命令返回值 |
|---|---|---|
| OBJ_ENCODING_LINKEDLIST | 使用 linkedlist 實現列表對象 |
linkedlist |
| OBJ_ENCODING_ZIPLIST | 使用 ziplist 實現列表對象 |
ziplist |
| OBJ_ENCODING_QUICKLIST | 使用 quicklist 實現列表對象 |
quicklist |
linkedlist 是一個雙向列表，每個節(jié)點都會存儲指向上一個節(jié)點和指向下一個節(jié)點的指針。linkedlist 因為每個節(jié)點之間的空間是不連續(xù)的，所以可能會造成過多的內存空間碎片。
鏈表中每一個節(jié)點都是一個 listNode 對象（源碼 adlist.h 內），不過需要注意的是，列表中的 value 其實也是一個字符串對象，其他幾種數據類型其內部最終也是會嵌套字符串對象，字符串對象也是唯一一種會被其他對象引用的基本類型：
typedef struct listNode {
struct listNode *prev;//前一個節(jié)點
struct listNode *next;//后一個節(jié)點
void *value;//值(字符串對象)
} listNode;
然后會將其再進行封裝成為一個 list 對象（源碼 adlist.h 內）：
typedef struct list {
listNode *head;//頭節(jié)點
listNode *tail;//尾節(jié)點
void *(*dup)(void *ptr);//節(jié)點值復制函數
void (*free)(void *ptr);//節(jié)點值釋放函數
int (*match)(void *ptr, void *key);//節(jié)點值對比函數
unsigned long len;//節(jié)點數量
} list;
Redis 中對 linkedlist 的訪問是以 NULL 值為終點的，因為 head 節(jié)點的 prev 節(jié)點為 NULL，tail 節(jié)點的 next 節(jié)點也為 NULL，所以從頭節(jié)點開始遍歷，當發(fā)現 tail 為 NULL 時，則可以認為已經到了列表末尾。
當我們設置一個列表對象時，在 Redis 3.2 版本之前我們可以得到如下存儲示意圖：
壓縮列表在前面已經介紹過，想要詳細了解的可以點擊這里。
在 Redis3.2 之前，linkedlist 和 ziplist 兩種編碼可以進選擇切換，如果需要列表使用 ziplist 編碼進行存儲，則必須滿足以下兩個條件：
列表對象保存的所有字符串元素的長度都小于 64 字節(jié)。列表對象保存的元素數量小于 512 個。
一旦不滿足這兩個條件的任意一個，則會使用 linkedlist 編碼進行存儲。
PS：這兩個條件可以通過參數 list-max-ziplist-value 和 list-max-ziplist-entries 進行修改。
這兩種列表能在特定的場景下發(fā)揮各自的作用，應該來說已經能滿足大部分需求了，然后 Redis 并不滿足于此，于是一場改革引發(fā)了，quicklist 橫空出世。
在 Redis 3.2 版本之后，為了進一步提升 Redis 的性能，列表對象統一采用 quicklist 來存儲列表對象。quicklist存儲了一個雙向列表，每個列表的節(jié)點是一個 ziplist，所以實際上 quicklist 并不是一個新的數據結構，它就是linkedlist 和 ziplist 的結合，然后被命名為快速列表。
quicklist 中每一個節(jié)點都是一個 quicklistNode 對象，其數據結構定義如下：
typedef struct quicklistNode {
struct quicklistNode *prev;//前一個節(jié)點
struct quicklistNode *next;//后一個節(jié)點
unsigned char *zl;//當前指向的ziplist或者quicklistLZF
unsigned int sz;//當前ziplist占用字節(jié)
unsigned int count : 16;//ziplist中存儲的元素個數，16字節(jié)(最大65535個)
unsigned int encoding : 2; //是否采用了LZF壓縮算法壓縮節(jié)點 1：RAW 2:LZF
unsigned int container : 2; //存儲結構，NONE=1, ZIPLIST=2
unsigned int recompress : 1; //當前ziplist是否需要再次壓縮(如果前面被解壓過則為true，表示需要再次被壓縮)
unsigned int attempted_compress : 1;//測試用
unsigned int extra : 10; //后期留用
} quicklistNode;
然后各個 quicklistNode 就構成了一個快速列表 quicklist：
typedef struct quicklist {
quicklistNode *head;//列表頭節(jié)點
quicklistNode *tail;//列表尾節(jié)點
unsigned long count;//ziplist中一共存儲了多少元素，即:每一個quicklistNode內的count相加
unsigned long len; //雙向鏈表的長度，即quicklistNode的數量
int fill : 16;//填充因子
unsigned int compress : 16;//壓縮深度 0-不壓縮
} quicklist;
根據這兩個結構，我們可以得到 Redis 3.2 版本之后的列表對象的一個存儲結構示意圖：
compress 是用來表示壓縮深度，ziplist 除了內存空間是連續(xù)之外，還可以采用特定的 LZF 壓縮算法來將節(jié)點進行壓縮存儲，從而更進一步的節(jié)省空間，壓縮深度可以通過參數 list-compress-depth 控制：
0：不壓縮(默認值)
1：首尾第1個元素不壓縮
2：首位前2個元素不壓縮
3：首尾前3個元素不壓縮以此類推
注意：之所以采取這種壓縮兩端節(jié)點的方式是因為很多場景都是兩端的元素訪問率最高的，而中間元素訪問率相對較低，所以在實際使用時，我們可以根據自己的實際情況選擇是否進行壓縮，以及具體的壓縮深度。
zl 指針默認指向了 ziplist，上面提到 quicklistNode 中有一個 sz 屬性記錄了當前 ziplist 占用的字節(jié)，不過這僅僅限于當前節(jié)點沒有被壓縮（通過LZF 壓縮算法）的情況，如果當前節(jié)點被壓縮了，那么被壓縮節(jié)點的 zl 指針會指向另一個對象 quicklistLZF，而不會直接指向 ziplist。quicklistLZF 是一個 4+N 字節(jié)的結構：
typedef struct quicklistLZF {
unsigned int sz;// LZF大小，占用4字節(jié)
char compressed[];//被壓縮的內容，占用N字節(jié)
} quicklistLZF;
quicklist 同樣采用了 linkedlist 的雙端列表特性，然后 quicklist 中的每個節(jié)點又是一個 ziplist，所以quicklist 就是綜合平衡考慮了 linkedlist 容易產生空間碎片的問題和 ziplist 的讀寫性能兩個維度而設計出來的一種數據結構。使用 quicklist 需要注意以下 2 點：
如果 ziplist 中的 entry 個數過少，最極端情況就是只有 1 個 entry 的壓縮列表，那么此時 quicklist 就相當于退化成了一個普通的 linkedlist。如果 ziplist 中的 entry 過多，那么也會導致一次性需要申請的內存空間過大（ziplist 空間是連續(xù)的），而且因為 ziplist 本身的就是以時間換空間，所以會過多 entry 也會影響到列表對象的讀寫性能。
ziplist 中的 entry 個數可以通過參數 list-max-ziplist-size 來控制：
list-max-ziplist-size 1
注意：這個參數可以配置正數也可以配置負數。正數表示限制每個節(jié)點中的 entry 數量，如果是負數則只能為 -1~-5，其代表的含義如下：
-1：每個 ziplist 最多只能為 4KB
-2：每個 ziplist 最多只能為 8KB
-3：每個 ziplist 最多只能為 16KB
-4：每個 ziplist 最多只能為 32KB
-5：每個 ziplist 最多只能為 64KB
lpush key value1 value2：將一個或者多個 value 插入到列表 key 的頭部，key 不存在則創(chuàng)建 key（value2 在value1 之后）。
value 插入到列表 key 的頭部，key 不存在則不做任何處理（value2 在value1 之后）。key 值的列表頭元素。value 插入到列表 key 的尾部，key 不存在則創(chuàng)建 key（value2 在value1 之后）。value 插入到列表 key 的尾部，key 不存在則不做任何處理（value2 在value1 之后）。key 的尾元素。key 的長度。key 中下標為 index 的元素。index 為正數（從 0 開始）表示從隊頭開始算，index 為負數（從-1開始）則表示從隊尾開始算。key 中下標 [start,end] 之間的元素。value 設置到列表 key 中指定 index 位置，key 不存在或者 index 超出范圍則會報錯。 ltrim key start end：截取列表中 [start,end] 之間的元素，并替換原列表保存。了解了操作列表對象的常用命令，我們就可以來驗證下前面提到的列表對象的類型和編碼了，在測試之前為了防止其他 key 值的干擾，我們先執(zhí)行 flushall 命令清空 Redis 數據庫。
接下來依次輸入命令：
lpush name zhangsan type name object encoding name
可以看到，通過 type 命令輸出的是 list，說明當前 name 存的是一個列表對象，并且編碼是 quicklist（示例中用的是 5.0.5 版本）。
本文主要介紹了 Redis 中 5 種常用數據類型中的 列表對象，并介紹了底層的存儲結構 quicklist，并分別對舊版本的兩種底層數據 linkedlist 和 ziplist 進行了分析對比得出了為什么 Redis 最終要采用 quicklist 來存儲列表對象。
到此這篇關于Redis都做了哪些加快速度的設計的文章就介紹到這了,更多相關Redis 加快速度的設計內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
