我們來聊聊「跳表（Skip List）」，這是一個既經典又優雅的數據結構，尤其在 Redis 中非常重要，比如 ZSet（有序集合）底層就用到了跳表。
🌟 跳表（Skip List）簡介
跳表是一種有序鏈表的升級版，通過引入多級“索引層”來加快查找效率。
? 主要特點：
| 特性 | 說明 |
|---|---|
| 有序結構 | 跳表維護的是一個按 key 排序的鏈表 |
| 多級索引 | 類似高速公路入口，有“快捷路徑” |
| 查找時間復雜度 | O(log n)，跟平衡樹差不多 |
| 實現簡單 | 不像紅黑樹那樣復雜 |
| 支持范圍查找 | 很適合 Redis 中的范圍查詢場景 |
📐 跳表結構長啥樣？
假設我們有以下數據：[1, 3, 5, 7, 9]
我們構建跳表的過程如下（用 → 表示鏈表）：
Level 2: 1 → → → 9
Level 1: 1 → 5 → → 9
Level 0: 1 → 3 → 5 → 7 → 9
你可以把它想象成“高架橋+地面道路”的組合：
- 第 0 層是原始鏈表，所有節點都在這里
- 每上一層都是稀疏的抽樣索引，跳過一些中間節點，加快查找速度
- 查找從最上層開始，逐層向下，“跳躍式前進”
🔍 查找過程舉例：查找 7
- 從最上層的 1 開始 → 跳到 9（9 > 7，不行）
- 回退到下一層 → 1 → 5 → 9（9 > 7，繼續往下）
- 到最底層 → 5 → 7 ? 找到！
→ 相比普通鏈表要順著一格一格走，跳表“跳著走”，很快！
📈 跳表的時間復雜度
| 操作 | 時間復雜度 |
|---|---|
| 查找 | O(log n) |
| 插入 | O(log n) |
| 刪除 | O(log n) |
| 空間復雜度 | O(n) |
相比紅黑樹、AVL 樹，它的代碼實現更簡單、更易于維護。
💡 跳表的應用場景
| 場景 | 用途 |
|---|---|
| Redis ZSet | 支持快速插入、范圍查詢（如 zrangebyscore） |
| LSM-Tree（如 RocksDB） | 早期實現用過跳表 |
| 時間序列數據 | 有序插入、范圍檢索 |
| 分布式系統 | 一致性哈希環也可用跳表改進檢索速度 |
🔧 跳表 vs 紅黑樹
| 項目 | 跳表 | 紅黑樹 |
|---|---|---|
| 插入復雜度 | O(log n) | O(log n)，但旋轉邏輯復雜 |
| 實現難度 | 簡單 | 復雜（需維持平衡） |
| 查詢性能 | 相似 | 相似 |
| 空間開銷 | 稍高（多指針） | 較少 |
🧪 小技巧：跳表的層數怎么選？
跳表是隨機化結構，每次插入一個節點時，以一定概率（如 1/2）決定它是否晉升到上一層。
最常見的方式是：
while (random() < p && level < MAX_LEVEL) {level++;
}
所以跳表是一種「概率平衡」的數據結構。
📦 總結
| 優點 | 缺點 |
|---|---|
| 實現簡單、性能穩定 | 占用內存較多 |
| 支持快速范圍查找 | 查詢時間有輕微波動 |
| 非常適合緩存、有序集合 | 不如 B 樹適合磁盤存儲 |
在 Redis 中，跳表（Skip List） 主要用于 Sorted Set（有序集合，zset） 的底層實現。
? 使用跳表的場景：zset（有序集合）
Redis 的 zset 類型是一個既可以快速查找元素、又能按照分數排序的數據結構。為了實現這個特性，它使用了 兩種結構 來共同實現：
| 結構 | 作用 |
|---|---|
| 哈希表（dict） | 用于通過成員名快速定位其分數，O(1) 時間復雜度 |
| 跳表（skiplist） | 用于按照分數進行有序排列，支持范圍查找、按排名查找等，平均 O(log n) 復雜度 |
🧠 為什么 Redis 用跳表而不是紅黑樹？
雖然紅黑樹、AVL 樹等自平衡二叉樹也能滿足排序要求，但 Redis 選擇跳表是因為：
- 實現簡單、易于維護
- 插入和刪除操作更平滑，少量隨機性避免最壞情況
- 天然支持范圍查詢和按 rank 查找
- 跳表是線性結構，遍歷更快，利于內存預取（cache friendly）
🧪 舉個例子：
127.0.0.1:6379> ZADD myzset 1 a 2 b 3 c
127.0.0.1:6379> ZRANGE myzset 0 -1 WITHSCORES
1) "a"
2) "1"
3) "b"
4) "2"
5) "c"
6) "3"
在內部：
- Redis 用 dict 維護
a → 1，b → 2，c → 3 - 同時用跳表按分數 1 → 2 → 3 排列節點，方便范圍查詢，比如
ZRANGEBYSCORE
🔧 Redis 跳表結構核心代碼（在源碼中）
源碼路徑：/src/t_zset.c
關鍵結構：zskiplist、zskiplistNode
typedef struct zskiplistNode {robj *obj; // 成員對象double score; // 分數struct zskiplistNode *backward;struct zskiplistLevel {struct zskiplistNode *forward;unsigned int span;} level[];
} zskiplistNode;
? 總結
Redis 中只有
zset使用跳表，結合 hash dict 實現高效的查找和排序。
