為什么需要 SkipList（跳表）

在普通鏈表中查找元素的時候，因為需要遍歷查找，所以查詢效率非常低，時間復(fù)雜度是O(N)。

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

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

如下圖所示，這是一個層級為3的跳表

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

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

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

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

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

跳表的節(jié)點（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，用于存儲該節(jié)點的元素
• score，用于存儲節(jié)點的分?jǐn)?shù)（節(jié)點按照 score 值排序，score 值一樣則按照 ele 排序）
• *backward，指向上一個節(jié)點

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

?? span 跨度有什么用？

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

跳表（zskiplist ）

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

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

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

跳表的查詢過程

在使用 ZRANGEBYSCORE key min max進行范圍查詢的時候

• redis 會調(diào)用 zslFirstInRange 或 zslLastInRange 函數(shù)獲取符合范圍條件的起始節(jié)點（正序調(diào)用**zslFirstInRange** ，逆序調(diào)用**zslLastInRange** ）
• 獲取起始節(jié)點之后，進入一個循環(huán)，每次迭代時都會檢查節(jié)點的分?jǐn)?shù)是否仍在范圍內(nèi)（如果存在偏移量，跳過指定數(shù)量的元素，而不進行分?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ù)檢查整個有序集合是否都在范圍之外，如果是，則直接返回空，表示范圍內(nèi)不存在滿足條件的節(jié)點。
• 初始化變量 x 為跳表的頭節(jié)點。
• 從跳表的最高層級開始逆序遍歷每個層級，直到達到最底層級。
• 在每個層級中，通過比較節(jié)點的分?jǐn)?shù)（score）和范圍的最小值，向前遍歷跳表，直到找到第一個在范圍內(nèi)的節(jié)點。
• 最終，變量 x 存儲的是范圍內(nèi)第一個節(jié)點的前一個節(jié)點。
• 使用 serverAssert 函數(shù)進行斷言，確保變量 x 的下一個節(jié)點不為空（如果跳表中存在節(jié)點，則下一個節(jié)點不應(yīng)為空）。
• 更新變量 x 為下一個節(jié)點，即范圍內(nèi)的第一個滿足條件的節(jié)點。
• 檢查變量 x 的score 是否小于等于范圍的最大值，如果大于最大值，則返回空，表示范圍內(nèi)不存在滿足條件的節(jié)點。
• 返回變量 x，即范圍內(nèi)的第一個滿足條件的節(jié)點。

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

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

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

最新評論