不想寫 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) 理論上存在，但概率低到不用在意。
為什麼 Redis 選 Skip List 而不是紅黑樹？
Redis 作者 antirez 說過原因：
- 實作簡單：Skip List 的 code 比紅黑樹少很多，bug 也少
- 區間查詢：
ZRANGEBYSCORE需要取一段範圍，Skip List 的有序鏈表天然支援，紅黑樹要做中序遍歷 - 並發友善：Skip List 只需要鎖住局部的幾個節點，紅黑樹旋轉可能影響整棵子樹
| Skip List | AVL / Red-Black Tree | |
|---|---|---|
| 實作難度 | 低 | 高 |
| 區間查詢 | 天然支援 | 要遍歷 |
| 並發加鎖 | 局部鎖 | 困難 |
| 平衡方式 | 隨機化 | 旋轉 |
實際應用
- Redis Sorted Set（zset）：排行榜、延遲佇列
- LevelDB / RocksDB：MemTable（記憶體中的排序結構）
- Java ConcurrentSkipListMap：並發安全的有序 Map
Skip List 告訴我們一件事：有時候「差不多隨機」比「精確旋轉」更實用。工程上的最佳解不一定是理論上的最優解。