跳表（Skip List）是一種支持高效插入、刪除和查找的鏈表結構，用于加速查找操作，特別適用于有序數據集合。它在Redis、LevelDB等系統中被用于**有序集合（Sorted Set）**的實現。

1. 跳表的結構

跳表的核心思想是：
在鏈表的基礎上，引入多級索引，類似于高速公路的匝道，提高查找效率。

一個跳表通常由多層索引構成：

• 最底層（Level 0） 是一個有序單鏈表，存儲所有數據；
• 上層索引（Level > 0） 由部分節點構成，起到“跳躍”的作用，加速查找；
• 最上層索引 由少量節點構成，使得查找可以迅速縮小范圍。

示例跳表（3 層）：

Level 2:    1 --------------> 9 ----------------> 19
Level 1:    1 ----> 5 -----> 9 ----> 13 -------> 19
Level 0:    1 -> 3 -> 5 -> 7 -> 9 -> 11 -> 13 -> 15 -> 17 -> 19

每一層都是上一層的子集，節點的“晉升”是概率性的（通常是 1/2）。

2. 跳表的基本操作

查找

跳表的查找過程類似于二分查找：

1. 從最高層索引開始，查找小于目標值的最大節點；
2. 向下移動到下一層索引，繼續查找；
3. 直到底層（Level 0），最終在普通鏈表中找到目標節點或確認其不存在。

時間復雜度：
$$O(\log n)$$ —— 因為跳表的高度是O(log n)，查找路徑長度也大約是O(log n)。

插入

1. 查找插入位置，找到前驅節點；
2. 隨機決定新節點的層數（常見做法：擲硬幣，每次有 50% 概率提升一層）；
3. 在每一層進行插入，更新索引。

時間復雜度：

• 平均 O(log n)，因為最多遍歷 log n 層；
• 最壞 O(n)（所有元素都在同一層）。

刪除

1. 查找目標節點（與查找操作類似）；
2. 在每一層移除節點；
3. 如果某層為空，則刪除該層。

時間復雜度：
$$O(\log n)$$

3. 跳表 vs. 其他數據結構

數據結構	查找時間復雜度	插入時間復雜度	刪除時間復雜度	額外空間	適用場景
跳表	O(log n)	O(log n)	O(log n)	O(n)	有序數據、高效查找
平衡二叉搜索樹 (AVL, 紅黑樹)	O(log n)	O(log n)	O(log n)	O(n)	適用于動態數據
哈希表	O(1)	O(1)	O(1)	O(n)	適用于無序數據、頻繁查詢
鏈表	O(n)	O(1)	O(n)	O(n)	適用于插入、刪除較多

跳表 vs. 紅黑樹

• 跳表實現更簡單，只需維護索引，而紅黑樹需要復雜的旋轉操作；
• 跳表在分布式環境中更友好，如 Redis 的有序集合（ZSet）采用跳表；
• 紅黑樹適用于內存受限的場景，因為跳表的索引層需要額外存儲空間。

4. 實際應用

Redis

Redis 有序集合（Sorted Set） 的底層結構是 跳表 + 哈希表：

• 跳表：用于范圍查詢（ZRANGE、ZREVRANGE）
• 哈希表：用于O(1) 查找（ZADD）

LevelDB

Google 的 LevelDB 用跳表存儲MemTable，然后刷盤成 SSTable。

5. 代碼實現（Java）

跳表節點

class SkipListNode {int val;SkipListNode[] next; // 指向不同層級的下一個節點public SkipListNode(int val, int level) {this.val = val;this.next = new SkipListNode[level];}
}

跳表類

import java.util.Random;class SkipList {private static final int MAX_LEVEL = 16;  // 最大層數private final SkipListNode head; // 頭節點private int levelCount = 1; // 當前最大層數private final Random random = new Random();public SkipList() {head = new SkipListNode(-1, MAX_LEVEL); // 初始化頭節點}// 查找public boolean search(int target) {SkipListNode cur = head;for (int i = levelCount - 1; i >= 0; i--) {while (cur.next[i] != null && cur.next[i].val < target) {cur = cur.next[i];}}cur = cur.next[0];  // 進入最底層return cur != null && cur.val == target;}// 插入public void insert(int num) {SkipListNode[] update = new SkipListNode[MAX_LEVEL]; // 記錄每層的前驅節點SkipListNode cur = head;for (int i = levelCount - 1; i >= 0; i--) {while (cur.next[i] != null && cur.next[i].val < num) {cur = cur.next[i];}update[i] = cur;  // 記錄前驅節點}int newLevel = randomLevel();levelCount = Math.max(levelCount, newLevel);SkipListNode newNode = new SkipListNode(num, newLevel);for (int i = 0; i < newLevel; i++) {newNode.next[i] = update[i].next[i];update[i].next[i] = newNode;}}// 刪除public void delete(int num) {SkipListNode cur = head;SkipListNode[] update = new SkipListNode[MAX_LEVEL];for (int i = levelCount - 1; i >= 0; i--) {while (cur.next[i] != null && cur.next[i].val < num) {cur = cur.next[i];}update[i] = cur;}SkipListNode target = cur.next[0];if (target == null || target.val != num) return;for (int i = 0; i < levelCount; i++) {if (update[i].next[i] != target) break;update[i].next[i] = target.next[i];}}// 隨機生成層數private int randomLevel() {int level = 1;while (random.nextDouble() < 0.5 && level < MAX_LEVEL) {level++;}return level;}
}

6. 總結

• 跳表通過多層索引加速查詢，時間復雜度接近O(log n)；
• 插入/刪除時動態調整索引，比紅黑樹實現簡單；
• Redis、LevelDB 等系統采用跳表，適用于有序集合、范圍查詢等場景；
• 比紅黑樹占用更多空間，但更適合并發和分布式環境。