摘要：記錄壓縮列表總共占用的字節數，在對壓縮列表進行內存重分配時使用個字節。為十六進制值，標記一個壓縮列表的末尾具體的數據存放在中。占用或字節表示當前存儲數據的類型與數據的長度。在學習的同時，如果沒有經過自己的思考，收效甚微。

baiyan
全部視頻：https://segmentfault.com/a/11...

乍一看標題，我們可能還不知道ziplist是何許人也。但是如果我說list、hash、zset這幾種數據結構，大家就很熟悉了。而ziplist就是這幾種數據結構的底層實現之一：

list：3.2.x之前為（ziplist + linkedlist）之后為quicklist
hash：數據量小的時候使用ziplist，量大時使用hashtable（dict）
zset：數據量小的時候使用ziplist，量大時使用skiplist

我們可以看到，ziplist總是在一種列表、哈希、有序集合這幾種結構在存儲的數據量小的時會使用。隨著數據量的增長，會轉換到相對應較復雜的類型。我們可以猜測，ziplist是一種輕巧、簡單、且占用內存小的數據結構。它能夠解決在redis數據量小時的存儲問題。

在redis的設計思想中，大多數情況下，都是以時間換空間。由于redis基于內存，且內存資源是相當寶貴的，所以節省空間的“性價比”相對于節省時間，顯然更高一些。在學習數據結構與算法的過程中，我們常常將數組和鏈表放在一起比較。由于數組使用一塊連續的內存，而鏈表分為指針域和數據域，數組在空間利用率上明顯要高于鏈表。參考以上設計思想，如果讓我們自己去設計ziplist的結構，我們如何思考呢？

需要一塊連續的內存空間去存儲真正的數據
需要一些額外的信息字段去記錄它的長度、結束標志、還有數據的總量等輔助信息

在ziplist中，是按照如下結構進行存儲的，是否符合你的預期呢？

每個字段的含義如下：

zlbytes：4個字節。記錄壓縮列表總共占用的字節數，在對壓縮列表進行內存重分配時使用
zltail：4個字節。可通過這個字段快速定位到鏈表末尾
zllen：2個字節。記錄總共有多少個entry
entry：具體數據的內容就存在這里
zlend：1個字節。為十六進制值0xFF，標記一個壓縮列表的末尾

具體的數據存放在entry中。在ziplist中，可以存儲兩種數據：

字符串（字節數組）
整數

舉一個例子，一個zset在數據量少的情況下，會將元素名和分值按從小到大的順序在ziplist的entry中連續存儲：

那么問題來了，我們在讀取數據的時候，我們怎么知道是應該按照讀取字符串還是整數類型的方式去讀取呢？我們需要知道當前entry存儲數據的類型，即一個encoding字段，用來標識當前entry數據的類型。
除此之外，我們在查找一個元素的時候，需要對其進行遍歷，在ziplist中是如何遍歷的呢？回想我們在數組中的遍歷方式：

普通數組的遍歷是根據數組里存儲的數據類型來找到下一個元素的，例如int類型的數組（也是指針）訪問下一個元素時每次只需要加上相應類型的指針偏移量即可（如果用下標法表示數組，p[0]到p[1]就等效于p+1*sizeof(int)這個過程；如果用指針法，可以用p+1來表示，它也等效于p+1*sizeof(int)）

那么在ziplist中，我們不知道數據類型，也不知道這個數據的長度，該如何將遍歷用的指針往后挪呢？這就需要一個字段去完成這個任務，這里就是previous_entry_length，它記錄前一個entry的長度，可以利用它完成壓縮列表的遍歷
最后，就是最重要的字段，即存儲真正數據的字段content
以我們上圖的例子，繼續我們畫出entry的結構：

previous_entry_length：記錄了壓縮列表中前一個entry的長度。占用1或5字節

encoding：表示當前entry存儲數據的類型與數據的長度。占用1、2或5字節

content：真正存儲數據的地方

遍歷是查找操作的基礎，學習任意一種數據結構，遍歷都是關鍵。

正向遍歷ziplist：首先指針p在第一個entry的起始位置，即previous_entry_length字段的位置。由于previous_entry_length可能占用1個字節、也可能占用5個字節，所以我們需要知道如何區分這個字段占用了1還是5字節。表示方法如下：

如果前一個entry的長度小于254字節時，previous_entry_length用1字節表示
如果前一個entry的長度大于等于254字節時，previous_entry_length用5字節表示。注意此時第一個字節是固定的標志0xFE（254），后面4個字節用來表示前一個entry的長度

這樣一來，我們就能夠知道：由于我們當前的指針為unsigned char *類型（見源碼），指針運算p+1就等于往后偏移1個字節（即8位）。所以只需要讀取當前指針的第一個字節的內容，即p[0]的值是否在二進制的00000000 ~ 11111110（即0~254）之間。如果在這個區間內，就說明previous_entry_length只占用1個字節，使用p+1就能夠得到encoding的首地址了；如果p[0]的值為11111111（255），說明previous_entry_length占用了5個字節，使用p+5也能夠得到encoding的首地址。

現在我們的指針來到了encoding字段起始地址的位置。那么，encoding字段是如何存儲數據類型和長度的呢？為了節省encoding字段所占用的內存空間，將所有字符數組（字符串）類型以及整數類型按照如下編碼方式區分：

觀察上圖encoding的編碼方式，我們發現，只需要讀取當前指針位置往后偏移兩位的內容，就能夠得到encoding字段的長度。（00、11占用1字節；01占用2字節；10占用5字節）。那么我們相應的p+1、p+2、p+5即可將指針偏移到content的位置。

由于我們在encoding字段中知道content字段的數據類型的長度（如int16等）再將指針往后偏移之前encoding字段中存儲的的相應數據類型長度，就可以偏移到content字段的末尾了。后面如果有多個同樣的entry結構，也同理，這樣就成功實現了ziplist的正序遍歷。

由于previous_entry_length字段的存在，我們首先取出外部zltail字段，也就是指向ziplist結構末尾的指針，然后一次又一次地將指針減去entry中previous_entry_length字段的值，就能夠將指針偏移到ziplist的頭部，原理很簡單，相信大家都能夠理解，不再贅述。所以我們能夠發現，ziplist更適合從后往前遍歷。

其實ziplist就是借鑒了數組的思想，skiplist借鑒了鏈表的思想。不管是正向還是反向遍歷，還是在ziplist的插入或者刪除中需要將后面的元素往后挪或者往前挪，所有操作的復雜度均為O(n)。比起zset的另一種實現dict+skiplist中查詢O(1)的時間復雜度，還有插入以及刪除的O(logn)復雜度，ziplist在效率方面并沒有優勢。但是我們之前講過，redis的設計思想一般都是以時間換空間，所以，相比skiplist需要維護大量的指針、在多層上面重復的數據（skiplist占用的空間為2n，詳情請看上一篇筆記），ziplist在空間復雜度上優勢盡顯。

但是我們不得不說，ziplist在時間復雜度上面的劣勢依然存在，所以我們不能把劣勢無限放大開來，而是要揚長避短。所以，redis開發者也反復權衡，考慮到了這一點。就拿zset來說，只有符合如下兩個條件，才會使用ziplist編碼，否則使用skiplist進行編碼：

zset中的對象保存的元素數量不超過128個
zset中保存的所有元素成員的長度小于64字節

這樣一來，由于ziplist只處理少量、且規模很小的數據，這使得時間復雜度O(n)在ziplist處理少量數據的時候，這個n是非常小的。所以，這樣就能夠將其時間復雜度的影響降到了最低，將其空間復雜度的優勢發揮到最大，這就是為什么需要進行編碼轉換的根本原因。

至于ziplist的關鍵之處就講完了。至于其增刪改查的具體源碼，有興趣的讀者可以去ziplist.c中深入查看，筆者在這篇文章里再復制粘貼一次意義也不大。學習的過程中，我閱讀了大量的資料，但是內容質量參差不齊。這里我想說，我們在學習一種新知識的時候，不僅僅要知道它是什么樣子，也要知道它為什么是這樣的、為什么這么做而不采用其它的替代方案？它的比較優勢在哪里？而不要簡單的堆砌概念。在學習的同時，如果沒有經過自己的思考，收效甚微。