深入淺出 Redis 底層資料結構（下）：跳躍表、整數集合、壓縮列表

Redis 底層資料結構深度解析（下）

上篇介紹了 SDS、雙向鏈表、字典。本文續講 Redis 另外三大核心結構：跳躍表（有序集合）、整數集合（小整數集合）、壓縮列表（列表/哈希底層），幫助你在選擇資料型別時做出正確決策。

五、跳躍表

5.1 概述

跳躍表是一種有序、隨機化的多層鏈表，查找/插入/刪除皆為 O(log N) 期望時間，實現遠比平衡樹簡單。Redis 僅在兩處使用：有序集合鍵與叢集節點內部結構。

5.2 結構定義

節點 zskiplistNode

typedef struct zskiplistNode {
    struct zskiplistLevel {   // 層
        struct zskiplistNode *forward; // 前進指標
        unsigned int span;             // 跨度（節點間距離）
    } level[];
    struct zskiplistNode *backward;    // 後退指標
    double score;                      // 分值（排序依據）
    robj *obj;                         // 成員物件（SDS 字串）
} zskiplistNode;

• 層高：1~32 隨機，層數越高「跳」得越遠。
• 前進/後退指標：支援正向範圍查詢與反向遍歷。
• 跨度：用於計算排名（ZRANK）。
• 排序規則：分值升序；分值相同按成員字典序。

跳躍表 zskiplist

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 表頭/表尾
    unsigned long length;                // 節點總數
    int level;                           // 最大層數
} zskiplist;

5.3 小結

• 有序集合底層實現之一（另一為壓縮列表，視元素數量/大小切換）
• 節點層高隨機、分值排序、成員唯一
• 支援高效範圍查詢與排名操作

六、整數集合

6.1 定義

當集合只含整數且元素數量較少時，Redis 使用 intset 作為集合鍵底層實現。

6.2 結構

typedef struct intset {
    uint32_t encoding;  // 編碼方式：INT16/INT32/INT64
    uint32_t length;    // 元素數量
    int8_t contents[];  // 實際儲存陣列（型別由 encoding 決定）
} intset;

6.3 升級機制

新增元素超出當前編碼範圍時，自動升級：

1. 按新元素型別擴展陣列空間
2. 現有元素全部轉換為新編碼（重新分配空間）
3. 插入新元素

優點：提升靈活性、節省記憶體（小整數用 INT16）。只升不降，避免頻繁轉換開銷。

七、壓縮列表

7.1 適用場景

列表鍵或哈希鍵元素較少、且值為小整數或短字串時使用，極度節省記憶體。

7.2 結構組成

+--------+--------+--------+--------+--------+--------+------+
| zlbytes| zltail | zllen  | entry1 | entry2 | ...  | zlend|
+--------+--------+--------+--------+--------+--------+------+

• zlbytes：總佔用位元組數
• zltail：尾節點偏移量（O(1) 尾部操作）
• zllen：節點數
• entryX：節點內容（字串或整數，緊湊編碼）
• zlend：結束標記 0xFF

7.3 連鎖更新

插入/刪除節點可能導致後續節點zltail、zlbytes 需調整，極端情況觸發連鎖更新（O(N²)），但實際觸發機率極低。

總結對照表

理解底層結構，才能根據數據特徵選擇最佳 Redis 資料型別，避免記憶體浪費與效能瓶頸。