如果要存一組有序的 int 型資料集合，我們可以如何實現？通常我們會想到最常見的兩種實現方案：
1. 陣列
2. 連結串列
如上圖，一個有序的連結串列，如果要找值為 50 的節點，需要從第一個節點開始遍歷，查詢最後才能找到值為 50 的節點。
我們給這個連結串列加一層索引，如圖：
我們按照一級索引來查詢（橙色查詢路線），可以發現我們至少可以少遍歷一半的節點。
還覺得有些慢？，那麼再增加一層，再加一層，如圖：
是不是更快地找到我們需要的節點了，當然這裡的節點數量不夠多，如果節點數量非常多，查詢效率提升會更加明顯。
如果需要找中間的某個節點，比如尋找 42 ，過程大概是這樣的：
看懂了跳躍表的資料結構，那麼就很容易理解節點的插入操作了，基本上兩步操作就可以實現：在最底層的資料鏈表中插入資料，然後調整索引；
其中每一層的索引連結串列中是否需要增加新增的節點，其實並沒有什麼標準答案，我們儘量做到索引的平均分佈即可，常用的就是【隨機判斷】決定是否需要新增或調整索引，當有新節點插入的時候，透過機率演算法判斷這個節點需要插入到幾級節點中。
比如：
底層資料鏈表有 N 個元素，隨機選擇 N/2 個元素作為 1 級索引，隨機選擇 N/4 個元素作為 2 級索引...一直到頂層索引；
新插入資料節點，1/2 機率不插入任何一級索引，1/4 機率返回需要插入 1 級索引，1/8 機率返回需要插入到 2 級索引，以此類推；
這裡要注意一點，插入 2 級索引的時候，同時也需要插入 1 級索引；也就是插入 n 級索引的時候，同時也要插入 1~( n-1 ) 級索引。
總結來說：
可以把跳躍表看成多個有序連結串列（最底層的資料鏈表+多層索引連結串列）；
查詢的過程中，從最長層開始查詢，找到對應的區間再到下一層查詢 ；
每個節點都有兩個指標，分別指向右邊和下邊；
插入新節點時，隨機判斷該節點是否要插入索引，最高插入幾級索引；
插入 n 級索引的時候，同時也要插入 1~(n-1) 級索引；
跳躍表和紅黑樹等平衡樹相比，更容易實現，並且不需要維護平衡性；
Redis 中的 ZSet 的一種實現方式是 skipList 與 hashTable 的結合；
Google 的 LevelDB 、Facebook 的 RocksDB ，它們都是使用了跳躍表這種資料結構。
如果要存一組有序的 int 型資料集合，我們可以如何實現？通常我們會想到最常見的兩種實現方案：
1. 陣列
2. 連結串列
跳躍表如上圖，一個有序的連結串列，如果要找值為 50 的節點，需要從第一個節點開始遍歷，查詢最後才能找到值為 50 的節點。
我們給這個連結串列加一層索引，如圖：
我們按照一級索引來查詢（橙色查詢路線），可以發現我們至少可以少遍歷一半的節點。
還覺得有些慢？，那麼再增加一層，再加一層，如圖：
是不是更快地找到我們需要的節點了，當然這裡的節點數量不夠多，如果節點數量非常多，查詢效率提升會更加明顯。
如果需要找中間的某個節點，比如尋找 42 ，過程大概是這樣的：
插入節點看懂了跳躍表的資料結構，那麼就很容易理解節點的插入操作了，基本上兩步操作就可以實現：在最底層的資料鏈表中插入資料，然後調整索引；
其中每一層的索引連結串列中是否需要增加新增的節點，其實並沒有什麼標準答案，我們儘量做到索引的平均分佈即可，常用的就是【隨機判斷】決定是否需要新增或調整索引，當有新節點插入的時候，透過機率演算法判斷這個節點需要插入到幾級節點中。
比如：
底層資料鏈表有 N 個元素，隨機選擇 N/2 個元素作為 1 級索引，隨機選擇 N/4 個元素作為 2 級索引...一直到頂層索引；
新插入資料節點，1/2 機率不插入任何一級索引，1/4 機率返回需要插入 1 級索引，1/8 機率返回需要插入到 2 級索引，以此類推；
這裡要注意一點，插入 2 級索引的時候，同時也需要插入 1 級索引；也就是插入 n 級索引的時候，同時也要插入 1~( n-1 ) 級索引。
總結來說：
可以把跳躍表看成多個有序連結串列（最底層的資料鏈表+多層索引連結串列）；
查詢的過程中，從最長層開始查詢，找到對應的區間再到下一層查詢 ；
每個節點都有兩個指標，分別指向右邊和下邊；
插入新節點時，隨機判斷該節點是否要插入索引，最高插入幾級索引；
插入 n 級索引的時候，同時也要插入 1~(n-1) 級索引；
跳躍表和紅黑樹等平衡樹相比，更容易實現，並且不需要維護平衡性；
Redis 中的 ZSet 的一種實現方式是 skipList 與 hashTable 的結合；
Google 的 LevelDB 、Facebook 的 RocksDB ，它們都是使用了跳躍表這種資料結構。