Redis 跳躍表的實現(xiàn)

跳躍表是一種可以對有序鏈表進行近似二分查找的數(shù)據(jù)結構，redis 在兩個地方用到了跳躍表，一個是實現(xiàn)有序集合，另一個是在集群節(jié)點中用作內(nèi)部數(shù)據(jù)結構。

    跳躍表 ( skiplist ) 是一種有序數(shù)據(jù)結構，它通過在每個節(jié)點中維持多個指向其他節(jié)點的指針，從而達到快速訪問節(jié)點的目的。

    跳躍表支持平均O ( logN ) 、最壞 O(N) 復雜度的節(jié)點查找，還可以通過順序性操作來批量處理節(jié)點。

    在大部分情況下，跳躍表的效率可以和平衡樹相媲美，并且因為跳躍表的實現(xiàn)比平衡樹要來得更為簡單，所以有不少程序都使用跳躍表來代替平衡樹。

    Redis使用跳躍表作為有序集合鍵的底層實現(xiàn)之一，如果一個有序集合包含的元素數(shù)量比較多，又或者有序集合中元素的成員 ( member ) 是比較長的字符串時，Redis 就會使用跳躍表來作為有序集合鍵的底層實現(xiàn)。

    和鏈表、字典等數(shù)據(jù)結構被廣泛地應用在 Redis 內(nèi)部不同，Redis 只在兩個地方用到了跳躍表，一個是實現(xiàn)有序集合鍵，另一個是在集群節(jié)點中用作內(nèi)部數(shù)據(jù)結構，除此之外，跳躍表在 Redis 里面沒有其他用途。

圖 5-1 展示了一個跳躍表示例， 位于圖片最左邊的是 zskiplist 結構， 該結構包含以下屬性：

• header ：指向跳躍表的表頭節(jié)點。
• tail ：指向跳躍表的表尾節(jié)點。
• level ：記錄目前跳躍表內(nèi)，層數(shù)最大的那個節(jié)點的層數(shù)（表頭節(jié)點的層數(shù)不計算在內(nèi)）。
• length ：記錄跳躍表的長度，也即是，跳躍表目前包含節(jié)點的數(shù)量（表頭節(jié)點不計算在內(nèi)）。

位于 zskiplist 結構右方的是四個 zskiplistNode 結構， 該結構包含以下屬性：

• 層（level）：節(jié)點中用 L1 、 L2 、 L3 等字樣標記節(jié)點的各個層， L1 代表第一層， L2 代表第二層，以此類推。每個層都帶有兩個屬性：前進指針和跨度。前進指針用于訪問位于表尾方向的其他節(jié)點，而跨度則記錄了前進指針所指向節(jié)點和當前節(jié)點的距離。在上面的圖片中，連線上帶有數(shù)字的箭頭就代表前進指針，而那個數(shù)字就是跨度。當程序從表頭向表尾進行遍歷時，訪問會沿著層的前進指針進行。
• 后退（backward）指針：節(jié)點中用 BW 字樣標記節(jié)點的后退指針，它指向位于當前節(jié)點的前一個節(jié)點。后退指針在程序從表尾向表頭遍歷時使用。
• 分值（score）：各個節(jié)點中的 1.0 、 2.0 和 3.0 是節(jié)點所保存的分值。在跳躍表中，節(jié)點按各自所保存的分值從小到大排列。
• 成員對象（obj）：各個節(jié)點中的 o1 、 o2 和 o3 是節(jié)點所保存的成員對象。

注意表頭節(jié)點和其他節(jié)點的構造是一樣的： 表頭節(jié)點也有后退指針、分值和成員對象， 不過表頭節(jié)點的這些屬性都不會被用到， 所以圖中省略了這些部分， 只顯示了表頭節(jié)點的各個層。

本節(jié)接下來的內(nèi)容將對 zskiplistNode 和 zskiplist 兩個結構進行更詳細的介紹。

跳躍表節(jié)點

跳躍表節(jié)點的實現(xiàn)由 redis.h/zskiplistNode 結構定義：

typedef struct zskiplistNode {

    // 后退指針
    struct zskiplistNode *backward;

    // 分值
    double score;

    // 成員對象
    robj *obj;

    // 層
    struct zskiplistLevel {

        // 前進指針
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;

分值和成員

    節(jié)點的分值(score屬性)是一個double類型的浮點數(shù)，跳躍表中的所有節(jié)點都按分值從小到大來排序。

    節(jié)點的成員對象(obj屬性)是一個指針，它指向一個字符串對象，而字符串對象則保存著一個SDS值。

    在同一個跳躍表中，各個節(jié)點保存的成員對象必須是唯一的，但是多個節(jié)點保存的分值卻可以是相同的：分至相同的節(jié)點將按照成員對象在字典中的大小來進行排序，成員對象較小的節(jié)點會排在前面(靠近表頭的方向)，而成員對象較大的節(jié)點則會排在后面(靠近表尾的方向)。

    舉個例子，在下圖中所示的跳躍表中，三個跳躍表節(jié)點都保存了相同的分值10086.0，但保存成員對象 o1 的節(jié)點卻排在保存成員對象 o2 和 o3 的節(jié)點的前面，而保存成員對象 o2 的節(jié)點又排在保存成員對象 o3 的節(jié)點之前，由此可見，o1、o2、o3 三個成員對象在字典中的排序為 o1<=o2<=o3 。

后退指針

    節(jié)點的后退指針 ( backward 屬性 ) 用于從表尾向表頭方向訪問節(jié)點：跟可以一次跳過多個節(jié)點的前進指針不同，因為每個節(jié)點只有一個后退指針，所以每次只能后退至前一個節(jié)點。

    下圖用虛線展示了如何從表尾向表頭遍歷跳躍表中的所有節(jié)點：程序首先通過跳躍表的tail指針訪問表尾節(jié)點，然后通過后退指針訪問倒數(shù)第二個節(jié)點，之后再沿著后退指針訪問倒數(shù)第三個節(jié)點，再之后遇到指向 NULL 的后退指針，于是訪問結束。

層

    跳躍表節(jié)點的 level 數(shù)組可以包含多個元素，每個元素都包含一個指向其他節(jié)點的指針，程序可以通過這些層來加快訪問其他節(jié)點的速度，一般來說，層的數(shù)量越多，訪問其他節(jié)點的速度就越快。

    每次創(chuàng)建一個新跳躍表節(jié)點的時候，程序根據(jù)冪次定律 ( power law，越大的數(shù)出現(xiàn)的概率越小)隨機生成一個介于 1 和 32 之間的值作為 level 數(shù)組的大小，這個大小就是層的“高度”。

    下圖分別展示了三個高度為1層、3層和5層的節(jié)點，因為 C 語言的數(shù)組索引總是從 0 開始的，所以節(jié)點的第一層是 level[0]，而第二層是 level[1]，依次類推。

前進指針

??每個層都有一個指向表尾方向的前進指針(level[i].forward屬性)，用于從表頭向表尾方向訪問節(jié)點。下圖用虛線表示出了程序從表頭向表尾方向，遍歷跳躍表中所有節(jié)點的路徑：

1. 迭代程序首先訪問跳躍表的第一個節(jié)點(表頭)，然后從第四層的前進指針移動到表中的第二個節(jié)點。
2. 在第二個節(jié)點時，程序沿著第二層的前進指針移動到表中的第三個節(jié)點。
3. 在第三個節(jié)點時，程序同樣沿著第二層的前進指針移動到表中的第四個節(jié)點。
4. 當程序再次沿著第四個節(jié)點的前進指針移動時，它碰到一個NULL，程序知道這時已經(jīng)到達了跳躍表的表尾，于是結束這次遍歷。

跨度

層的跨度（level[i].span 屬性）用于記錄兩個節(jié)點之間的距離：

• 兩個節(jié)點之間的跨度越大， 它們相距得就越遠。
• 指向 NULL 的所有前進指針的跨度都為 0 ， 因為它們沒有連向任何節(jié)點。

初看上去， 很容易以為跨度和遍歷操作有關， 但實際上并不是這樣 —— 遍歷操作只使用前進指針就可以完成了， 跨度實際上是用來計算排位（rank）的： 在查找某個節(jié)點的過程中， 將沿途訪問過的所有層的跨度累計起來， 得到的結果就是目標節(jié)點在跳躍表中的排位。

舉個例子， 圖 5-4 用虛線標記了在跳躍表中查找分值為 3.0 、 成員對象為 o3 的節(jié)點時， 沿途經(jīng)歷的層： 查找的過程只經(jīng)過了一個層， 并且層的跨度為 3 ， 所以目標節(jié)點在跳躍表中的排位為 3 。