Redis 跳躍表

跳躍表

跳躍表（skiplist ）是一種隨機(jī)化的數(shù)據(jù)，由 William Pugh 在論文《Skip lists: a probabilistic alternative to balanced trees》 中提出，跳躍表以有序的方式在層次化的鏈表中保存元素，效率和平衡樹(shù)媲美 ——查找、刪除、添加等操作都可以在對(duì)數(shù)期望時(shí)間下完成，并且比起平衡樹(shù)來(lái)說(shuō)，跳躍表的實(shí)現(xiàn)要簡(jiǎn)單直觀得多。

以下是個(gè)典型的跳躍表例子：

從圖中可以看到，跳躍表主要由以下部分構(gòu)成：

• 表頭（head）：負(fù)責(zé)維護(hù)跳躍表的節(jié)點(diǎn)指針。
• 跳躍表節(jié)點(diǎn)：保存著元素值，以及多個(gè)層。
• 層：保存著指向其他元素的指針。高層的指針越過(guò)的元素?cái)?shù)量大于等于低層的指針，為了提高查找的效率，程序總是從高層先開(kāi)始訪問(wèn)，然后隨著元素值范圍的縮小，慢慢降低層次。
• 表尾：全部由 NULL 組成，表示跳躍表的末尾。

因?yàn)樘S表的定義可以在任何一本算法或數(shù)據(jù)結(jié)構(gòu)的書(shū)中找到，所以本章不介紹跳躍表的具體實(shí)現(xiàn)方式或者具體的算法，而只介紹跳躍表在 Redis 的應(yīng)用、核心數(shù)據(jù)結(jié)構(gòu)和 API 。

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

為了滿足自身的功能需要，Redis 基于 William Pugh 論文中描述的跳躍表進(jìn)行了以下修改：

1. 允許重復(fù)的 score 值：多個(gè)不同的 member 的 score 值可以相同。
2. 進(jìn)行對(duì)比操作時(shí)，不僅要檢查 score 值，還要檢查 member ：當(dāng) score 值可以重復(fù)時(shí)，單靠 score 值無(wú)法判斷一個(gè)元素的身份，所以需要連 member 域都一并檢查才行。
3. 每個(gè)節(jié)點(diǎn)都帶有一個(gè)高度為 1 層的后退指針，用于從表尾方向向表頭方向迭代：當(dāng)執(zhí)行 ZREVRANGE 或 ZREVRANGEBYSCORE 這類以逆序處理有序集的命令時(shí)，就會(huì)用到這個(gè)屬性。

這個(gè)修改版的跳躍表由 redis.h/zskiplist 結(jié)構(gòu)定義：

typedef struct zskiplist {

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

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

    // 目前表內(nèi)節(jié)點(diǎn)的最大層數(shù)
    int level;

} zskiplist;

跳躍表的節(jié)點(diǎn)由 redis.h/zskiplistNode 定義：

typedef struct zskiplistNode {

    // member 對(duì)象
    robj *obj;

    // 分值
    double score;

    // 后退指針
    struct zskiplistNode *backward;

    // 層
    struct zskiplistLevel {

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

        // 這個(gè)層跨越的節(jié)點(diǎn)數(shù)量
        unsigned int span;

    } level[];

} zskiplistNode;

以下是操作這兩個(gè)數(shù)據(jù)結(jié)構(gòu)的 API ，API 的用途與相應(yīng)的算法復(fù)雜度：

跳躍表的應(yīng)用

和字典、鏈表或者字符串這幾種在 Redis 中大量使用的數(shù)據(jù)結(jié)構(gòu)不同，跳躍表在 Redis 的唯一作用，就是實(shí)現(xiàn)有序集數(shù)據(jù)類型。

跳躍表將指向有序集的 score 值和 member 域的指針作為元素，并以 score 值為索引，對(duì)有序集元素進(jìn)行排序。

舉個(gè)例子，以下代碼創(chuàng)建了一個(gè)帶有 3 個(gè)元素的有序集：

redis> ZADD s 6 x 10 y 15 z
(integer) 3

redis> ZRANGE s 0 -1 WITHSCORES
1) "x"
2) "6"
3) "y"
4) "10"
5) "z"
6) "15"

在底層實(shí)現(xiàn)中，Redis 為 x 、 y 和 z 三個(gè) member 分別創(chuàng)建了三個(gè)字符串，值分別為 double 類型的 6 、 10 和 15 ，然后用跳躍表將這些指針有序地保存起來(lái)，形成這樣一個(gè)跳躍表：

zskipNode\n(head) |<3> |<2> |<1> |score\n NULL |robj\n NULL", fillcolor = "#F2F2F2"]; six [label = "zskipNode |<3> |<2> |<1> |score\n 6 |robj\n x", fillcolor = "#95BBE3"]; ten [label = "zskipNode | <1> |score\n 10 |robj\n y", fillcolor = "#95BBE3"]; fiften [label = "zskipNode |<3> |<2> |<1> |score\n 15 |robj\n z", fillcolor = "#95BBE3"]; skiplist:3 -> six:3; skiplist:2 -> six:2; skiplist:1 -> six:1; six:1 -> ten:1; six:2 -> fiften:2; six:3 -> fiften:3; ten:1 -> fiften:1; null_1 [label = "NULL", shape=plaintext]; null_2 [label = "NULL", shape=plaintext]; null_3 [label = "NULL", shape=plaintext]; fiften:1 -> null_1; fiften:2 -> null_2; fiften:3 -> null_3;}" />

為了方便展示，在圖片中我們直接將 member 和 score 值包含在表節(jié)點(diǎn)中，但是在實(shí)際的定義中，因?yàn)樘S表要和另一個(gè)實(shí)現(xiàn)有序集的結(jié)構(gòu)（字典）分享 member 和 score 值，所以跳躍表只保存指向 member 和 score 的指針。更詳細(xì)的信息，請(qǐng)參考《有序集》章節(jié)。

小結(jié)

• 跳躍表是一種隨機(jī)化數(shù)據(jù)結(jié)構(gòu)，查找、添加、刪除操作都可以在對(duì)數(shù)期望時(shí)間下完成。
• 跳躍表目前在 Redis 的唯一作用，就是作為有序集類型的底層數(shù)據(jù)結(jié)構(gòu)（之一，另一個(gè)構(gòu)成有序集的結(jié)構(gòu)是字典）。
• 為了滿足自身的需求，Redis 基于 William Pugh 論文中描述的跳躍表進(jìn)行了修改，包括：

1. score 值可重復(fù)。
2. 對(duì)比一個(gè)元素需要同時(shí)檢查它的 score 和 memeber 。
3. 每個(gè)節(jié)點(diǎn)帶有高度為 1 層的后退指針，用于從表尾方向向表頭方向迭代。