工具-跳表

🎯 什麼情境該想到我

當你「需要一個有序結構，而且要同時支援範圍查詢與排名計算」，正在平衡樹（紅黑樹／AVL）與 B+ 樹之間猶豫的時候。也是 Redis ZSet、排行榜、延遲佇列底下那個結構。

⚙️ 怎麼用（步驟 / 公式）

一句話：在有序鏈結串列上疊多層索引

單向鏈結串列查一個元素要 O(N)，因為只能一格一格走。跳表在原始串列上疊多級索引——上層是下層的稀疏抽樣，查找時從最高層開始：

右邊的節點比目標小 → 往右走；比目標大 → 下沉一層。 重複到最底層。

每下沉一層，候選區間就縮小一次，所以平均 O(log N)。插入、刪除同理（先查到位置，再改指標）。

層高用「擲硬幣」決定，不做旋轉

平衡樹要靠旋轉維持平衡，跳表不維持任何全域不變式——新節點的層高是隨機擲出來的：

/* redis/redis src/t_zset.c，查證 2026-09-25 */
static int zslRandomLevel(void) {
    static const int threshold = ZSKIPLIST_P*RAND_MAX;   /* ZSKIPLIST_P = 0.25 */
    int level = 1;
    while (random() < threshold)
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;  /* MAXLEVEL = 32 */
}

層高服從幾何分布，可以直接推導：

量	公式	`P=0.25` 時
節點恰好 `k` 層的機率	`P^(k-1) · (1-P)`	1 層 75%、2 層 18.75%、3 層 4.69%
每個節點的期望層數	`1/(1-P)`	1.333 層
期望最高層（N 個節點）	`log_{1/P}(N)`	N=100 萬 → `log₄(10⁶) ≈ 9.97`

100 萬節點的模擬驗證（Python 複刻 zslRandomLevel，seed=42，2026-09-25）：

平均層數 = 1.33299   （理論 1.33333）
最高層   = 11        （理論 log₄(10⁶) ≈ 9.97）
第 1 層 750123 個 (0.7501，理論 0.7500)
第 2 層 187680 個 (0.1877，理論 0.1875)
第 3 層  46435 個 (0.0464，理論 0.0469)

這個 1.33 很重要：它是跳表的記憶體帳。每層要一個 forward 指標（8 bytes）＋一個 span（8 bytes）＝ 16 bytes，所以平均每個節點的索引開銷只有 1.33 × 16 ≈ 21 bytes——跳表並不是「每個節點都存一堆指標」。

ZSKIPLIST_MAXLEVEL = 32（不是 64，網路上常抄錯）。頭節點一次就配滿 32 層，固定 32 × 16 = 512 bytes——用一個極小的定額開銷，換掉「頭節點動態擴容」那一整套邏輯。

span：跳表能算排名的關鍵

Redis 在每個前進指標上額外記一個 span（這一跳跨過幾個元素）。ZRANK 沿查找路徑把經過的 span 累加，就是名次——不必從頭數，所以排名也是 O(log N)。

這是跳表相對於「純索引結構」的加分項：平衡樹要算排名，得額外在每個節點維護子樹大小（order-statistic tree），跳表天生順手就有。

★ 為什麼 Redis 選跳表，不選 B+ 樹或紅黑樹

對手	它的優勢前提	在 Redis 裡為什麼不成立
B+ 樹	壓低樹高 → 減少磁碟 I/O 次數	Redis 純記憶體，沒有磁碟 I/O 可省；而 B+ 樹的頁分裂會降低填充率（內部碎片）並造成寫入抖動
紅黑樹 / AVL	最壞情況有保證	範圍查詢要中序走訪，不如跳表「查到起點後沿最底層直接往後掃」；且旋轉邏輯複雜，併發與實作成本高

再加上一條工程理由：跳表的程式碼短得多，好維護、好擴充（Redis 就是在它上面加了 span 來支援排名）。

自己實作時的三個要點

update[] 陣列：查找時沿路記下每層的前驅節點，插入時只要改這 1~K 層的指標。
同分怎麼排：Redis 的規則是 score 相同時按 member 字典序——沒有這條規則，範圍查詢的邊界會不確定。
backward 指標只在最底層，用來倒序走訪（ZREVRANGE）。

🧪 我實際套用的紀錄

2026-09-25：用 Python 複刻 zslRandomLevel 跑 100 萬次，層數分布與 P^(k-1)(1-P) 吻合到小數第三位，平均層數 1.333。這組數字之後估 ZSet 記憶體時可以直接用。

⚠️ 注意 / 什麼時候不適用

最壞情況沒有保證。層高是隨機的，理論上可能退化成鏈結串列（機率極低）。要硬保證最壞 O(log N) 的場景（例如即時系統）請用平衡樹。
不適合磁碟。節點散落在記憶體各處，換到磁碟上每次下沉都是一次隨機 I/O——這正是資料庫索引用 B+ 樹不用跳表的原因。
現行 Redis unstable 的節點布局已經變了：SDS 改成內嵌在 level[] 之後，level 0 的 span 被挪去存節點資訊。照著舊文章抄 zskiplistNode 結構時要對版本。
有序但不能重複。ZSet 的 member 唯一，重複 ZADD 同一個 member 是更新 score 而不是新增。

🔗 相關工具

工具-Redis資料型別的底層編碼 — 跳表只在 ZSet 超過 zset-max-listpack-entries 後才登場
工具-延遲任務方案選型 — 拿 ZSet 當延遲佇列時，「取最小 score 是 O(log N)」指的就是這裡
紅黑樹 Red-Black Tree — 對照組：靠旋轉維持不變式的做法
工具-儲存引擎B-Tree與LSM-Tree — 對照組：磁碟導向的結構為什麼非得壓低樹高
工具-資料結構的選擇 — 「有序 + 範圍 + 排名」這組需求該怎麼挑

Quartz 5

Explorer