跳表 (Skip List)#

跳表是對鏈結串列的改造，透過建立多層索引，實現類似二分查找的效率。它是 Redis 有序集合的底層實現。

核心思想#

單鏈結串列即使有序，查找也需要 O(n)。跳表的解決方案是：空間換時間，建立多層索引。

索引構建規則#

• 每 2 個節點抽取 1 個作為上層索引
• 第 1 層索引約 n/2 個節點
• 第 2 層索引約 n/4 個節點
• 第 k 層索引約 n/2^k 個節點

跳表本質上是在鏈結串列上實現了「二分查找」的效果。

時間複雜度分析#

索引層數#

假設最高層索引有 2 個節點： $$\frac{n}{2^h} = 2 \Rightarrow h = \log_2 n - 1$$

包含原始鏈結串列，總高度為 log n。

每層走訪節點數#

關鍵觀察：每層最多走訪 3 個節點。

• 假設在第 k 層找到 y < target < z
• 下降到第 k-1 層，y 和 z 之間最多 3 個節點

時間複雜度：O(log n)

等同於二分查找，但適用於鏈結串列！

空間複雜度分析#

索引節點總數（等比數列求和）： $$\frac{n}{2} + \frac{n}{4} + \frac{n}{8} + … + 2 = n - 2$$

空間複雜度：O(n)

優化策略#

若每 3 個節點抽取 1 個作為索引： $$\frac{n}{3} + \frac{n}{9} + … \approx \frac{n}{2}$$

實際應用中，索引只存儲 key 和指標，物件資料存在原始鏈結串列中，額外空間開銷可以忽略。

動態插入與刪除#

插入 O(log n)#

1. 找到插入位置（O(log n)）
2. 插入節點（O(1)）
3. 隨機決定是否提升為索引

刪除 O(log n)#

1. 找到目標節點（O(log n)）
2. 刪除該節點及其所有索引節點

索引動態更新#

如果只插入不更新索引，跳表可能退化為鏈結串列！

隨機化策略#

插入新節點時，透過隨機函式決定將其提升到哪幾層索引：

import random

def random_level(max_level=16, p=0.5):
    level = 1
    while random.random() < p and level < max_level:
        level += 1
    return level

這種方法從概率上保證索引的平衡性。

為何 Redis 選擇跳表而非紅黑樹？#

Redis 有序集合支援的操作：

1. 插入、刪除、查找元素
2. 按區間查找資料
3. 迭代輸出有序序列

Redis 選擇跳表的原因：

1. 區間查找高效：找到起點後沿鏈結串列走訪即可
2. 實作簡單：比紅黑樹易於理解和維護
3. 靈活：可通過改變索引策略平衡效能與空間

跳表結構示意#

Level 3:  1 --------------------------> 9
Level 2:  1 --------> 4 --------------> 9
Level 1:  1 --> 3 --> 4 --> 6 --> 7 --> 9
Level 0:  1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

查找 7 的過程：

1. Level 3: 1 → 9 (7 < 9，下降)
2. Level 2: 1 → 4 → 9 (7 < 9，下降)
3. Level 1: 4 → 6 → 7 (找到！)

只需走訪 6 個節點，而原始鏈結串列需要走訪 7 個。