---

highlight: a11y-dark theme: channing-cyan

---

本文主要用來學習下，redis當中使用的壓縮表和跳躍表，為什麼在諸多的資料結構中，redis要選擇他們作為自己的資料儲存結構。

什麼是壓縮表？

壓縮表是Redis為了節約記憶體而開發的，是由一系列特殊編碼的連續記憶體塊組成的順序型（sequential）資料結構。一個壓縮列表可以包含任意多個節點（entry），每個節點可以儲存一個位元組陣列或者一個整數值。

壓縮表的構成

壓縮表的構成如下所示：

壓縮表各構成部分的含義說明：

| 屬性 | 用途 | | --- | --- | | zlbytes | 記錄整個壓縮表佔用的位元組數；在對壓縮列表進行記憶體重分配或者計算zlend時使用 | | zltail | 記錄壓縮表尾結點距離起始節點的位元組距離 | | zllen | 記錄壓縮表包含的節點數量 | | entry | 壓縮表的節點，長度由其內容決定 | | zlend | 標記壓縮表末端 |

壓縮表節點(entry)的構成

每個節點由以下三個部分組成：

其中三個部分的含義分別是：

| 屬性 | 用途 | | --- | --- | | previous_entry_length | 以位元組為單位，記錄前一個節點的長度。程式可以通過指標運算，根據當前節點的起始地址來計算出前一個節點的起始地址。從表尾向表頭遍歷操作就是通過這樣原理實現的。 | | encoding | 記錄了節點的content屬性所儲存資料的型別以及長度 | | content | 儲存節點的值，節點值可以是一個位元組陣列或者整數，值的型別和長度由節點的encoding屬性決定 |

連鎖更新問題

在前面介紹previous_entry_length的時候，有一點沒有詳細說明：

• 如果前一節點的長度小於254位元組，那麼previous_entry_length屬性需要用1位元組長的空間來儲存這個長度值。

• 如果前一節點的長度大於等於254位元組，那麼previous_entry_length屬性需要用5位元組長的空間來儲存這個長度值。

正是由於這樣的設計，從而會導致連鎖更新問題。

假設有 entry1 到 entryN 個節點，每個節點的位元組長度都在 250 到 253 之間，則每個節點的previous_entry_length儲存的長度都是1。

如果此時 new 一個大於254的節點被壓入壓縮表的頭部，那麼這個 new 將成為 e1 前面的頭結點。此時e1的previous_entry_length只有1位元組，無法儲存前一節點new的5位元組長度，所以需要將e1的長度擴大為254 ~ 257。

同樣的，對於e2來說，需要如e1一樣增加容量才行。直到eN，都需要重新分配空間，這一種連續擴充套件空間的操作被稱之為連鎖更新。

其實連鎖更新造成的效能損耗的機率是很低的，實際使用過程中幾乎不會出現我們上面提到的極端環境，即使少量的連鎖更新，也可以忽略不計

什麼是跳躍表？

跳躍表（skiplist）是一種有序資料結構，它通過在每個節點中維持多個指向其他節點的指標，從而達到快速訪問節點的目的。

跳躍表的時間複雜度是平均O（logN）、最壞O（N）。

實現有序集合的方式有很多，為什麼redis選擇跳躍表？

• 陣列：陣列元素插入、刪除不便
• 連結串列：查詢元素效率低
• 平衡樹：實現複雜

大多數情況下，跳躍表的效率可以和和平衡樹媲美，而其實現相對平衡樹要簡單，所以很多情況下用跳躍表去替代平衡樹。

跳躍表的構成

跳躍表在redis當中由兩部分構成： * zskiplistNode：跳躍表節點 * zskiplist：儲存跳躍表節點資訊

跳躍表的模型如下所示：

如上圖所示：

• 藍色的是zskiplist結構
• 其他四個綠色的是zskiplistNode結構

zskiplist結構介紹

在前面的圖上我們看到zskiplist包含四個部分：

• header：指向跳躍表頭結點
• tail：指向跳躍表的尾結點
• level：記錄跳躍表中層數最大的節點層數。（注意：頭結點固定高度為32，初始全部指向NULL，且不被levle記錄層高）
• length：記錄跳躍表長度，即包含幾個節點。（頭結點除外）

使用多個節點就可以作為跳躍表，那麼為什麼還需要zskiplist？

實際通過zskiplist的結構就可以得出： * header和tail:快速訪問跳躍表的頭或尾節點，且時間複雜度是O(1)，否則可能需要遍歷至少大於等於1次。 * length：快速獲取長度（即節點數量），時間複雜度都O(1)，否則需要遍歷整個跳躍表。 * level：用來快速獲取最高節點層數，時間複雜度是O(1)。

可以幫助我們方便、快速的處理跳躍表。

zskiplistNode結構介紹

在前面的圖我們看到zskiplistNode包含四種部分： * Level：層，即以L開頭的部分。Level包含兩個部分前進指標和跨度。表頭向表位遍歷時，會沿著前進指標前進。

* `前進指標`：指向表尾方向的其他節點
* `跨度`：當前節點距離指向節點的距離，即上圖箭頭上的數字。

每當有一個新的節點加入跳躍表，程式根據[冪次法則](http://baike.baidu.com/item/%E5%B9%82%E6%AC%A1%E6%B3%95%E5%88%99/8271554)生成一個介於1和32之間的值作為level的大小，即層的高度。

• backward：後退指標，即BW。指向當前節點的前一個節點，當從表尾向表頭遍歷時被使用。
• score：分值，即1.0、2.0、3.0。在跳躍表中會按照分值從小到大排列。
• object：成員物件，即o1、o2、o3。當分值相同時，按照成員物件進行排序

表頭節點也有backward、score、object，但是不會使用。