Redis 數據結構源碼剖析（SDS、Dict、Skiplist、Quicklist、Ziplist）

1. 前言

Redis 的高性能與豐富數據結構密切相關。
核心數據結構包括：

• SDS（Simple Dynamic String）：字符串底層實現。
• Dict（哈希表）：Key-Value 映射。
• Skiplist（跳表）：有序集合底層結構。
• Quicklist（快速列表）：List 的底層實現。
• Ziplist / Listpack（壓縮列表）：小型集合或 Hash 的緊湊存儲。

這些結構各有特點，支持 高效讀寫、低內存消耗 和 動態擴展。

---

2. SDS（Simple Dynamic String）

2.1 SDS 概念

Redis 字符串不是簡單 C 字符數組，而是 SDS，支持 動態擴容、二進制安全、O(1) 獲取長度。

2.2 SDS 結構

struct sdshdr {int len;      // 已使用長度int free;     // 剩余可用空間char buf[];   // 字符串內容（實際數據）
};

2.3 特性

• len：快速獲取字符串長度，避免 O(n) strlen()。
• free：預留空間，減少擴容次數。
• 二進制安全：可存儲 \0。

2.4 核心操作

s = sdsnew("hello");       // 創建
s = sdscat(s, " world");   // 拼接
sdsfree(s);                // 釋放

SDS 的擴容采用 指數增長，保證拼接操作的均攤 O(1) 性能。

---

3. Dict（哈希表）

3.1 Dict 概念

Redis 的 Hash 類型、數據庫全局 Key-Value 都使用 Dict。

3.2 Dict 結構

typedef struct dictEntry {void *key;void *val;struct dictEntry *next;   // 沖突鏈表
} dictEntry;typedef struct dictht {dictEntry **table;unsigned long size;unsigned long sizemask;unsigned long used;
} dictht;typedef struct dict {dictht ht[2];   // 支持漸進式 rehashlong rehashidx;
} dict;

3.3 特性

• 漸進式 rehash：避免大表擴容阻塞主線程。
• 沖突處理：鏈表法（拉鏈法）。
• 可定制化：支持自定義 hash 函數與 key/value dup/free 函數。

---

4. Skiplist（跳表）

4.1 Skiplist 概念

跳表是 Redis 有序集合（ZSet） 的底層結構。

• 支持快速 范圍查詢 和 按分數排序。
• 查找、插入、刪除平均 O(log n)。

4.2 Skiplist 結構

typedef struct zskiplistNode {sds ele;double score;struct zskiplistNode *backward;struct zskiplistLevel {struct zskiplistNode *forward;unsigned int span;} level[];
} zskiplistNode;typedef struct zskiplist {struct zskiplistNode *header, *tail;unsigned long length;int level;
} zskiplist;

• score：排序依據。
• forward：多層索引，提高查找效率。
• span：用于計算排名。

---

5. Quicklist（快速列表）

5.1 Quicklist 概念

Redis 3.2 之后，List 類型底層使用 Quicklist 替代雙端鏈表 + ziplist。

5.2 Quicklist 結構

typedef struct quicklistNode {struct quicklistNode *prev, *next;unsigned char *zl;   // ziplist 存儲多個元素unsigned int sz;     // ziplist 大小
} quicklistNode;typedef struct quicklist {quicklistNode *head, *tail;unsigned long count; // 元素總數int fill;            // ziplist fill factor
} quicklist;

5.3 特性

• 每個節點存儲多個元素，減少鏈表節點開銷。
• 內置 壓縮策略，節省內存。
• 支持雙向訪問，O(1) 插入/刪除。

---

6. Ziplist / Listpack

6.1 Ziplist 概念

• 小型集合、Hash、ZSet 會用 Ziplist 存儲。
• 是 連續內存壓縮存儲，減少內存碎片。

6.2 Ziplist 結構

[zlbytes][zltail][zllen][entry][entry]...[zlend]

• zlbytes：總字節數
• zltail：最后一個元素偏移
• zllen：元素數量
• entry：元素內容，支持整數壓縮

6.3 特性

• 對小對象極致節省內存
• 查詢效率較低，但適合小規模數據

---

7. 數據結構選擇策略

數據類型	小規模	大規模
String	embstr	raw
List	ziplist	quicklist
Hash	ziplist	dict
Set	intset	dict
ZSet	ziplist	skiplist+dict

Redis 會根據 元素個數、元素長度、配置閾值 自動升級底層數據結構。

---

8. 小結

本文分析了 Redis 核心數據結構源碼：

1. SDS：高效字符串存儲，支持 O(1) 獲取長度和動態擴容。
2. Dict：高性能哈希表，支持漸進式 rehash。
3. Skiplist：有序集合底層結構，支持快速排序和范圍查詢。
4. Quicklist：List 的底層實現，支持壓縮和雙向訪問。
5. Ziplist / Listpack：小型集合壓縮存儲，節省內存。

📌 理解這些數據結構是 Redis 高性能和內存優化的核心，也是所有命令執行和對象操作的基礎。

---

下一篇可以寫 Redis 內存優化與管理機制（內存碎片、LRU、惰性刪除、內存回收策略），這樣 Redis 的內存管理體系就完整了。