跳表 (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 kotlin.random.Random

fun randomLevel(maxLevel: Int = 16, p: Double = 0.5): Int {
    var level = 1
    while (Random.nextDouble() < p && level < maxLevel) {
        level++
    }
    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 個。

這個「能往前就往前、卡住就下降一層」的走法，寫成程式碼如下：

const val MAX_LEVEL = 16

class Node(val value: Int) {
    // forward[i]：本節點在第 i 層指向的下一個節點
    val forward = arrayOfNulls<Node>(MAX_LEVEL)
}

// 從最高層開始，能往前就往前，走不動就下降一層
fun search(head: Node, target: Int): Node? {
    var current = head
    for (level in MAX_LEVEL - 1 downTo 0) {
        var next = current.forward[level]
        while (next != null && next.value < target) {
            current = next
            next = current.forward[level]
        }
    }
    // 此時停在第 0 層 target 的前一個節點，往前一步驗證
    val candidate = current.forward[0]
    return if (candidate?.value == target) candidate else null
}