為什么需要 SkipList（跳表）

在普通鏈表中查找元素的時(shí)候，因?yàn)樾枰闅v查找，所以查詢效率非常低，時(shí)間復(fù)雜度是O(N)。

因此我們需要跳表。跳表是在鏈表基礎(chǔ)上改進(jìn)過來的，實(shí)現(xiàn)了一種 “多層” 的 有序 鏈表，這樣的好處是能快速定位數(shù)據(jù)。

跳表的結(jié)構(gòu)設(shè)計(jì)

如下圖所示，這是一個(gè)層級(jí)為3的跳表

和普通的雙向鏈表一樣，SkipList 都有一個(gè)指向上一個(gè)節(jié)點(diǎn)的指針，也有一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針。

但是你會(huì)發(fā)現(xiàn)，在層次為 3 的跳表中，會(huì)有三級(jí)指針的存在，而且 SkipList 中元素會(huì)按照 score 值升序排序（score 值一樣則按照 ele 排序）

• 一級(jí)指針普通鏈表一樣，指向下一個(gè)節(jié)點(diǎn)（圖中的 L0）
• 二級(jí)指針跨度為2，指向的節(jié)點(diǎn)與自己間隔了一個(gè)節(jié)點(diǎn)
• 三級(jí)指針跨度為3，指向的節(jié)點(diǎn)與自己間隔了兩個(gè)節(jié)點(diǎn)

這樣的設(shè)計(jì)會(huì)帶來什么好處呢？

• 假設(shè)我們要在普通鏈表中查詢值為 3 的節(jié)點(diǎn)，我們需要從頭結(jié)點(diǎn)開始，向后遍歷1 → 2 → 3 ，三個(gè)節(jié)點(diǎn)才能找到。時(shí)間復(fù)雜度為 O(n)
• 當(dāng)使用了 SkipList 這個(gè)數(shù)據(jù)結(jié)構(gòu)之后，我們可以直接通過三級(jí)指針（L2），直接找到這個(gè)節(jié)點(diǎn)（建立在元素有序的情況下，類似于二分查找一步一步縮小范圍）。時(shí)間復(fù)雜度為 O(logN)

跳表的節(jié)點(diǎn)（zskiplistNode ）

我們來看看跳表的結(jié)構(gòu)體源碼

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

其中，

• ele，用于存儲(chǔ)該節(jié)點(diǎn)的元素
• score，用于存儲(chǔ)節(jié)點(diǎn)的分?jǐn)?shù)（節(jié)點(diǎn)按照 score 值排序，score 值一樣則按照 ele 排序）
• *backward，指向上一個(gè)節(jié)點(diǎn)

而 level[] 就是實(shí)現(xiàn)跳表多層次指針的關(guān)鍵所在，level 數(shù)組中的每一個(gè)元素代表跳表的一層，比如 leve[0] 就表示第一層，leve[1] 就表示第二層。zskiplistLevel 結(jié)構(gòu)體里定義了指向下一個(gè)跳表節(jié)點(diǎn)的指針** *forward 和用來記錄兩個(gè)節(jié)點(diǎn)之間的距離 span，如圖所示，

?? span 跨度有什么用？

• 第一眼看到跨度的時(shí)候，你可能以為是遍歷操作有關(guān)，實(shí)際上并沒有任何關(guān)系，遍歷操作只需要用前向指針（struct zskiplistNode *forward）就可以完成了。
• 跨度實(shí)際上是為了計(jì)算這個(gè)節(jié)點(diǎn)在跳表中的位置。具體怎么做的呢？
• 因?yàn)樘碇械墓?jié)點(diǎn)都是按序排列的，那么計(jì)算某個(gè)節(jié)點(diǎn)位置的時(shí)候，從頭節(jié)點(diǎn)點(diǎn)到該結(jié)點(diǎn)的查詢路徑上，將沿途訪問過的所有層的跨度累加起來，得到的結(jié)果就是目標(biāo)節(jié)點(diǎn)在跳表中的排位。
• 舉個(gè)例子，查找圖中節(jié)點(diǎn) 3 在跳表中的排位，從頭節(jié)點(diǎn)開始查找節(jié)點(diǎn) 3，查找的過程只經(jīng)過了一個(gè)層（L2），并且層的跨度是 3，所有節(jié)點(diǎn) 3 在跳表中的排位是 3。

跳表（zskiplist ）

跳表的結(jié)構(gòu)如下

    typedef struct zskiplist {
        struct zskiplistNode *header, *tail;
        unsigned long length;
        int level;
    } zskiplist;

• zskiplistNode *header, *tail ，跳表的頭尾節(jié)點(diǎn)
• length，跳表的長度
• level，跳表的最大層數(shù)

跳表的查詢過程

在使用 ZRANGEBYSCORE key min max進(jìn)行范圍查詢的時(shí)候

• redis 會(huì)調(diào)用 zslFirstInRange 或 zslLastInRange 函數(shù)獲取符合范圍條件的起始節(jié)點(diǎn)（正序調(diào)用**zslFirstInRange** ，逆序調(diào)用**zslLastInRange** ）
• 獲取起始節(jié)點(diǎn)之后，進(jìn)入一個(gè)循環(huán)，每次迭代時(shí)都會(huì)檢查節(jié)點(diǎn)的分?jǐn)?shù)是否仍在范圍內(nèi)（如果存在偏移量，跳過指定數(shù)量的元素，而不進(jìn)行分?jǐn)?shù)的檢查），如果不在范圍內(nèi)，則中止循環(huán)。
• 這樣就能獲取指定分?jǐn)?shù)內(nèi)的所有元素。

可在 t_zset.c#genericZrangebyscoreCommand(zrange_result_handler *handler, zrangespec *range, robj *zobj, long offset, long limit, int reverse) 查看源碼

在 zslFirstInRange （zslLastInRange 類似）中，我們就能看到跳表根據(jù) scroe 值的查詢過程，源碼如下：

    /* Find the first node that is contained in the specified range.
     * Returns NULL when no element is contained in the range. */
    zskiplistNode *zslFirstInRange(zskiplist *zsl, zrangespec *range) {
        zskiplistNode *x;
        int i;
        /* If everything is out of range, return early. */
        if (!zslIsInRange(zsl,range)) return NULL;
        x = zsl->header;
        for (i = zsl->level-1; i >= 0; i--) {
            /* Go forward while *OUT* of range. */
            while (x->level[i].forward &&
                !zslValueGteMin(x->level[i].forward->score,range))
                    x = x->level[i].forward;
        }
        /* This is an inner range, so the next node cannot be NULL. */
        x = x->level[0].forward;
        serverAssert(x != NULL);
        /* Check if score <= max. */
        if (!zslValueLteMax(x->score,range)) return NULL;
        return x;
    }

該函數(shù)執(zhí)行邏輯如下：

• 首先，通過調(diào)用 zslIsInRange 函數(shù)檢查整個(gè)有序集合是否都在范圍之外，如果是，則直接返回空，表示范圍內(nèi)不存在滿足條件的節(jié)點(diǎn)。
• 初始化變量 x 為跳表的頭節(jié)點(diǎn)。
• 從跳表的最高層級(jí)開始逆序遍歷每個(gè)層級(jí)，直到達(dá)到最底層級(jí)。
• 在每個(gè)層級(jí)中，通過比較節(jié)點(diǎn)的分?jǐn)?shù)（score）和范圍的最小值，向前遍歷跳表，直到找到第一個(gè)在范圍內(nèi)的節(jié)點(diǎn)。
• 最終，變量 x 存儲(chǔ)的是范圍內(nèi)第一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。
• 使用 serverAssert 函數(shù)進(jìn)行斷言，確保變量 x 的下一個(gè)節(jié)點(diǎn)不為空（如果跳表中存在節(jié)點(diǎn)，則下一個(gè)節(jié)點(diǎn)不應(yīng)為空）。
• 更新變量 x 為下一個(gè)節(jié)點(diǎn)，即范圍內(nèi)的第一個(gè)滿足條件的節(jié)點(diǎn)。
• 檢查變量 x 的score 是否小于等于范圍的最大值，如果大于最大值，則返回空，表示范圍內(nèi)不存在滿足條件的節(jié)點(diǎn)。
• 返回變量 x，即范圍內(nèi)的第一個(gè)滿足條件的節(jié)點(diǎn)。

簡單來說在 SkipList 中找到一個(gè)元素的步驟如下：

• 從跳表的頂層開始，從左到右遍歷指針，直到找到一個(gè)指針指向的值大于或等于目標(biāo)元素。記錄下該位置作為當(dāng)前位置。
• 如果當(dāng)前位置指向的值等于目標(biāo)元素，則找到了目標(biāo)元素，搜索結(jié)束。
• 如果當(dāng)前位置的下一個(gè)指針存在且指向的值小于目標(biāo)元素，將當(dāng)前位置向右移動(dòng)到下一個(gè)指針?biāo)赶虻奈恢?。重?fù)步驟1。
• 如果當(dāng)前位置的下一個(gè)指針不存在或指向的值大于目標(biāo)元素，將當(dāng)前位置向下移動(dòng)一層。重復(fù)步驟1。

到此這篇關(guān)于Redis底層數(shù)據(jù)結(jié)構(gòu)SkipList的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Redis SkipList內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論