本文主要用來學(xué)習(xí)下，redis當中使用的壓縮表和跳躍表，為什么在諸多的數(shù)據(jù)結(jié)構(gòu)中，redis要選擇他們作為自己的數(shù)據(jù)存儲結(jié)構(gòu)。
什么是壓縮表？
壓縮表是Redis為了
節(jié)約內(nèi)存而開發(fā)的，是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型（sequential）數(shù)據(jù)結(jié)構(gòu)。一個壓縮列表可以包含任意多個節(jié)點（entry），每個節(jié)點可以保存一個字節(jié)數(shù)組或者一個整數(shù)值。
壓縮表的構(gòu)成
壓縮表的構(gòu)成如下所示：
壓縮表各構(gòu)成部分的含義說明：
| 屬性 | 用途 |
|---|---|
| zlbytes | 記錄整個壓縮表占用的字節(jié)數(shù)；在對壓縮列表進行內(nèi)存重分配或者計算zlend時使用 |
| zltail | 記錄壓縮表尾結(jié)點距離起始節(jié)點的字節(jié)距離 |
| zllen | 記錄壓縮表包含的節(jié)點數(shù)量 |
| entry | 壓縮表的節(jié)點，長度由其內(nèi)容決定 |
| zlend | 標記壓縮表末端 |
壓縮表節(jié)點(entry)的構(gòu)成
每個節(jié)點由以下三個部分組成：
其中三個部分的含義分別是：
| 屬性 | 用途 |
|---|---|
| previous_entry_length | 以字節(jié)為單位，記錄前一個節(jié)點的長度。程序可以通過指針運算，根據(jù)當前節(jié)點的起始地址來計算出前一個節(jié)點的起始地址。從表尾向表頭遍歷操作就是通過這樣原理實現(xiàn)的。 |
| encoding | 記錄了節(jié)點的content屬性所保存數(shù)據(jù)的類型以及長度 |
| content | 保存節(jié)點的值，節(jié)點值可以是一個字節(jié)數(shù)組或者整數(shù)，值的類型和長度由節(jié)點的encoding屬性決定 |
連鎖更新問題
在前面介紹previous_entry_length的時候，有一點沒有詳細說明：
如果前一節(jié)點的長度小于254字節(jié)，那么previous_entry_length屬性需要用1字節(jié)長的空間來保存這個長度值。
如果前一節(jié)點的長度大于等于254字節(jié)，那么previous_entry_length屬性需要用5字節(jié)長的空間來保存這個長度值。
正是由于這樣的設(shè)計，從而會導(dǎo)致連鎖更新問題。
假設(shè)有 entry1 到 entryN 個節(jié)點，每個節(jié)點的字節(jié)長度都在 250 到 253 之間，則每個節(jié)點的previous_entry_length存儲的長度都是1。
如果此時 new 一個大于254的節(jié)點被壓入壓縮表的頭部，那么這個 new 將成為 e1 前面的頭結(jié)點。此時e1的previous_entry_length只有1字節(jié)，無法保存前一節(jié)點new的5字節(jié)長度，所以需要將e1的長度擴大為254 ~ 257。
同樣的，對于e2來說，需要如e1一樣增加容量才行。直到eN，都需要重新分配空間，這一種連續(xù)擴展空間的操作被稱之為連鎖更新。
其實連鎖更新造成的性能損耗的幾率是很低的，實際使用過程中幾乎不會出現(xiàn)我們上面提到的極端環(huán)境，即使少量的連鎖更新，也可以忽略不計
什么是跳躍表？
跳躍表（skiplist）是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過在每個節(jié)點中維持多個指向其他節(jié)點的指針，從而達到快速訪問節(jié)點的目的。
跳躍表的時間復(fù)雜度是平均O（logN）、最壞O（N）。
實現(xiàn)有序集合的方式有很多，為什么redis選擇跳躍表？
- 數(shù)組：數(shù)組元素插入、刪除不便
- 鏈表：查詢元素效率低
- 平衡樹：實現(xiàn)復(fù)雜
大多數(shù)情況下，跳躍表的效率可以和和平衡樹媲美，而其實現(xiàn)相對平衡樹要簡單，所以很多情況下用跳躍表去替代平衡樹。
跳躍表的構(gòu)成
跳躍表在redis當中由兩部分構(gòu)成：
-
zskiplistNode：跳躍表節(jié)點 -
zskiplist：保存跳躍表節(jié)點信息
跳躍表的模型如下所示：
如上圖所示：
- 藍色的是
zskiplist結(jié)構(gòu) - 其他四個綠色的是
zskiplistNode結(jié)構(gòu)
zskiplist結(jié)構(gòu)介紹
在前面的圖上我們看到zskiplist包含四個部分：
-
header：指向跳躍表頭結(jié)點 -
tail：指向跳躍表的尾結(jié)點 -
level：記錄跳躍表中層數(shù)最大的節(jié)點層數(shù)。（注意：頭結(jié)點固定高度為32，初始全部指向NULL，且不被levle記錄層高） -
length：記錄跳躍表長度，即包含幾個節(jié)點。（頭結(jié)點除外）
使用多個節(jié)點就可以作為跳躍表，那么為什么還需要zskiplist？
實際通過zskiplist的結(jié)構(gòu)就可以得出：
-
header和tail:快速訪問跳躍表的頭或尾節(jié)點，且時間復(fù)雜度是O(1)，否則可能需要遍歷至少大于等于1次。 -
length：快速獲取長度（即節(jié)點數(shù)量），時間復(fù)雜度都O(1)，否則需要遍歷整個跳躍表。 -
level：用來快速獲取最高節(jié)點層數(shù)，時間復(fù)雜度是O(1)。
可以幫助我們方便、快速的處理跳躍表。
zskiplistNode結(jié)構(gòu)介紹
在前面的圖我們看到zskiplistNode包含四種部分：
-
Level：層，即以L開頭的部分。Level包含兩個部分前進指針和跨度。表頭向表位遍歷時，會沿著前進指針前進。-
前進指針：指向表尾方向的其他節(jié)點 -
跨度：當前節(jié)點距離指向節(jié)點的距離，即上圖箭頭上的數(shù)字。
每當有一個新的節(jié)點加入跳躍表，程序根據(jù)冪次法則生成一個介于1和32之間的值作為level的大小，即層的高度。
-
backward：后退指針，即BW。指向當前節(jié)點的前一個節(jié)點，當從表尾向表頭遍歷時被使用。score：分值，即1.0、2.0、3.0。在跳躍表中會按照分值從小到大排列。object：成員對象，即o1、o2、o3。當分值相同時，按照成員對象進行排序
表頭節(jié)點也有backward、score、object，但是不會使用。
