跳躍表在 Redis 中的應用

前提申明，因篇幅有限，本文隻介紹跳躍表在 Redis 中的應用，而關于跳躍表的原理性介紹，還請參考其他相關書籍，或參考博文[url=https://blog.csdn.net/u014427196/article/details/52454462]跳躍表 SkipList【資料結構】原理及實作[/url]。

跳躍表是一種有序資料結構，它實作了同二分查找一樣的平均 O(logN)、最壞 O(N) 複雜度的節點查找。由于它的效率可以和平衡樹相媲美，而實作又比平衡樹簡單，是以很多情況下可以用來代替平衡樹。

跳躍表在 Redis 中不如連結清單和字典等資料結構的應用廣泛，隻有兩個地方用到。一是實作有序集合鍵，另一個是在叢集節點中用作内部資料結構。

Redis 中的跳躍表節點的實作如下：

關于該結構中的成員需要作如下說明：

* 層數組 level：其中的每個 zskiplistLevel 結構元素都表示一層，該結構中包含一個指向同層中下一個連結清單節點的指針 forward，稱為前進指針，以及一個稱為跨度的屬性 span，表示前進指針指向的下一個節點與目前節點的距離。跨度主要是用來計算目标節點的排位（rank，即相當于在底層整個有序連結清單中的索引位置）：在查找某個節點的過程中，将沿途通路過的所有層的跨度累計起來，得到的結果就是目标節點在跳躍表中的排位。層就如同于對一個普通有序連結清單建立起了多級索引，是以一般層的數量越多，通路相應節點的速度就越快。每次建立一個新跳躍表節點的時候，Redis 都會根據幂次定律（即越大的數出現的機率越小）随機生成一個介于 1 到 32 之間的數作為 level 數組的大小，也就是層的“高度”。

* 後退指針 backward：主要用于從表尾向表頭方向通路節點。它不能像前進指針一樣可以一次跳過多個中間節點，因為每個節點隻有一個後退指針，是以每次隻能後退至前一個節點。

* 成員分值 score 和成員對象 obj：這兩個屬性就是每個節點中儲存的真正的資料值。跳躍表中的所有節點都按分值從小到大來排序。成員分值可以相同，但成員對象必須唯一：分值相同的成員将按照成員對象的字典序來進行排序。

雖然通過多個跳躍表節點就可以組成一個跳躍表，不過 Redis 使用了如下的 zskiplist 結構來持有這些節點，這樣就能更友善地對整個跳躍表進行處理，比如快速通路跳躍表的表頭節點和表尾節點，或者快速地擷取跳躍表的節點數量等。

下圖是 Redis 中的一個跳躍表示例。

[img]http://dl2.iteye.com/upload/attachment/0130/5591/8fca27c9-da15-3f93-83d1-7d2e9a7ccdd3.png[/img]

圖中的 L1、L2 等字樣表示節點的各個層，連線上帶有數字的箭頭代表前進指針，而那個數字就是跨度，後退指針用 BW 字樣表示。另外，由于表頭節點的後退指針、成員分值和成員對象都不會被用到，是以圖中隻顯示了表頭節點的各個層。