Redis跳躍表結(jié)構(gòu)

跳躍表結(jié)構(gòu)是有序集合的底層實現(xiàn)之一，它通過在每個節(jié)點中維持多個指向其他節(jié)點的指針，從而達(dá)到快速訪問節(jié)點的目的。

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

以下是本篇筆記目錄：

• 跳躍表及跳躍表節(jié)點結(jié)構(gòu)
• 跳躍表屬性
• 跳躍表節(jié)點屬性
• 跳躍表節(jié)點層(level)的生成
• 跳躍表的查詢過程

1、跳躍表及跳躍表節(jié)點結(jié)構(gòu)

接下來介紹一下跳躍表和跳躍表節(jié)點結(jié)構(gòu)。

跳躍表結(jié)構(gòu)：

typedef struct zskiplist{
    // 表頭節(jié)點和表尾節(jié)點
    struct skiplistNode *header, *tail;
    // 表中節(jié)點的數(shù)量
    unsigned long length;
    // 表中層數(shù)最大的節(jié)點的層數(shù)
    int level;
} zskiplist;

跳躍表結(jié)構(gòu)中包含指向表頭和表尾的指針，以及 length 字段表示表中節(jié)點的數(shù)量，level 字段則是表示所有跳躍表節(jié)點中最大的節(jié)點層數(shù)，層數(shù)的概念在跳躍表節(jié)點結(jié)構(gòu)中再詳細(xì)說明。

跳躍表節(jié)點結(jié)構(gòu)：

typedef struct zskiplistNode{
    // 后退指針
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成員對象
    robj *obj;
    // 層
    struct zskiplistLevel {
        // 前進(jìn)指針
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level [];
} zskiplistNode;

我們可以將跳躍表理解成鏈表，不過鏈表上的每個節(jié)點都有指向前面一個節(jié)點的指針和多個指向后面某些節(jié)點的指針，指向后面的指針以數(shù)組的形式存在。

接下來我們以一張圖來示意一下跳躍表及其節(jié)點之間的關(guān)系。

2、跳躍表結(jié)構(gòu)

在上面的偽代碼示例和上圖結(jié)構(gòu)中，可以看到一個跳躍表結(jié)構(gòu)如下幾個屬性：

a) header

header 是跳躍表的頭節(jié)點指針，可以快速定位跳躍表的頭節(jié)點

b) tail

tail 是跳躍表的尾部節(jié)點指針，可以快速定位跳躍表的尾部節(jié)點

c) level

level 表示的是跳躍表節(jié)點中層數(shù)最高的數(shù)值，比如在圖中第三個跳躍表節(jié)點的層數(shù)最高，數(shù)值是 5，所以跳躍表的這個值是 5。

d) length

length 屬性表示的是跳躍表節(jié)點的個數(shù)，也就是跳躍表的長度。

3、跳躍表節(jié)點結(jié)構(gòu)

跳躍表節(jié)點的各個屬性如下：

a) obj

節(jié)點的成員對象，見圖中的，o1，o2，o3，是一個指針，指向一個字符串對象，字符串對象保存著一個 SDS 值，就是有序集合中存儲的數(shù)值。

b) score

有序集合用來進(jìn)行排序的分值，有序集合通過這個屬性用來對集合的元素進(jìn)行排序，保存的是 double 類型的浮點數(shù)，在跳躍表中，所有節(jié)點按照分值從小到大來排序。

c) backward

后退指針，跳躍表的每個節(jié)點通過這個屬性指向前一個節(jié)點，用于從表尾向表頭方向訪問節(jié)點。

圖中展示了如何從表尾向跳躍表的頭節(jié)點遍歷的過程：通過 tail 指針指向跳躍表的尾部節(jié)點，然后通過 backward 后退指針逐個往前遍歷，直到第一個節(jié)點的 backward 為 NULL 表示遍歷結(jié)束。

d) skiplistLevel

skiplistLevel 是跳躍表節(jié)點的層，層數(shù)介于 1 到 32 之間，每個層的都包含兩個屬性，前進(jìn)指針和跨度。

前進(jìn)指針：forward，指向同一層級的下一個跳躍表節(jié)點

跨度：span，用于記錄到同層級的下一個節(jié)點之間的距離，比如第一個節(jié)點的第四層級，下一個節(jié)點的第四層級是第三個節(jié)點，因此，o1 的第四層級的的跨度是 2。

4、跳躍表節(jié)點層(level)介紹

前面介紹跳躍表節(jié)點的層屬性是一個數(shù)組，包含多個指向下一個同一層級的指針，而每個節(jié)點層的大小則是根據(jù)冪次定律(power law) 來生成的。

在創(chuàng)建一個跳躍表節(jié)點的時候，程序都會根據(jù)冪次定律隨機生成一個介于 1 到 32 之間的值作為 level 數(shù)組的大小，這個規(guī)則是越大的數(shù)出現(xiàn)的概率越小，它有一種計算方式，層數(shù)每加 1，出現(xiàn)的概率都是前一個數(shù)字的 0.25。

比如 level = 1 的概率是 0.75，那么 level = 2 的概率是 0.75 0.25，level = 3 的概率則是 0.75 0.25 * 0.25，直到最高層數(shù)

所以每個跳躍表節(jié)點的層數(shù)都是隨機的，跟這個節(jié)點在跳躍表的前后位置無關(guān)。

5、跳躍表的查詢過程

以上面的圖為例，比如我們想查詢 score 為 2.0 的 o2 節(jié)點，那么查詢的過程是這樣的：

• 首先根據(jù)頭節(jié)點的最高一層節(jié)點，在圖中是 L5，L5 指向的是 o3 節(jié)點，o3 節(jié)點的分值比目標(biāo)分值 2.0 大，舍棄
• 頭節(jié)點往下降一層，到 L4，L4 指向下個節(jié)點 o1，o1的 score 比 2.0 小，跳到 o1 節(jié)點，繼續(xù)查詢
• o1 節(jié)點的 L4 指向的下一節(jié)點是 o3，o3 的 score 比 2.0 大，舍棄，o1 的 L4 繼續(xù)下降一層
• o1 節(jié)點的 L3 節(jié)點指向的 o3 還是不符合條件，繼續(xù)下降一層
• o1 節(jié)點的 L2 節(jié)點指向的 o2 節(jié)點，其分值滿足條件，而從 o1 到 o2 的跨度為 1 + 1 = 2

以上就是Redis數(shù)據(jù)結(jié)構(gòu)之跳躍表使用學(xué)習(xí)的詳細(xì)內(nèi)容，更多關(guān)于Redis數(shù)據(jù)結(jié)構(gòu)跳躍表的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論