跳表是一種基於有序鏈表並增加多層索引的概率性資料結構，查找、插入、刪除時間複雜度均為 O(log N)，實現簡單且效能優異。LevelDB、Redis Sorted Set 等知名專案均採用跳表作為核心索引結構。本文通過圖解與原始碼分析，帶你透徹理解跳表設計精髓。
假設有一個有序鏈表 12 → 23 → 34 → 43 → 50 → 59 → 72，查找 59 需遍歷 6 個節點。若每隔幾個節點提取一層索引：
14 → 34 → 50 → 7234 → 72查找時從最高層索引開始「向右找、向下降」，大幅減少比較次數。這就是跳表的核心——多層有序鏈表 + 向下指標。
log₂N 左右。forward（同層下一節點）與 down（下層對應節點）。INT_MIN（-1）與 INT_MAX（1）。從最高層頭節點開始：
forward->value ≤ target，向右移動。level（通常用幂次分布：50% 機率 level=1，25% level=2...）。level > 當前最大層數，擴展頭節點層數並更新 update 數組。查找目標節點，記錄各層前驅節點，逐層跳過目標節點，最後釋放記憶體；若最高層僅剩哨兵，降低層數。
完整、可用於生產環境的 C 實現請參考：
https://github.com/begeekmyfriend/skiplist
該實現包含：
| 維度 | 跳表 | 平衡樹 |
|---|---|---|
| 實現複雜度 | 低（約 200-300 行核心代碼） | 高（旋轉、重新平衡邏輯繁瑣） |
| 並發友好度 | 高（易於實現無鎖或細粒度鎖） | 低（旋轉操作難以細粒度加鎖） |
| 記憶體開銷 | 較大（多層指標，約 1.33 倍節點） | 固定（兩個子節點指標） |
| 快取局部性 | 較好（底層鏈表連續訪問） | 一般（樹節點分散） |
