前言

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

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

什么是跳表？

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

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

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

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

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

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

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

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

Redis 中的 Sorted Set

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. 插入操作

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

Redis 使用的隨機(jī)層數(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ù)概率隨機(jī)生成節(jié)點(diǎn)的層數(shù)，使得跳表在理論上能夠保持 log 級(jí)別的復(fù)雜度。

插入示例：

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

ZADD myzset 1 "apple"

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

4. 查找操作

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

查找示例：

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

ZRANGE myzset 3 3

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

5. 刪除操作

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

刪除示例：

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

ZREM myzset "banana"

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

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

優(yōu)勢(shì)

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

局限

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

總結(jié)

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

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

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

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

最新評(píng)論