Redis3.0之前：ziplist/linkedlist

Redis3.0之后：quicklist

1、ziplist

1.1、什么是ziplist？

ziplist是一個經(jīng)過特殊編碼的雙向鏈表，它的設計目標就是為了提高存儲效率。

1.2、ziplist結構

• zlbytes：ziplist的長度，32位無符號整數(shù)。

• zltail：ziplist最后一個節(jié)點的偏移量，反向遍歷ziplist或者pop尾部節(jié)點的時候用來提升性能。

• zllen：ziplist的entry（節(jié)點）個數(shù)。

• entry：節(jié)點，并不是一個數(shù)組，然后里面存的值，而是一個數(shù)據(jù)結構。下面說。

• zlend：值為255，用于標記ziplist的結尾。

1.3、總結

• ziplist是為節(jié)省內(nèi)存空間而生的。

• ziplist是一個為Redis專門提供的底層數(shù)據(jù)結構之一，本身可以有序也可以無序。當作為list和hash的底層實現(xiàn)時，節(jié)點之間沒有順序；當作為zset的底層實現(xiàn)時，節(jié)點之間會按照大小順序排列。

• ziplist的弊端也很明顯了，對于較多的entry或者entry長度較大時，需要大量的連續(xù)內(nèi)存，并且節(jié)省的空間比例相對不再占優(yōu)勢，就可以考慮使用其他結構了。

2、linkedlist

就是雙向鏈表，對首尾節(jié)點的定位很快，O(1)復雜度。在首位前后插入節(jié)點也是O(1)。

3、ziplist和linkedlist怎么選擇？

Redis的list類型什么時候會使用ziplist編碼，什么時候又會使用linkedlist編碼呢？

當列表對象可以同時滿足下列兩個條件時，列表對象采用ziplist編碼，否則采用linkedlist編碼。

• 列表對象保存的所有字符串元素的長度都小于64字節(jié)；

• 列表元素保存的元素數(shù)量小于512個；

上述兩個參數(shù)可以更改配置進行自定義。

4、quicklist

5、總結

linkedlist：

1. 雙端鏈表便于在表的兩端進行push和pop操作，但是它的內(nèi)存開銷比較大；

2. 雙端鏈表每個節(jié)點上除了要保存數(shù)據(jù)之外，還要額外保存兩個指針(pre/next)；

3. 雙端鏈表的各個節(jié)點是單獨的內(nèi)存塊，地址不連續(xù)，節(jié)點多了容易產(chǎn)生內(nèi)存碎片；

ziplist：

1. ziplist由于是一整塊連續(xù)內(nèi)存，所以存儲效率很高；

2. ziplist不利于修改操作，每次數(shù)據(jù)變動都會引發(fā)一次內(nèi)存的realloc；

3. 當ziplist長度很長的時候，一次realloc可能會導致大批量的數(shù)據(jù)拷貝，進一步降低性能；

quicklist：

1. 空間換時間，之前l(fā)inkedlist需要兩個指針，浪費空間，我現(xiàn)在不用linkedlist，我都采取ziplist，然后上面封裝一層quicklistnode，底層存儲還是ziplist，只是空間上多了一層指針用于檢索。

2. 結合了雙端鏈表和壓縮列表的優(yōu)點。