列表對象是 Redis 中 5 種基礎(chǔ)數(shù)據(jù)類型之一得封，在 Redis 3.2 版本之前，列表對象底層存儲結(jié)構(gòu)有兩種：linkedlist（雙端列表）和 ziplist（壓縮列表）拷呆，而在 Redis 3.2 版本之后疫粥，列表對象底層存儲結(jié)構(gòu)只有一種：quicklist（快速列表）梗逮，難道通過精心設(shè)計的 ziplist 最終被 Redis 拋棄了嗎？
同字符串對象一樣娄蔼，列表對象到底使用哪一種數(shù)據(jù)結(jié)構(gòu)來進(jìn)行存儲也是通過編碼來進(jìn)行區(qū)分：
編碼屬性描述object encoding命令返回值OBJ_ENCODING_LINKEDLIST使用 linkedlist 實現(xiàn)列表對象linkedlistOBJ_ENCODING_ZIPLIST使用 ziplist 實現(xiàn)列表對象ziplistOBJ_ENCODING_QUICKLIST使用 quicklist 實現(xiàn)列表對象quicklist
linkedlist
linkedlist 是一個雙向列表岁诉，每個節(jié)點都會存儲指向上一個節(jié)點和指向下一個節(jié)點的指針跋选。linkedlist 因為每個節(jié)點之間的空間是不連續(xù)的野建，所以可能會造成過多的內(nèi)存空間碎片。
linkedlist存儲結(jié)構(gòu)
鏈表中每一個節(jié)點都是一個 listNode 對象（源碼 adlist.h 內(nèi)）同眯，不過需要注意的是唯鸭，列表中的 value 其實也是一個字符串對象目溉，其他幾種數(shù)據(jù)類型其內(nèi)部最終也是會嵌套字符串對象，字符串對象也是唯一一種會被其他對象引用的基本類型：
typedefstructlistNode{
structlistNode*prev;//前一個節(jié)點
structlistNode*next;//后一個節(jié)點
void*value;//值(字符串對象)
} listNode;
然后會將其再進(jìn)行封裝成為一個 list 對象（源碼 adlist.h 內(nèi)）：
typedefstructlist{
listNode *head;//頭節(jié)點
listNode *tail;//尾節(jié)點
void*(*dup)(void*ptr);//節(jié)點值復(fù)制函數(shù)
void(*free)(void*ptr);//節(jié)點值釋放函數(shù)
int(*match)(void*ptr,void*key);//節(jié)點值對比函數(shù)
unsignedlonglen;//節(jié)點數(shù)量
}list;
Redis 中對 linkedlist 的訪問是以 NULL 值為終點的，因為 head 節(jié)點的 prev 節(jié)點為 NULL陷猫，tail 節(jié)點的 next 節(jié)點也為 NULL绣檬，所以從頭節(jié)點開始遍歷，當(dāng)發(fā)現(xiàn) tail 為 NULL 時墨缘，則可以認(rèn)為已經(jīng)到了列表末尾零抬。
當(dāng)我們設(shè)置一個列表對象時平夜，在 Redis 3.2 版本之前我們可以得到如下存儲示意圖：
ziplist
壓縮列表在前面已經(jīng)介紹過褥芒，想要詳細(xì)了解的可以點擊這里。
linkedlist 和 ziplist 的選擇
在 Redis3.2 之前献酗，linkedlist 和 ziplist 兩種編碼可以進(jìn)選擇切換坷牛，如果需要列表使用 ziplist 編碼進(jìn)行存儲京闰，則必須滿足以下兩個條件：
列表對象保存的所有字符串元素的長度都小于 64 字節(jié)甩苛。
列表對象保存的元素數(shù)量小于 512 個讯蒲。
一旦不滿足這兩個條件的任意一個肄扎，則會使用 linkedlist 編碼進(jìn)行存儲犯祠。
PS：這兩個條件可以通過參數(shù) list-max-ziplist-value 和 list-max-ziplist-entries 進(jìn)行修改。
這兩種列表能在特定的場景下發(fā)揮各自的作用搔耕，應(yīng)該來說已經(jīng)能滿足大部分需求了度迂，然后 Redis 并不滿足于此猜揪，于是一場改革引發(fā)了而姐，quicklist 橫空出世。
quicklist
在 Redis 3.2 版本之后钧萍，為了進(jìn)一步提升 Redis 的性能政鼠，列表對象統(tǒng)一采用 quicklist 來存儲列表對象公般。quicklist存儲了一個雙向列表，每個列表的節(jié)點是一個 ziplist瞬雹，所以實際上 quicklist 并不是一個新的數(shù)據(jù)結(jié)構(gòu)刽虹，它就是linkedlist 和 ziplist 的結(jié)合，然后被命名為快速列表尚镰。
quicklist 內(nèi)部存儲結(jié)構(gòu)
quicklist 中每一個節(jié)點都是一個 quicklistNode 對象哪廓，其數(shù)據(jù)結(jié)構(gòu)定義如下：
typedefstructquicklistNode{
structquicklistNode*prev;//前一個節(jié)點
structquicklistNode*next;//后一個節(jié)點
unsignedchar*zl;//當(dāng)前指向的ziplist或者quicklistLZF
unsignedintsz;//當(dāng)前ziplist占用字節(jié)
unsignedintcount :16;//ziplist中存儲的元素個數(shù)撩独，16字節(jié)(最大65535個)
unsignedintencoding :2;//是否采用了LZF壓縮算法壓縮節(jié)點 1：RAW 2:LZF
unsignedintcontainer :2;//存儲結(jié)構(gòu)账月，NONE=1, ZIPLIST=2
unsignedintrecompress :1;//當(dāng)前ziplist是否需要再次壓縮(如果前面被解壓過則為true局齿，表示需要再次被壓縮)
unsignedintattempted_compress :1;//測試用
unsignedintextra :10;//后期留用
} quicklistNode;
然后各個 quicklistNode 就構(gòu)成了一個快速列表 quicklist：
typedefstructquicklist{
quicklistNode *head;//列表頭節(jié)點
quicklistNode *tail;//列表尾節(jié)點
unsignedlongcount;//ziplist中一共存儲了多少元素抓歼，即:每一個quicklistNode內(nèi)的count相加
unsignedlonglen;//雙向鏈表的長度，即quicklistNode的數(shù)量
intfill :16;//填充因子
unsignedintcompress :16;//壓縮深度 0-不壓縮
} quicklist;
根據(jù)這兩個結(jié)構(gòu)萄喳，我們可以得到 Redis 3.2 版本之后的列表對象的一個存儲結(jié)構(gòu)示意圖：
quicklist 的 compress 屬性
compress 是用來表示壓縮深度他巨，ziplist 除了內(nèi)存空間是連續(xù)之外染突，還可以采用特定的 LZF 壓縮算法來將節(jié)點進(jìn)行壓縮存儲辈灼，從而更進(jìn)一步的節(jié)省空間份企，壓縮深度可以通過參數(shù) list-compress-depth 控制：
0：不壓縮(默認(rèn)值)
1：首尾第1個元素不壓縮
2：首位前2個元素不壓縮
3：首尾前3個元素不壓縮
以此類推
注意：之所以采取這種壓縮兩端節(jié)點的方式是因為很多場景都是兩端的元素訪問率最高的，而中間元素訪問率相對較低巡莹，所以在實際使用時司志，我們可以根據(jù)自己的實際情況選擇是否進(jìn)行壓縮，以及具體的壓縮深度降宅。
quicklistNode 的 zl 指針
zl 指針默認(rèn)指向了 ziplist俐芯，上面提到 quicklistNode 中有一個 sz 屬性記錄了當(dāng)前 ziplist 占用的字節(jié)，不過這僅僅限于當(dāng)前節(jié)點沒有被壓縮（通過LZF 壓縮算法）的情況钉鸯，如果當(dāng)前節(jié)點被壓縮了吧史，那么被壓縮節(jié)點的 zl 指針會指向另一個對象 quicklistLZF，而不會直接指向 ziplist。quicklistLZF 是一個 4+N 字節(jié)的結(jié)構(gòu)：
typedefstructquicklistLZF{
unsignedintsz;// LZF大小吨述，占用4字節(jié)
charcompressed[];//被壓縮的內(nèi)容，占用N字節(jié)
} quicklistLZF;
quicklist 對比原始兩種編碼的改進(jìn)
quicklist 同樣采用了 linkedlist 的雙端列表特性钞脂，然后 quicklist 中的每個節(jié)點又是一個 ziplist揣云，所以quicklist 就是綜合平衡考慮了 linkedlist 容易產(chǎn)生空間碎片的問題和 ziplist 的讀寫性能兩個維度而設(shè)計出來的一種數(shù)據(jù)結(jié)構(gòu)。使用 quicklist 需要注意以下 2 點：
如果 ziplist 中的 entry 個數(shù)過少冰啃，最極端情況就是只有 1 個 entry 的壓縮列表邓夕，那么此時 quicklist 就相當(dāng)于退化成了一個普通的 linkedlist。
如果 ziplist 中的 entry 過多阎毅，那么也會導(dǎo)致一次性需要申請的內(nèi)存空間過大（ziplist 空間是連續(xù)的）焚刚，而且因為 ziplist 本身的就是以時間換空間，所以會過多 entry 也會影響到列表對象的讀寫性能扇调。
ziplist 中的 entry 個數(shù)可以通過參數(shù) list-max-ziplist-size 來控制：
list-max-ziplist-size1
注意：這個參數(shù)可以配置正數(shù)也可以配置負(fù)數(shù)矿咕。正數(shù)表示限制每個節(jié)點中的 entry 數(shù)量，如果是負(fù)數(shù)則只能為 -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 之后）。
lpushx key value1 value2：將一個或者多個 value 插入到列表 key 的頭部熬芜，key 不存在則不做任何處理（value2 在value1 之后）莲镣。
lpop key：移除并返回 key 值的列表頭元素。
rpush key value1 value2：將一個或者多個 value 插入到列表 key 的尾部涎拉，key 不存在則創(chuàng)建 key（value2 在value1 之后）剥悟。
rpushx key value1 vaue2：將一個或者多個 value 插入到列表 key 的尾部，key 不存在則不做任何處理（value2 在value1 之后）曼库。
rpop key：移除并返回列表 key 的尾元素区岗。
llen key：返回列表 key 的長度。
lindex key index：返回列表 key 中下標(biāo)為 index 的元素毁枯。index 為正數(shù)（從 0 開始）表示從隊頭開始算慈缔，index 為負(fù)數(shù)（從-1開始）則表示從隊尾開始算。
lrange key start stop：返回列表 key 中下標(biāo) [start,end] 之間的元素种玛。
lset key index value：將 value 設(shè)置到列表 key 中指定 index 位置藐鹤，key 不存在或者 index 超出范圍則會報錯。
ltrim key start end：截取列表中 [start,end] 之間的元素赂韵，并替換原列表保存娱节。
了解了操作列表對象的常用命令，我們就可以來驗證下前面提到的列表對象的類型和編碼了祭示，在測試之前為了防止其他 key 值的干擾肄满，我們先執(zhí)行 flushall 命令清空 Redis 數(shù)據(jù)庫。
接下來依次輸入命令：
lpush name zhangsan
type name
object encoding name
可以看到，通過 type 命令輸出的是 list稠歉，說明當(dāng)前 name 存的是一個列表對象掰担，并且編碼是 quicklist（示例中用的是 5.0.5 版本）。
本文主要介紹了 Redis 中 5 種常用數(shù)據(jù)類型中的 列表對象怒炸，并介紹了底層的存儲結(jié)構(gòu) quicklist带饱，并分別對舊版本的兩種底層數(shù)據(jù) linkedlist 和 ziplist 進(jìn)行了分析對比得出了為什么 Redis 最終要采用 quicklist 來存儲列表對象。
