跳表
Redis 隻有 Zset 對象的底層實作用到了跳表，跳表的優勢是能支援平均 O(logN) 複雜度的節點查找。
zset 結構體裡有兩個資料結構：一個是跳表，一個是哈希表。這樣的好處是既能進行高效的範圍查詢，也能進行高效單點查詢。
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset; Zset 對象在執行資料插入或是資料更新的過程中，會依次在跳表和哈希表中插入或更新相應的資料，進而保證了跳表和哈希表中記錄的資訊一緻。
Zset 對象能支援範圍查詢（如 ZRANGEBYSCORE 操作），這是因為它的資料結構設計采用了跳表，而又能以常數複雜度擷取元素權重（如 ZSCORE 操作），這是因為它同時采用了哈希表進行索引。
可能很多人會奇怪，為什麼我開頭說 Zset 對象的底層資料結構是「壓縮清單」或者「跳表」，而沒有說哈希表呢？
Zset 對象在使用跳表作為資料結構的時候，是使用由「哈希表+跳表」組成的 struct zset，但是我們讨論的時候，都會說跳表是 Zset 對象的底層資料結構，而不會提及哈希表，是因為 struct zset 中的哈希表隻是用于以常數複雜度擷取元素權重，大部分操作都是跳表實作的。
接下來，詳細的說下跳表。
跳表結構設計
連結清單在查找元素的時候，因為需要逐一查找，是以查詢效率非常低，時間複雜度是O(N)，于是就出現了跳表。跳表是在連結清單基礎上改進過來的，實作了一種「多層」的有序連結清單，這樣的好處是能快讀定位資料。
那跳表長什麼樣呢？我這裡舉個例子，下圖展示了一個層級為 3 的跳表。
圖中頭節點有 L0~L2 三個頭指針，分别指向了不同層級的節點，然後每個層級的節點都通過指針連接配接起來：
- L0 層級共有 5 個節點，分别是節點1、2、3、4、5；
- L1 層級共有 3 個節點，分别是節點 2、3、5；
- L2 層級隻有 1 個節點，也就是節點 3 。
如果我們要在連結清單中查找節點 4 這個元素，隻能從頭開始周遊連結清單，需要查找 4 次，而使用了跳表後，隻需要查找 2 次就能定位到節點 4，因為可以在頭節點直接從 L2 層級跳到節點 3，然後再往前周遊找到節點 4。
可以看到，這個查找過程就是在多個層級上跳來跳去，最後定位到元素。當資料量很大時，跳表的查找複雜度就是 O(logN)。
那跳表節點是怎麼實作多層級的呢？這就需要看「跳表節點」的資料結構了，如下：
typedef struct zskiplistNode {
//Zset 對象的元素值
sds ele;
//元素權重值
double score;
//後向指針
struct zskiplistNode *backward;
//節點的level數組，儲存每層上的前向指針和跨度
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned long span;
} level[];
} zskiplistNode; Zset 對象要同時儲存「元素」和「元素的權重」，對應到跳表節點結構裡就是 sds 類型的 ele 變量和 double 類型的 score 變量。每個跳表節點都有一個後向指針（struct zskiplistNode *backward），指向前一個節點，目的是為了友善從跳表的尾節點開始通路節點，這樣倒序查找時很友善。
跳表是一個帶有層級關系的連結清單，而且每一層級可以包含多個節點，每一個節點通過指針連接配接起來，實作這一特性就是靠跳表節點結構體中的zskiplistLevel 結構體類型的 level 數組。
level 數組中的每一個元素代表跳表的一層，也就是由 zskiplistLevel 結構體表示，比如 leve[0] 就表示第一層，leve[1] 就表示第二層。zskiplistLevel 結構體裡定義了「指向下一個跳表節點的指針」和「跨度」，跨度時用來記錄兩個節點之間的距離。
比如，下面這張圖，展示了各個節點的跨度。
第一眼看到跨度的時候，以為是周遊操作有關，實際上并沒有任何關系，周遊操作隻需要用前向指針（struct zskiplistNode *forward）就可以完成了。
跨度實際上是為了計算這個節點在跳表中的排位。具體怎麼做的呢？因為跳表中的節點都是按序排列的，那麼計算某個節點排位的時候，從頭節點點到該結點的查詢路徑上，将沿途通路過的所有層的跨度累加起來，得到的結果就是目标節點在跳表中的排位。
舉個例子，查找圖中節點 3 在跳表中的排位，從頭節點開始查找節點 3，查找的過程隻經過了一個層（L2），并且層的跨度是 3，是以節點 3 在跳表中的排位是 3。
另外，圖中的頭節點其實也是 zskiplistNode 跳表節點，隻不過頭節點的後向指針、權重、元素值都沒有用到，是以圖中省略了這部分。
問題來了，由誰定義哪個跳表節點是頭節點呢？這就介紹「跳表」結構體了，如下所示：
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist; 跳表結構裡包含了：
- 跳表的頭尾節點，便于在O(1)時間複雜度内通路跳表的頭節點和尾節點；
- 跳表的長度，便于在O(1)時間複雜度擷取跳表節點的數量；
- 跳表的最大層數，便于在O(1)時間複雜度擷取跳表中層高最大的那個節點的層數量；
跳表節點查詢過程
查找一個跳表節點的過程時，跳表會從頭節點的最高層開始，逐一周遊每一層。在周遊某一層的跳表節點時，會用跳表節點中的 SDS 類型的元素和元素的權重來進行判斷，共有兩個判斷條件：
- 如果目前節點的權重「小于」要查找的權重時，跳表就會通路該層上的下一個節點。
- 如果目前節點的權重「等于」要查找的權重時，并且目前節點的 SDS 類型資料「小于」要查找的資料時，跳表就會通路該層上的下一個節點。
如果上面兩個條件都不滿足，或者下一個節點為空時，跳表就會使用目前周遊到的節點的 level 數組裡的下一層指針，然後沿着下一層指針繼續查找，這就相當于跳到了下一層接着查找。
舉個例子，下圖有個 3 層級的跳表。
如果要查找「元素：abcd，權重：4」的節點，查找的過程是這樣的：
- 先從頭節點的最高層開始，L2 指向了「元素：abc，權重：3」節點，這個節點的權重比要查找節點的小，是以要通路該層上的下一個節點；
- 但是該層的下一個節點是空節點（ leve[2]指向的是空節點），于是就會跳到「元素：abc，權重：3」節點的下一層去找，也就是 leve[1];
- 「元素：abc，權重：3」節點的 leve[1] 的下一個指針指向了「元素：abcde，權重：4」的節點，然後将其和要查找的節點比較。雖然「元素：abcde，權重：4」的節點的權重和要查找的權重相同，但是目前節點的 SDS 類型資料「大于」要查找的資料，是以會繼續跳到「元素：abc，權重：3」節點的下一層去找，也就是 leve[0]；
- 「元素：abc，權重：3」節點的 leve[0] 的下一個指針指向了「元素：abcd，權重：4」的節點，該節點正是要查找的節點，查詢結束。
跳表節點層數設定
跳表的相鄰兩層的節點數量的比例會影響跳表的查詢性能。
舉個例子，下圖的跳表，第二層的節點數量隻有 1 個，而第一層的節點數量有 6 個。
這時，如果想要查詢節點 6，那基本就跟連結清單的查詢複雜度一樣，就需要在第一層的節點中依次順序查找，複雜度就是 O(N) 了。是以，為了降低查詢複雜度，我們就需要維持相鄰層結點數間的關系。
**跳表的相鄰兩層的節點數量最理想的比例是 2:1，查找複雜度可以降低到 O(logN)**。
下圖的跳表就是，相鄰兩層的節點數量的比例是 2 : 1。
那怎樣才能維持相鄰兩層的節點數量的比例為 2 : 1 呢？
如果采用新增節點或者删除節點時，來調整跳表節點以維持比例的方法的話，會帶來額外的開銷。
Redis 則采用一種巧妙的方法是，跳表在建立節點的時候，随機生成每個節點的層數，并沒有嚴格維持相鄰兩層的節點數量比例為 2 : 1 的情況。
具體的做法是，跳表在建立節點時候，會生成範圍為[0-1]的一個随機數，如果這個随機數小于 0.25（相當于機率 25%），那麼層數就增加 1 層，然後繼續生成下一個随機數，直到随機數的結果大于 0.25 結束，最終确定該節點的層數。
這樣的做法，相當于每增加一層的機率不超過 25%，層數越高，機率越低，層高最大限制是 64。
為什麼用跳表而不用平衡樹？
為什麼 Zset 的實作用跳表而不用平衡樹（如 AVL樹、紅黑樹等）？
對于這個問題，Redis的作者 @antirez 是怎麼說的：
There are a few reasons:
- They are not very memory intensive. It's up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
- A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
- They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.
簡單翻譯一下，主要是從記憶體占用、對範圍查找的支援、實作難易程度這三方面總結的原因：
- 它們不是非常記憶體密集型的。基本上由你決定。改變關于節點具有給定級别數的機率的參數将使其比 btree 占用更少的記憶體。
- Zset 經常需要執行 ZRANGE 或 ZREVRANGE 的指令，即作為連結清單周遊跳表。通過此操作，跳表的緩存局部性至少與其他類型的平衡樹一樣好。
- 它們更易于實作、調試等。例如，由于跳表的簡單性，我收到了一個更新檔（已經在Redis master中），其中擴充了跳表，在 O(log(N) 中實作了 ZRANK。它隻需要對代碼進行少量修改。
我再詳細補充點：
從記憶體占用上來比較，跳表比平衡樹更靈活一些。平衡樹每個節點包含 2 個指針（分别指向左右子樹），而跳表每個節點包含的指針數目平均為 1/(1-p)，具體取決于參數 p 的大小。如果像 Redis裡的實作一樣，取 p=1/4，那麼平均每個節點包含 1.33 個指針，比平衡樹更有優勢。
在做範圍查找的時候，跳表比平衡樹操作要簡單。在平衡樹上，我們找到指定範圍的小值之後，還需要以中序周遊的順序繼續尋找其它不超過大值的節點。如果不對平衡樹進行一定的改造，這裡的中序周遊并不容易實作。而在跳表上進行範圍查找就非常簡單，隻需要在找到小值之後，對第 1 層連結清單進行若幹步的周遊就可以實作。
從算法實作難度上來比較，跳表比平衡樹要簡單得多。平衡樹的插入和删除操作可能引發子樹的調整，邏輯複雜，而跳表的插入和删除隻需要修改相鄰節點的指針，操作簡單又快速。