Skip List 跳躍表

不想寫 AVL Tree 的旋轉？丟硬幣就能平衡的 Skip List 了解一下。Redis 就是這麼選的。

丟硬幣就能平衡

Skip List 用多層鏈表加上隨機化達成期望 O(log n) 的查找、插入、刪除。實作比平衡樹簡單得多、天然支援區間查詢、並發場景容易加鎖。Redis 的 Sorted Set（zset）底層就是 Skip List，不是紅黑樹。

結構：多層快速通道

Level 3: HEAD ─────────────────────── 25 ─── null
Level 2: HEAD ────── 7 ──────────── 25 ─── null
Level 1: HEAD ── 3 ── 7 ──── 12 ── 25 ─── null
Level 0: HEAD ── 3 ── 6 ── 7 ── 9 ── 12 ── 19 ── 25 ── null

Level 0 是完整的有序鏈表。每往上一層就跳過更多節點，像是書的目錄：Level 0 是每一頁、Level 1 是章節、Level 2 是大章、Level 3 是總覽。

查找時從最高層開始，遇到比目標大的就往下降一層，逐步縮小搜尋範圍。

查找 19：
Level 3: HEAD → 25（太大，下降）
Level 2: HEAD → 7 → 25（太大，下降）
Level 1: 7 → 12 → 25（太大，下降）
Level 0: 12 → 19 ✓

隨機化：不用旋轉也能平衡

插入新元素時，隨機決定它要出現在幾層。每次丟硬幣，正面就多一層。

int randomLevel() {
    int level = 0;
    while (level < MAX_LEVEL && random.nextDouble() < 0.5)
        level++;
    return level;
}

期望下來，大約一半的節點只在 Level 0，四分之一在 Level 1，八分之一在 Level 2…自然形成「越高層越稀疏」的結構。不需要任何旋轉操作。

是的，這是一個靠隨機達成平衡的資料結構。聽起來不靠譜？數學上期望時間複雜度是嚴格的 O(log n)。最差情況 O(n) 理論上存在，但概率低到不用在意。

插入和刪除也都建立在「先查找」上：查找時順手記下每一層的前驅節點，插入就在隨機出來的那幾層把指標接上去，刪除則反過來把每層的指標繞過它。沒有旋轉、沒有重新著色，就是改幾個 next 指標而已——這正是它 code 量比紅黑樹少一截的原因。

操作	平均	最差
查找	O(log n)	O(n)
插入	O(log n)	O(n)
刪除	O(log n)	O(n)
空間	O(n)	O(n log n)

最差那欄是丟硬幣連續丟到爛運氣、所有節點都疊到高層的假想情況，實務上你這輩子不會遇到；空間的 O(n log n) 上界也一樣，期望值就是 O(n)。

為什麼 Redis 選 Skip List 而不是紅黑樹？

Redis 作者 antirez 說過原因：

1. 實作簡單：Skip List 的 code 比紅黑樹少很多，bug 也少
2. 區間查詢：ZRANGEBYSCORE 需要取一段範圍，Skip List 的有序鏈表天然支援，紅黑樹要做中序遍歷
3. 並發友善：Skip List 只需要鎖住局部的幾個節點，紅黑樹旋轉可能影響整棵子樹

	Skip List	AVL / Red-Black Tree
實作難度	低	高
區間查詢	天然支援	要遍歷
並發加鎖	局部鎖	困難
平衡方式	隨機化	旋轉

實際應用

• Redis Sorted Set（zset）：排行榜、延遲佇列
• LevelDB / RocksDB：MemTable（記憶體中的排序結構）
• Java ConcurrentSkipListMap：並發安全的有序 Map

🎬 互動視覺化：Skip List 逐層查找動畫 — 插入時親眼看它丟硬幣決定爬幾層，查找時看那條「先橫衝、撞牆再下降」的路徑怎麼把 O(n) 砍成 O(log n)。

---

Skip List 告訴我們一件事：有時候「差不多隨機」比「精確旋轉」更實用。工程上的最佳解不一定是理論上的最優解。

接下來往哪走

• Bloom Filter 布隆過濾器 — 下一篇：另一個用機率換工程效益的資料結構
• Red-Black Tree 紅黑樹 — Redis 沒選的那個對照組，看完就懂 antirez 在比什麼
• Redis 是什麼：很多人只拿它當快取，其實它是後端的瑞士刀 — zset 排行榜在真實後端場景怎麼用