跳表（Skiplists）有什麼用？

背景

這篇文章源於 Antithesis 團隊在處理大規模模糊測試（Fuzzing）數據時遇到的挑戰。由於測試過程會產生龐大的分支樹狀結構，傳統資料庫在處理「向上追溯父節點」這類點對點查詢時效率極低，團隊因此受到跳表（Skiplist）啟發，開發出一種名為「跳樹」（Skiptree）的變體結構，藉此在分析型資料庫中實現高效的樹狀路徑檢索。

社群觀點

在 Hacker News 的討論中，跳表被視為一種極具爭議但也充滿魅力的資料結構。支持者認為跳表最大的優勢在於實作簡單且程式碼精簡，比起複雜的平衡二元樹（如紅黑樹），跳表更容易實現無鎖（Lock-free）的併發控制。在現代資料庫架構中，跳表扮演著關鍵角色，例如它是 LSM 樹（Log-Structured Merge-tree）記憶體表（Memtable）的基礎，廣泛應用於 2005 年後開發的多數主流資料庫。此外，跳表結合了隨機存取的效能與鏈結串列的有序迭代特性，在需要頻繁進行範圍掃描或有序遍歷的場景中表現優異。

然而，許多開發者對跳表的實務效能持保留態度。反對意見指出，在現代計算機硬體架構下，跳表需要進行大量的指標解引用（Pointer Dereferencing），這會導致頻繁的快取失效（Cache Miss）。相比之下，B+ 樹在單次輸入輸出操作中能處理更多數據，對硬體更為友善。有留言者質疑 Antithesis 團隊為何不直接使用 B+ 樹或圖形資料庫，認為跳樹的概念雖然新穎，但可能只是在解決一個因選錯工具而產生的問題。針對 Antithesis 的具體案例，甚至有觀點提出「以計算換取空間」的替代方案：既然模糊測試是確定性的，只需儲存隨機種子，在查詢時重新執行測試即可重建路徑，無需儲存龐大的樹狀結構。

討論中也延伸到了開發者技能的隱憂。部分留言者擔心在生成式 AI 與自動化工具盛行的時代，深入理解底層資料結構與硬體優化的能力正逐漸邊緣化。當開發者傾向於透過增加硬體資源或調用現成 API 來解決問題時，像跳表這類精巧的演算法知識可能會變成一種「冷門知識」。但也有人反駁，隨著硬體成本上升與推論需求增加，如何更聰明地分配資源、利用硬體特性進行極致優化，反而會成為未來開發者的核心競爭力。

延伸閱讀

在討論中，社群成員分享了幾個值得深入研究的資源。首先是 Qt 框架中 QMap 容器曾使用跳表的技術原理解析，這對於理解跳表在通用函式庫中的應用非常有幫助。其次，針對高效能運算需求，有一篇關於 GPU 友善的跳表演算法論文（GPUSkiplist.pdf）被提及，展示了如何利用 SIMD 指令集來加速跳表操作。這些資源為跳表在現代硬體上的應用提供了更多技術細節。