引言：為什么 Redis 選擇跳表？

在有序集合（ZSET）的實現(xiàn)中，Redis 開發(fā)者面臨一個關(guān)鍵抉擇：如何在高性能讀寫和代碼簡潔性之間找到平衡？傳統(tǒng)平衡樹（如紅黑樹）雖然能保證 O(logN) 時間復(fù)雜度，但實現(xiàn)復(fù)雜且難以支持范圍查詢。跳表（Skip List） 以媲美平衡樹的性能、極簡的實現(xiàn)（約 200 行代碼）和天然支持范圍查詢的特性，成為 Redis ZSET 的核心數(shù)據(jù)結(jié)構(gòu)。本文將深入剖析跳表的實現(xiàn)細節(jié)與 Redis 的工程優(yōu)化。

一、跳表核心思想：概率化的多層索引

1.1 從鏈表到跳表的進化

• 普通鏈表：插入/刪除 O(1)，但查詢需要 O(N)
• 跳表創(chuàng)新：通過隨機化多層索引，實現(xiàn)對數(shù)級查詢效率

1.2 跳表結(jié)構(gòu)可視化

Level 3: Head -> 37 --------------------------> 99 -> NULL  
Level 2: Head -> 37 -------> 71 -------> 99 -> NULL  
Level 1: Head -> 37 -> 55 -> 71 -> 85 -> 99 -> NULL  
Level 0: Head -> 37 -> 55 -> 71 -> 85 -> 99 -> NULL  

關(guān)鍵特性：

每個節(jié)點隨機生成層數(shù)（Redis 最大層數(shù) 64）

高層索引跨越更多節(jié)點，加速搜索

底層鏈表存儲完整數(shù)據(jù)

二、Redis 跳表實現(xiàn)深度解剖

2.1 數(shù)據(jù)結(jié)構(gòu)定義（redis.h）

// 跳表節(jié)點
typedef struct zskiplistNode {
    sds ele;                          // 成員對象（SDS字符串）
    double score;                     // 排序分值
    struct zskiplistNode *backward;   // 后退指針（雙向鏈表）
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前進指針
        unsigned long span;            // 跨度（用于排名計算）
    } level[];                        // 柔性數(shù)組，層級隨機生成
} zskiplistNode;

// 跳表結(jié)構(gòu)
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;             // 節(jié)點總數(shù)
    int level;                        // 當前最大層數(shù)
} zskiplist;

設(shè)計亮點：

• span 字段：記錄節(jié)點在某一層的跨度，支持 O(1) 時間復(fù)雜度計算元素排名（ZRANK）
• backward 指針：構(gòu)成雙向鏈表，支持逆序遍歷
• 柔性數(shù)組（level[]）：內(nèi)存緊湊，避免指針冗余

2.2 關(guān)鍵操作源碼解析

2.2.1 節(jié)點層數(shù)生成算法

// redis.h 源碼節(jié)選
int zslRandomLevel(void) {
    int level = 1;
    // 0xFFFF 對應(yīng) 1/4 概率提升層級（基于位運算優(yōu)化）
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

數(shù)學(xué)原理：

• 使用 冪次定律（Power Law），高層節(jié)點指數(shù)級減少
• 每個節(jié)點有 50% 概率進入 L1，25% 進入 L2，12.5% 進入 L3...
• Redis 實際使用 1/4 的概率因子（優(yōu)化內(nèi)存與性能平衡）

2.2.2 插入節(jié)點流程（zslInsert）

• 搜索路徑記錄：從最高層開始，記錄每層的前驅(qū)節(jié)點和跨度
• 生成隨機層數(shù)：調(diào)用 zslRandomLevel
• 創(chuàng)建新節(jié)點：分配層級并連接前后指針
• 更新跨度：調(diào)整相鄰節(jié)點的 span 值
• 維護后退指針：設(shè)置新節(jié)點的 backward 指針

2.2.3 范圍查詢（ZRANGEBYSCORE）

• 從高層索引快速定位起點
• 利用底層鏈表遍歷范圍
• 復(fù)雜度：O(logN + M)（M 為返回元素數(shù)量）

三、性能分析與優(yōu)化策略

3.1 時間復(fù)雜度對比

注：跳表最壞情況（所有節(jié)點高度相同）概率極低（例如 1億節(jié)點出現(xiàn)概率為 1/(2^50)）

3.2 內(nèi)存占用分析

• 理論空間復(fù)雜度：O(NlogN)
• Redis 優(yōu)化實踐：通過 1/4 概率因子，實際空間占用約為 O(1.33N)（實測 100 萬節(jié)點內(nèi)存約 64MB）

3.3 調(diào)優(yōu)參數(shù)

• ZSKIPLIST_MAXLEVEL：控制最大層數(shù)（默認 64，可調(diào)整內(nèi)存與性能平衡）
• ZSKIPLIST_P：調(diào)整層數(shù)生成概率（默認 0.25）

四、跳表在 Redis 中的應(yīng)用場景

4.1 有序集合（ZSET）

元素數(shù)量 > 128 或 元素長度 > 64 字節(jié) 時，ZSET 內(nèi)部使用跳表

支持操作：

• ZADD/ZREM：插入刪除
• ZRANK/ZSCORE：排名查詢
• ZRANGE：范圍查詢

4.2 集群元數(shù)據(jù)管理

用于維護槽位（slot）與節(jié)點的映射關(guān)系

五、跳表 vs 平衡樹：工程角度的選擇

Redis 作者 Antirez 的評價：“跳表在理論上不如平衡樹優(yōu)雅，但實際工程中更簡單、更快，尤其適合需要范圍查詢的場景。”

總結(jié)：

跳表的精妙之處在于 用概率換結(jié)構(gòu)，通過隨機化層級分布避免復(fù)雜的再平衡操作。這種“以空間換時間” + “以概率換簡單性”的設(shè)計哲學(xué)，在分布式系統(tǒng)開發(fā)中具有重要借鑒意義。理解跳表不僅有助于掌握 Redis 源碼，更能啟發(fā)我們思考如何在高性能與可維護性之間找到平衡。

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

最新評論