0.前言
通過本文將瞭解到以下內容：
- 跳躍鏈表的基本概念
- 跳躍鏈表的實現原理
- 跳躍鏈表的應用簡介
注：以下簡稱跳躍鏈表為 跳錶，由於跳錶內容較多，分為2-3次寫完 。跳錶的實現可以是單鏈表和雙鏈表，本文主要基於單鏈表闡述。
1.跳躍鏈表的基本概念
- 初識跳錶
跳躍列表是一種數據結構。它允許快速查詢一個有序連續元素的數據鏈表。跳躍列表的平均查找和插入時間複雜度都是O(log n)，優於普通隊列的O(n)。
跳躍列表由威廉·普發明，發明者對跳躍列表的評價：跳躍列表是在很多應用中有可能替代平衡樹而作為實現方法的一種數據結構。
跳躍列表的算法有同平衡樹一樣的漸進的預期時間邊界，並且更簡單、更快速和使用更少的空間。
這種數據結構是由 William Pugh (音譯為威廉·普)發明的，最早出現於他在1990年發表的論文《Skip Lists: A Probabilistic Alternative to Balanced Trees》，在谷歌上想進一步查一下這個大佬的履歷，信息並不多，不過找到一篇作者關於 跳錶的論文 ，感 興趣強烈建議下載閱讀 ：
https:// epaperpress.com/sortsea rch/download/skiplist.pdfWillliam
看下這篇論文的摘要部分：
用我2009年考過的六級給翻譯一下：
跳躍鏈表是一種可以用來代替平衡樹的數據結構。跳錶使用概率平衡而非嚴格平衡，因此基於跳錶實現的算法在插入和刪除操作上比平衡樹更簡單且明顯更快。
從中我們獲取到的信息是：
跳錶在動態查找過程中使用了一種非嚴格的平衡機制來讓插入和刪除都更加便利和快捷，這種非嚴格平衡是基於概率的，而不是平衡樹的嚴格平衡。
說到非嚴格平衡，首先想到的是紅黑樹RbTree，它同樣採用非嚴格平衡來避免像AVL那樣調整樹的結構，這裡就不展開講紅黑樹了，不過後面一定講一下紅黑樹，看來跳錶也是一樣的路子，但是是基於概率實現的。
- 動態查找的數據結構
所謂動態查找就是查找的過程中存在元素的刪除和插入，這樣就對實現查找的數據結構有一定的挑戰，因為在每次刪除和插入時都要調整數據結構，來保持秩序。可以作為查找數據結構的包括：
- 線性結構：數組、鏈表
- 非線性結構：平衡樹
來分析一下各種數據結構在應對動態查找時的優劣：
- 數組結構
數組結構簡單內存連續，可以實現二分查找等基於下標的操作，我一直認為數組的殺手鐧就是下標，連續的內存也帶來了問題。當進行插入和刪除時就面臨著整體的調整，就像在火車站排隊買票，隊頭走一個整個隊伍向前挪一步，有加塞的後面的又整體向後挪一步，這種整體移動操作在數組結構中性能損耗很大，並且在大數據量時對連續內存要求很高，當然這個在大內存機器上可能沒有什麼問題。
如圖演示插入6和刪除5時 數組元素的移動：
- 鏈表結構
鏈表結構也比較簡單，但是不要求內存連續，不連續也就沒有下標可以加速，但是鏈表在執行刪除和插入時影響的只是插入刪除點的前後元素，影響非常小。但是每次查找元素是需要進行遍歷，就算我知道某個元素一定在大致的什麼位置，也只能一步步走過去，看到這裡要覺得有優化的空間，那你也蠻厲害的了，說不定早幾年跳錶就是你的發明了。
如圖演示了刪除元素5和插入元素49時的處理：
- 平衡樹
平衡樹也是處理動態查找問題的一把好手，樹一般是基於鏈表實現的，只不過樹的節點之間並不是鏈表簡單的線性關係，會有兄弟姐妹父親等節點，並且各個層級有數量的限制，可以看到樹其實還是蠻複雜的。節點需要存儲的信息很多，各個指針指來指去，複雜的結構增加了調整平衡性的難度，不同情況下的左旋右旋，所以出現了紅黑樹這種工程版本的AVL，但是在實際場景中可能並不需要這些兄弟姐妹父親關係，有種殺雞宰牛刀的意味了。
紅黑樹的 節點結構定義 ：
<code> 1 #define COLOR_RED 0x0
2 #define COLOR_BLACK 0x1
3
4 typedef struct RBNode{
5 int key;
6 unsigned char color;
7 struct RBNode *left;
8 struct RBNode *right;
9 struct RBNode *parent;
10 }rb_node_t, *rb_tree_t;
/<code>
另外紅黑樹調整屬性過程中插入分為3種情況，刪除分為4種情況，還是比較難以理解的。
- 三種結構對比
從上面的對比可以看到：數組並不能很好滿足要求，鏈表在搜索過程又顯得更笨拙，平衡樹又有點複雜，到底該怎麼辦？
- 跳錶的雛形
有條件要上，沒有條件創造條件也要上。
沒有條件，那麼就創造條件。上面的三類結構都存在一些問題，所以要進行改造，可以看到數組和平衡樹的某些特性決定了它們不容易被改造(數組內存連續性、平衡樹節點多指針和層級關係)，相反鏈表最有潛力被改造優化。
- 不要一步步走 我要跳起來
在有序鏈表中插入和刪除都比較簡單，搜索時無法依靠下標只能遍歷，但是明明知道要走兩步可以到達目的地，偏偏只能一步步走，這就是痛點。
如圖演示了O(n)遍歷元素35和跳躍搜索元素35的過程：
貌似看到了曙光，那麼如何實現跳躍呢？
沒錯！給鏈表加索引，讓索引告訴我們下一步該跳到哪裡。
看到這裡又讓我想起來那個經典的中間層理論，遇到問題，試著加個中間層試試，或許就完美解決了。
2.跳躍鏈表的實現原理
前面說了可以給普通鏈表加索引來解決，但是具體該怎麼操作，以及其中有什麼難點？一步步來分析。在工程中對跳錶索引層數和結點是否作為索引結點，是其很重要的屬性，後面就詳細講一下，現在先看一種簡單場景，說明索引帶來的便利性。
- 簡單的索引
選擇每隔1個結點為索引結點，並且索引為一層，雖然在工程中這種形式比較標準化，不過足以說明索引帶來的加速。
可以將鏈表中的偶數序號節點增加一層指針，讓其指向下一個偶數節點，如圖所示：
搜索過程：加入要搜索值為55的節點，則先在上層進行搜索，由16跳到38，在38的下一跳將到達72，因此向下降一級繼續類似的搜索，則找到55。
- 我要一步一步向上爬
基於偶數節點增加索引並且只有兩層的情況下，最高層的節點數是n/2，整體來看搜索的複雜度降低為O(n/2)，並不要小看這個1/2的係數，看到這裡會想 增加索引層數到k，那麼複雜度將指數降低為O(n/2^k)。
索引層數不是無休止增加的，取決於該層索引的節點數量，如果該層的索引的節點數量等於2了，那麼再往上加層也就沒有意義了，
畫個圖看一下：
這個非常好理解，如果所在層索引結點只有1個，比如4層索引的結點16，只能順著16向下遍歷，無法向後跳到4層其他結點，
因此當所在層索引結點數量等於2，則到達最高索引層，這個約束在分析跳錶複雜度時很重要。
- 索引層數和索引結點密度
跳錶的複雜度和索引層數、索引結點的稀疏程度有很大關係。索引層數我們從上面也看到了，稀疏程度相當於索引結點的數量比例，如果跳錶的索引結點數量很少，那麼將接近退化為普通鏈表，這種情況在數據量是較大時非常明顯，畫圖看下(藍色部分表示有很多結點)：
圖中可以看到雖然有索引層，但是索引結點數量相對全部數據比例較低，這種情況下搜索35相比無索引情況優勢並不明顯。
所以跳錶的效率和索引層數和索引結點的密度有密切的關係，當然索引結點太多也就等於沒有索引了。太少的索引結點和太多的索引結點都是一樣的低效。
- 複雜度分析
從前面的分析可知，跳錶的複雜度和索引層數m以及索引結點間隙d有直接關係，其中索引結點間隙理解為相隔幾個結點出現索引結點，體現了對應層索引結點的稀疏程度，在無索引結點時只能遍歷無法跳躍。
推導過程：
如何 確定最高索引層數m 呢？
如果一個鏈表有 n 個結點，如果每兩個結點取出一個結點建立索引，那麼第一級索引的結點數是 n/2，
第二級索引的結點數是n/4，以此類推第 m 級索引的結點數為 n/(2^m)，前面說過最高層結點數為2，因此存在關係：
算上最底層的原始鏈表，整個跳錶的高度為h=logn(底數為2)，每一層需要遍歷的結點數是d，那麼整個過程的複雜度為:O(d*logn)。
d表明了層間結點的稀疏程度，也就是每隔2個結點選取索引結點、或者每隔3個結點選取索引結點，每個4個結點選取索引結點......最密集的情況下d=2，
但是索引結點密集也意味著存儲空間的增加，跳錶相比較普通鏈表就是典型的用空間換時間的數據結構，這樣就達到了AVL的複雜度O(logn)。
- 跳錶的空間存儲
以d=2的最密集情況為例，計算跳錶的索引結點總數：
2+4+8+......n/8+n/4+n/2=n-2
由等比數列求和公式得d=2的跳錶額外空間為O(n-2)。
- 跳錶的插入和刪除
工程中的跳錶並不嚴格要求索引層結點數量遵循2:1的關係，因為這種要求將導致插入和刪除數據時的調整，成本很大，因此跳錶的每個插入的結點在插入時進行選擇是否作為索引結點，如果作為索引結點則隨機出層數，整個過程都是基於概率的，但是在大數據量時卻能很好地解決索引層數和結點數的權衡。
- 跳錶元素17插入：
鏈表的插入和刪除是結合搜索過程完成的，貼一張William Pugh在論文中給出的在跳錶中插入元素17的過程圖(暫時忽略結點17是否作為索引結點以及索引層數，後面會詳細說明)：
- 跳錶元素1刪除：
跳錶元素的刪除與普通鏈表相比增加了索引層的判斷，如果結點是非索引結點則正常處理，如果結點是索引結點那邊需要進行索引層結點的處理。
3.跳躍鏈表的應用簡介
一般討論查找問題時首先想到的是平衡樹和哈希表，但是跳錶這種數據結構也非常犀利，性能和實現複雜度都可以和紅黑樹媲美，甚至某些場景由於紅黑樹，從1990年被髮明目前廣泛應用於多種場景中，包括Redis、LevelDB等數據存儲引擎中，後續將詳細介紹。
4.小結
本文主要講述了跳錶的基本概念和簡單原理、以及索引結點層級、時間和空間複雜度等相關部分，並沒有涉及概率平衡以及工程實現部分，後續將陸續推出。
閱讀更多 sandag 的文章
