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

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

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

以下是本篇筆記目錄：

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

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

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

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

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

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

跳躍表節(jié)點(diǎn)結(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;

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

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

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

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

a) header

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

b) tail

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

c) level

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

d) length

length 屬性表示的是跳躍表節(jié)點(diǎn)的個(gè)數(shù)，也就是跳躍表的長(zhǎng)度。

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

跳躍表節(jié)點(diǎn)的各個(gè)屬性如下：

a) obj

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

b) score

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

c) backward

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

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

d) skiplistLevel

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

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

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

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

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

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

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

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

5、跳躍表的查詢過程

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

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

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

最新評(píng)論