前言

在 Redis 中，Sorted Set（有序集合） 是一種非常重要且高效的數(shù)據(jù)結(jié)構(gòu)。與普通的 Set 不同，Sorted Set 為每個元素關(guān)聯(lián)了一個分?jǐn)?shù)（score），并按照這個分?jǐn)?shù)進行排序。在許多需要快速插入、刪除、查找和范圍查詢的場景下，Sorted Set 提供了理想的解決方案。而其底層的核心數(shù)據(jù)結(jié)構(gòu)之一便是 跳表（Skip List），這種結(jié)構(gòu)有效地支持了有序集合的高效操作。

本文將深入剖析跳表的實現(xiàn)原理，并通過 Redis 中 Sorted Set 的具體案例進行分析，幫助你更好地理解 Redis Sorted Set 的強大性能來源。

什么是跳表？

跳表（Skip List）是一種 平衡數(shù)據(jù)結(jié)構(gòu)，它通過多級索引加快了查找操作的效率，最早由 William Pugh 在 1990 年提出。它的時間復(fù)雜度與平衡二叉樹類似，均為 O(log n)，但跳表的實現(xiàn)相對簡單，操作靈活。

跳表的基本思想是通過在鏈表基礎(chǔ)上建立多層索引，提升數(shù)據(jù)的查找效率。每一層都是下一層的 “縮略圖”，這樣在查找時，能通過跳躍方式快速逼近目標(biāo)元素。

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

跳表的結(jié)構(gòu)類似于多層鏈表：

• 第一層 是完整的有序鏈表，所有數(shù)據(jù)都在這一層。
• 第二層及以上 則是對部分?jǐn)?shù)據(jù)的抽象，使得每一層的數(shù)據(jù)量逐步減少，但依然保持有序。

每個元素會以一定概率決定是否提升到上層。因此，跳表有多條指向不同節(jié)點的指針，最低層類似普通鏈表，而上層指針可以跨越多個節(jié)點。

跳表的時間復(fù)雜度

在最優(yōu)情況下，跳表通過減少層數(shù)并允許跳躍式查找，平均查找、插入和刪除的時間復(fù)雜度都為 O(log n)，空間復(fù)雜度為 O(n)。這種特性使得跳表非常適合用于實現(xiàn)有序集合，尤其是像 Redis 這樣要求高效范圍查詢的場景。

Redis 中的 Sorted Set

Redis 的 Sorted Set 是通過兩個核心數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的：

• 跳表（Skip List）：用于按照分?jǐn)?shù)（score）排序元素，支持按順序查找、范圍查找等操作。
• 哈希表：用于根據(jù)元素的唯一標(biāo)識符（member）快速定位元素，避免重復(fù)插入。

Redis 通過這兩種數(shù)據(jù)結(jié)構(gòu)的結(jié)合，實現(xiàn)了有序集合的高效性和靈活性。

Sorted Set 的存儲結(jié)構(gòu)

Redis Sorted Set 的存儲結(jié)構(gòu)是 zset，它內(nèi)部由一個 dict 和一個 zskiplist 組成：

• dict：保存成員和對應(yīng)分?jǐn)?shù)的映射關(guān)系，確保成員唯一性，插入和刪除操作時間復(fù)雜度為 O(1)。
• zskiplist：用于按分?jǐn)?shù)排序的跳表，支持按分?jǐn)?shù)范圍查找、范圍刪除等操作，時間復(fù)雜度為 O(log n)。

這種設(shè)計確保了插入、刪除和范圍查詢等操作在高效性和穩(wěn)定性上的平衡。

跳表在 Redis Sorted Set 中的實現(xiàn)

1. 跳表節(jié)點（zskiplistNode）

在 Redis 中，每個跳表節(jié)點不僅包含元素的分?jǐn)?shù)和成員信息，還包含多個指向其他節(jié)點的指針，用于支持多層索引的實現(xiàn)。Redis 中 zskiplistNode 的定義如下：

typedef struct zskiplistNode {
    sds ele;  // 成員（member）
    double score;  // 分?jǐn)?shù)（score）
    struct zskiplistNode *backward;  // 后退指針，用于反向遍歷
    struct zskiplistLevel {
        struct zskiplistNode *forward;  // 前進指針，指向下一節(jié)點
        unsigned int span;  // 跨度，用于快速定位節(jié)點
    } level[];  // 每個節(jié)點的多層指針
} zskiplistNode;

• ele：保存成員數(shù)據(jù)。
• score：保存對應(yīng)成員的分?jǐn)?shù)。
• backward：用于反向遍歷，支持雙向鏈表的功能。
• level：是一個數(shù)組，每個元素對應(yīng)一層，保存指向下一個節(jié)點的指針。

2. 跳表結(jié)構(gòu)（zskiplist）

Redis 中的 zskiplist 結(jié)構(gòu)表示整個跳表，它由頭節(jié)點、尾節(jié)點、最大層數(shù)和節(jié)點總數(shù)組成：

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

3. 插入操作

插入新元素時，跳表通過從高層向低層逐層查找插入位置，并將新節(jié)點插入到相應(yīng)層級的鏈表中。每插入一個新節(jié)點時，會隨機決定它提升到哪一層，這種隨機性保證了跳表的平衡性。

Redis 使用的隨機層數(shù)生成算法如下：

int zslRandomLevel(void) {
    int level = 1;
    while ((random() & 0xFFFF) < (0.25 * 0xFFFF)) {
        level += 1;
    }
    return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

zslRandomLevel 函數(shù)根據(jù)概率隨機生成節(jié)點的層數(shù)，使得跳表在理論上能夠保持 log 級別的復(fù)雜度。

插入示例：

假設(shè)我們向 Redis 中的 Sorted Set 插入一個元素：

ZADD myzset 1 "apple"

• Redis 首先通過隨機算法為該元素分配一個層數(shù)。
• 然后，從最高層逐步查找合適的插入點，依次更新前后節(jié)點的指針，完成插入。

4. 查找操作

跳表的查找操作通過從上到下逐層遍歷實現(xiàn)。每一層跳過若干節(jié)點進行快速查找，直到在最低層找到目標(biāo)元素。由于跳表的層級設(shè)計，查找操作的時間復(fù)雜度為 O(log n)。

查找示例：

例如，我們要查詢分?jǐn)?shù)為 3 的元素：

ZRANGE myzset 3 3

跳表將從最高層開始，跳過一部分節(jié)點，快速找到分?jǐn)?shù)為 3 的節(jié)點。

5. 刪除操作

刪除元素時，跳表會先找到目標(biāo)元素所在的位置，然后從每一層中移除節(jié)點。為了保持?jǐn)?shù)據(jù)結(jié)構(gòu)的平衡，刪除時會調(diào)整各層級指針，并在必要時降低跳表的層數(shù)。

刪除示例：

假設(shè)我們刪除 myzset 中分?jǐn)?shù)為 2 的元素：

ZREM myzset "banana"

跳表會從頭節(jié)點開始，逐層找到 banana 所在的位置，并移除該元素，同時更新前后節(jié)點的指針關(guān)系。

Redis 跳表的優(yōu)勢與局限

優(yōu)勢

• 高效的范圍查詢：跳表通過分層索引，可以快速完成范圍查找、排名等操作。
• 插入、刪除操作高效：跳表保持了 O(log n) 的插入和刪除復(fù)雜度，適合大規(guī)模數(shù)據(jù)的動態(tài)增刪。
• 實現(xiàn)簡單：相比平衡樹，跳表結(jié)構(gòu)相對簡單，更易于實現(xiàn)和維護。

局限

• 內(nèi)存占用：跳表需要為每個節(jié)點維護多層指針，在內(nèi)存占用上相對鏈表較大。
• 隨機性導(dǎo)致的性能波動：由于跳表使用隨機算法決定節(jié)點層數(shù)，可能導(dǎo)致性能出現(xiàn)波動，雖然這種概率極低。

總結(jié)

Redis 中的跳表作為 Sorted Set 的核心數(shù)據(jù)結(jié)構(gòu)，提供了高效的排序、插入、刪除以及范圍查找等功能。通過跳表的多層索引機制，Redis 在處理有序集合時能夠維持 O(log n) 的時間復(fù)雜度，同時結(jié)合哈希表確保了成員的唯一性和快速訪問。

跳表的設(shè)計簡單卻強大，是 Redis 高性能的關(guān)鍵之一。在理解了其實現(xiàn)原理后，我們可以更好地運用 Redis 的 Sorted Set，優(yōu)化高并發(fā)環(huán)境中的數(shù)據(jù)查詢與操作。

如果你在構(gòu)建需要排序、范圍查詢或動態(tài)調(diào)整的數(shù)據(jù)系統(tǒng)時，Redis 的 Sorted Set 和跳表的組合無疑是一個值得選擇的高效解決方案。

到此這篇關(guān)于Redis Sorted Set 跳表的實現(xiàn)示例的文章就介紹到這了,更多相關(guān)Redis Sorted Set 跳表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論