Redis跳躍表的結構實現方法

# Redis跳躍表的結構實現方法

## 1. 引言

Redis作為高性能的鍵值數據庫，其有序集合（Sorted Set）的底層實現采用了跳躍表（Skip List）這一經典數據結構。跳躍表由William Pugh于1990年提出，通過構建多級索引的方式，在鏈表基礎上實現了接近平衡樹的查詢效率（O(log n)），同時保持了更簡單的實現和維護成本。

本文將深入剖析Redis跳躍表的結構設計與實現細節，包含以下內容：
- 跳躍表的基礎概念與優勢
- Redis跳躍表的具體結構定義
- 核心操作算法實現
- 性能分析與優化策略
- 實際應用場景示例

## 2. 跳躍表基礎概念

### 2.1 數據結構定義

跳躍表是由多層有序鏈表組成的概率型數據結構，具有以下特征：
- 最底層（L0）包含所有元素的有序鏈表
- 上層鏈表是下層的"快速通道"，元素按概率隨機晉升
- 頭節點（header）擁有完整的層級結構

### 2.2 與平衡樹的對比

| 特性               | 跳躍表                  | 平衡樹（如AVL/紅黑樹） |
|--------------------|-------------------------|-----------------------|
| 查詢復雜度         | O(log n)                | O(log n)              |
| 插入/刪除復雜度    | O(log n)                | O(log n)              |
| 實現難度           | 較簡單                  | 較復雜                |
| 范圍查詢效率       | 優（天然有序）          | 中                    |
| 內存占用           | 平均多50%左右           | 較少                  |
| 并發控制           | 更容易實現              | 較困難                |

## 3. Redis跳躍表實現細節

### 3.1 結構定義（Redis 6.2源碼）

```c
// 跳躍表節點
typedef struct zskiplistNode {
    sds ele;                            // 成員對象（SDS字符串）
    double score;                       // 排序分值
    struct zskiplistNode *backward;     // 后退指針
    struct zskiplistLevel {
        struct zskiplistNode *forward;   // 前進指針
        unsigned long span;              // 跨度（到下一個節點的距離）
    } level[];                          // 柔性數組實現多級索引
} zskiplistNode;

// 跳躍表容器
typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 頭尾節點指針
    unsigned long length;               // 節點數量
    int level;                          // 當前最大層數
} zskiplist;

3.2 關鍵設計特點

1. 分值排序：節點按score升序排列，相同score按字典序排列
2. 層級概率：Redis采用1/4的晉升概率（對比原始論文的1/2）
3. 最大層數：固定限制為32層（可存儲2^64元素）
4. 跨度記錄：每個層級維護span值，用于快速計算排名
5. 成員唯一性：通過ele確保元素唯一性

4. 核心操作實現

4.1 節點插入算法

def zslInsert(zsl, score, ele):
    # 1. 記錄搜索路徑
    update = [None] * ZSKIPLIST_MAXLEVEL
    rank = [0] * ZSKIPLIST_MAXLEVEL
    x = zsl.header
    
    # 2. 從最高層開始查找插入位置
    for i in range(zsl.level-1, -1, -1):
        rank[i] = 0 if i == zsl.level-1 else rank[i+1]
        while x.level[i].forward and (
            x.level[i].forward.score < score or 
            (x.level[i].forward.score == score and 
             compareStrings(x.level[i].forward.ele, ele) < 0)):
            rank[i] += x.level[i].span
            x = x.level[i].forward
        update[i] = x
    
    # 3. 隨機確定節點層數
    level = zslRandomLevel()
    if level > zsl.level:
        for i in range(zsl.level, level):
            rank[i] = 0
            update[i] = zsl.header
            update[i].level[i].span = zsl.length
        zsl.level = level
    
    # 4. 創建新節點
    x = zslCreateNode(level, score, ele)
    for i in range(level):
        x.level[i].forward = update[i].level[i].forward
        update[i].level[i].forward = x
        x.level[i].span = update[i].level[i].span - (rank[0] - rank[i])
        update[i].level[i].span = (rank[0] - rank[i]) + 1
    
    # 5. 調整上層跨度
    for i in range(level, zsl.level):
        update[i].level[i].span += 1
    
    # 6. 設置后退指針
    x.backward = update[0]
    if x.level[0].forward:
        x.level[0].forward.backward = x
    else:
        zsl.tail = x
    
    zsl.length += 1
    return x

4.2 隨機層數生成

Redis采用基于概率的冪次定律實現：

#define ZSKIPLIST_P 0.25      // 晉升概率

int zslRandomLevel(void) {
    int level = 1;
    // 0xFFFF = 65535, 每次有1/4概率晉升
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

4.3 范圍查詢（ZRANGE）

利用跳躍表的層級結構高效實現范圍查詢：

zskiplistNode* zslGetElementByRank(zskiplist *zsl, unsigned long rank) {
    zskiplistNode *x;
    unsigned long traversed = 0;
    int i;
    
    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        while (x->level[i].forward && 
              (traversed + x->level[i].span) <= rank) {
            traversed += x->level[i].span;
            x = x->level[i].forward;
        }
        if (traversed == rank) {
            return x;
        }
    }
    return NULL;
}

5. 性能優化策略

5.1 內存優化

1. 柔性數組：使用C99柔性數組（flexible array）實現動態層級
2. 共享元素：ele采用引用計數方式管理
3. 層級限制：32層最大限制避免極端情況

5.2 查詢優化

1. 緩存友好：相鄰節點內存局部性較好
2. 預計算跨度：span值加速排名計算
3. 惰性刪除：刪除時不立即收縮層級

5.3 并發控制

雖然Redis單線程模型不需要鎖，但設計上支持： - 讀操作無需加鎖（無寫沖突） - 寫操作通過CAS實現原子性

6. 實際應用示例

6.1 游戲排行榜實現

# 添加玩家分數
ZADD leaderboard 3500 "player1"
ZADD leaderboard 2800 "player2"

# 獲取TOP10
ZREVRANGE leaderboard 0 9 WITHSCORES

# 查詢玩家排名
ZREVRANK leaderboard "player1"
ZSCORE leaderboard "player2"

6.2 時間序列數據

# 添加事件時間戳
ZADD events 1651234567 "user:login"
ZADD events 1651234578 "order:create"

# 查詢某時間段事件
ZRANGEBYSCORE events 1651234560 1651234580

7. 基準測試數據

使用redis-benchmark測試對比（Key大小16字節，Value大小128字節）：

8. 總結

Redis跳躍表通過精巧的設計實現了： - 平均O(log n)的查詢效率 - 相對平衡樹更簡單的實現 - 優秀的內存局部性 - 高效的范圍查詢能力

這種實現方式特別適合有序集合場景，在排行榜、時間線、延遲隊列等業務中表現出色。理解其實現原理有助于開發者更好地利用Redis的能力，并在需要時進行針對性優化。

附錄：相關源碼文件

• src/t_zset.c - 有序集合實現
• src/redis.h - 數據結構定義
• src/zmalloc.c - 內存管理

”`

注：本文基于Redis 6.2源碼分析，實際實現可能隨版本演進有所調整。完整實現建議參考最新Redis源碼。