跳表實(shí)現(xiàn)

跳躍表（skiplist）是一種有序數(shù)據(jù)結(jié)構(gòu)， 它通過(guò)在每個(gè)節(jié)點(diǎn)中維持多個(gè)指向其他節(jié)點(diǎn)的指針， 從而達(dá)到快速訪問(wèn)節(jié)點(diǎn)的目的。

跳躍表支持平均 O(\log N) 最壞 O(N) 復(fù)雜度的節(jié)點(diǎn)查找， 還可以通過(guò)順序性操作來(lái)批量處理節(jié)點(diǎn)。
Redis 的跳躍表由 redis.h/zskiplistNode 和 redis.h/zskiplist 兩個(gè)結(jié)構(gòu)定義， 其中 zskiplistNode 結(jié)構(gòu)用于表示跳躍表節(jié)點(diǎn)， 而 zskiplist 結(jié)構(gòu)則用于保存跳躍表節(jié)點(diǎn)的相關(guān)信息， 比如節(jié)點(diǎn)的數(shù)量， 以及指向表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)的指針， 等等。

image.png

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

位于 zskiplist 結(jié)構(gòu)右方的是四個(gè) zskiplistNode 結(jié)構(gòu)， 該結(jié)構(gòu)包含以下屬性：

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

redis.h/zskiplistNode 結(jié)構(gòu)定義：

typedef struct zskiplistNode {

    // 后退指針
    struct zskiplistNode *backward;

    // 分值
    double score;

    // 成員對(duì)象
    robj *obj;

    // 層
    struct zskiplistLevel {

        // 前進(jìn)指針
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;

層

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

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

image.png

前進(jìn)指針

每個(gè)層都有一個(gè)指向表尾方向的前進(jìn)指針（level[i].forward 屬性）， 用于從表頭向表尾方向訪問(wèn)節(jié)點(diǎn)。

下圖用虛線表示出了程序從表頭向表尾方向， 遍歷跳躍表中所有節(jié)點(diǎn)的路徑：

• 迭代程序首先訪問(wèn)跳躍表的第一個(gè)節(jié)點(diǎn)（表頭）， 然后從第四層的前進(jìn)指針移動(dòng)到表中的第二個(gè)節(jié)點(diǎn)。
• 在第二個(gè)節(jié)點(diǎn)時(shí)， 程序沿著第二層的前進(jìn)指針移動(dòng)到表中的第三個(gè)節(jié)點(diǎn)。
• 在第三個(gè)節(jié)點(diǎn)時(shí)， 程序同樣沿著第二層的前進(jìn)指針移動(dòng)到表中的第四個(gè)節(jié)點(diǎn)。
• 當(dāng)程序再次沿著第四個(gè)節(jié)點(diǎn)的前進(jìn)指針移動(dòng)時(shí)， 它碰到一個(gè) NULL ， 程序知道這時(shí)已經(jīng)到達(dá)了跳躍表的表尾， 于是結(jié)束這次遍歷。

image.png

跨度

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

• 兩個(gè)節(jié)點(diǎn)之間的跨度越大， 它們相距得就越遠(yuǎn)。
• 指向 NULL 的所有前進(jìn)指針的跨度都為 0 ， 因?yàn)樗鼈儧](méi)有連向任何節(jié)點(diǎn)。
  初看上去， 很容易以為跨度和遍歷操作有關(guān)， 但實(shí)際上并不是這樣 —— 遍歷操作只使用前進(jìn)指針就可以完成了， 跨度實(shí)際上是用來(lái)計(jì)算排位（rank）的： 在查找某個(gè)節(jié)點(diǎn)的過(guò)程中， 將沿途訪問(wèn)過(guò)的所有層的跨度累計(jì)起來(lái)， 得到的結(jié)果就是目標(biāo)節(jié)點(diǎn)在跳躍表中的排位。

舉個(gè)例子， 下圖用虛線標(biāo)記了在跳躍表中查找分值為 3.0 、 成員對(duì)象為 o3 的節(jié)點(diǎn)時(shí)， 沿途經(jīng)歷的層： 查找的過(guò)程只經(jīng)過(guò)了一個(gè)層， 并且層的跨度為 3 ， 所以目標(biāo)節(jié)點(diǎn)在跳躍表中的排位為 3 。

image.png

后退指針

節(jié)點(diǎn)的后退指針（backward 屬性）用于從表尾向表頭方向訪問(wèn)節(jié)點(diǎn)： 跟可以一次跳過(guò)多個(gè)節(jié)點(diǎn)的前進(jìn)指針不同， 因?yàn)槊總€(gè)節(jié)點(diǎn)只有一個(gè)后退指針， 所以每次只能后退至前一個(gè)節(jié)點(diǎn)。

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

image.png

分值和成員

節(jié)點(diǎn)的分值（score 屬性）是一個(gè) double 類型的浮點(diǎn)數(shù)， 跳躍表中的所有節(jié)點(diǎn)都按分值從小到大來(lái)排序。

節(jié)點(diǎn)的成員對(duì)象（obj 屬性）是一個(gè)指針， 它指向一個(gè)字符串對(duì)象， 而字符串對(duì)象則保存著一個(gè) SDS 值。

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

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

image.png

跳躍表

雖然僅靠多個(gè)跳躍表節(jié)點(diǎn)就可以組成一個(gè)跳躍表

image.png

zskiplist 結(jié)構(gòu)的定義

typedef struct zskiplist {

    // 表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)
    struct zskiplistNode *header, *tail;

    // 表中節(jié)點(diǎn)的數(shù)量
    unsigned long length;

    // 表中層數(shù)最大的節(jié)點(diǎn)的層數(shù)
    int level;

} zskiplist;

但通過(guò)使用一個(gè) zskiplist 結(jié)構(gòu)來(lái)持有這些節(jié)點(diǎn)， 程序可以更方便地對(duì)整個(gè)跳躍表進(jìn)行處理， 比如快速訪問(wèn)跳躍表的表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)， 又或者快速地獲取跳躍表節(jié)點(diǎn)的數(shù)量（也即是跳躍表的長(zhǎng)度）等信息， 如下圖所示

image.png

header 和 tail 指針?lè)謩e指向跳躍表的表頭和表尾節(jié)點(diǎn)， 通過(guò)這兩個(gè)指針， 程序定位表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)的復(fù)雜度為 O(1) 。
通過(guò)使用 length 屬性來(lái)記錄節(jié)點(diǎn)的數(shù)量， 程序可以在 O(1) 復(fù)雜度內(nèi)返回跳躍表的長(zhǎng)度。
level 屬性則用于在 O(1) 復(fù)雜度內(nèi)獲取跳躍表中層高最大的那個(gè)節(jié)點(diǎn)的層數(shù)量， 注意表頭節(jié)點(diǎn)的層高并不計(jì)算在內(nèi)。

總結(jié)

• 跳躍表是有序集合的底層實(shí)現(xiàn)之一， 除此之外它在 Redis 中沒(méi)有其他應(yīng)用。
• Redis 的跳躍表實(shí)現(xiàn)由 zskiplist 和 zskiplistNode 兩個(gè)結(jié)構(gòu)組成， 其中 zskiplist 用于保存跳躍表信息（比如表頭節(jié)點(diǎn)、表尾節(jié)點(diǎn)、長(zhǎng)度）， 而 zskiplistNode 則用于表示跳躍表節(jié)點(diǎn)。
• 每個(gè)跳躍表節(jié)點(diǎn)的層高都是 1 至 32 之間的隨機(jī)數(shù)。
• 在同一個(gè)跳躍表中， 多個(gè)節(jié)點(diǎn)可以包含相同的分值， 但每個(gè)節(jié)點(diǎn)的成員對(duì)象必須是唯一的。
• 跳躍表中的節(jié)點(diǎn)按照分值大小進(jìn)行排序， 當(dāng)分值相同時(shí)， 節(jié)點(diǎn)按照成員對(duì)象的大小進(jìn)行排序。