跳表（Skip List）是一種多層有序鏈表結構，通過引入多級索引加速查找，其核心設計類似于“立體高速公路系統”，底層是原始鏈表，上面有各種高度的"高架橋"。

高層道路跨度大，連接遠方節點；底層道路密集，保留所有細節。

跳表不僅能提高搜索性能，同時也可以提高插入和刪除操作的性能。

它在性能上和紅黑樹，AVL樹不相上下，但是跳表的原理非常簡單，實現也比紅黑樹簡單很多。

跳表就能讓鏈表擁有近乎的接近二分查找的效率的一種數據結構，其原理依然是給上面加若干層索引，優化查找速度，典型的空間換取時間的方式

底層（Level 0）：完整的有序單鏈表，包含所有元素，例如 1 → 3 → 5 → 7 → 9。

上層索引（Level 1~N）：

• 每層節點數約為下層的 1/2（概率性生成，如概率P=0.5時，一般情況下為：0.25(redis使用的就是0.25)，表示的是上一層的節點數=當前層*0.25）。
• 高層節點稀疏但跨度大，底層節點密集。

示例結構（3層跳表）：

Level 2: 1 ---------------------> 9  
Level 1: 1 -----> 5 -----> 7 -----> 9  
Level 0: 1 → 3 → 5 → 7 → 9  

每個跳表節點包含一個值和一個指針數組forward。

這個數組長度就是節點的層級數，指向同層下一個節點。

在Redis的實現中，節點還包含后退指針(backward)和跨度(span)信息。

1.查詢操作

非常的簡單，思想就是二分思想

// search
public SkipNode<T> search(int key) {// 初始化開始節點為頭節點SkipNode<T> p = head;// 在當前的節點不是空的情況下，有三種情況：while (p != null) {if (p.getKey() == key) {// 如果當前節點的key等于要查找的key，則返回當前節點return p;} else if (p.getNext() == null || p.getNext().getKey() >  key) {// 如果右側沒有了，或者右側的key大于要查找的key，則繼續往下找p = p.getDown();} else {p = p.getNext(); // 否則向右找}}return null;
}

2.刪除操作

刪除操作比起查詢稍微復雜一些，但是比插入簡單。

刪除需要改變鏈表結構所以需要處理好節點之間的聯系。對于刪除操作你需要謹記以下幾點：

1. 刪除當前節點和這個節點的前后節點都有關系
2. 刪除當前層節點之后，下一層該key的節點也要刪除，一直刪除到最底層
   

例如上圖刪除10節點，流程如下：

• team=head 從 team 出發，7 < 10 向右
• 右側為null只能向下；
• 右側為10在當前層刪除10節點然后向下繼續查找下一層10節點；
• 8 < 10 向右；第五步右側為10刪除該節點并且team向下。
• team為null說明刪除完畢退出循環。

// delete
public void delete(int key) {SkipNode<T> term = head;  // 初始化當前節點while (term != null) {if (term.getNext() == null || term.getNext().getKey() > key) {// 如果當前節點的右側沒有節點，或者當前節點的右側的key大于要刪除的key// 則繼續往下找term = term.getDown();} else {// 否則，當前節點的key等于要刪除的keyif (term.getNext().getKey() == key) {// 如果當前節點的key等于要刪除的key，則將當前節點的next指向當前節點的next的nextterm.setNext(term.getNext().getNext());term = term.getDown();} else {// 否則，當前節點的key不等于要刪除的key，則繼續向右找term = term.getNext();}}}
}

3 插入操作

插入需要考慮是否插入索引，插入幾層等問題。

由于需要插入刪除所以我們肯定無法維護一個完全理想的索引結構，因為它耗費的代價太高。但我們使用隨機化的方法去判斷是否向上層插入索引。

即產生一個[0-1]的隨機數如果小于0.5就向上插入索引，插入完畢后再次使用隨機數判斷是否向上插入索引。運氣好這個值可能是多層索引，運氣不好只插入最底層(這是100%插入的)。

但是索引也不能不限制高度，我們一般會設置索引最高值如果大于這個值就不往上繼續添加索引了。

具體插入步驟：

步驟1：隨機決定層數java

// 為新節點隨機決定層數
int insertLevel = randomLevel(); // 比如隨機得到3層
private int randomLevel() {int level = 1;// 每次有1/2的概率繼續向上while (Math.random() < 0.5 && level < MAX_LEVEL) {//MAX_LEVEL:系統設定的最高層，不是當前的最高層level++;}return level;
}

步驟2：從最高層開始查找

// 從跳表的最高層開始查找，記錄每層的插入位置
Node[] update = new Node[MAX_LEVEL];
Node current = header;// 從最高層向下查找
for (int i = MAX_LEVEL - 1; i >= 0; i--) {while (current.next[i] != null && current.next[i].value < targetValue) {current = current.next[i];}update[i] = current; // 記錄第i層的插入位置
}

步驟3：逐層插入java

// 從底層開始逐層插入
for (int i = 0; i < insertLevel; i++) {newNode.next[i] = update[i].next[i];update[i].next[i] = newNode;
}

具體示例演示:

• 隨機層數在當前層數內

初始跳表：
Level 3: header ---------------------> 9
Level 2: header -----> 5 -----------> 9  
Level 1: header -----> 5 -----> 7 --> 9
Level 0: header -> 3 -> 5 -> 7 -> 9插入值6，隨機層數為2：步驟1：隨機決定層數 = 2步驟2：從最高層開始查找
- Level 3: header -> 9 (6 < 9)，記錄update[3] = header
- Level 2: header -> 5 -> 9 (6 > 5)，記錄update[2] = 5
- Level 1: header -> 5 -> 7 (6 < 7)，記錄update[1] = 5
- Level 0: header -> 5 -> 7 (6 < 7)，記錄update[0] = 5步驟3：逐層插入（只在Level 1和Level 0插入）
- Level 1: 5 -> 6 -> 7
- Level 0: 5 -> 6 -> 7結果：
Level 3: header ---------------------> 9
Level 2: header -----> 5 -----------> 9  
Level 1: header -----> 5 -> 6 -----> 7 --> 9
Level 0: header -> 3 -> 5 -> 6 -> 7 -> 9

• 隨機層數超過最高層

初始跳表：
Level 3: header ---------------------> 9
Level 2: header -----> 5 -----------> 9  
Level 1: header -----> 5 -----> 7 --> 9
Level 0: header -> 3 -> 5 -> 7 -> 9插入值6，隨機層數為5，當前最高層：4步驟1：隨機決定層數 = 5步驟2：從最高層開始查找
- Level 4: header -> null (6 < null)，記錄update[4] = header
- Level 3: header -> 9 (6 < 9)，記錄update[3] = header
- Level 2: header -> 5 -> 9 (6 > 5)，記錄update[2] = 5
- Level 1: header -> 5 -> 7 (6 < 7)，記錄update[1] = 5
- Level 0: header -> 5 -> 7 (6 < 7)，記錄update[0] = 5步驟3：創建新節點
Node newNode = new Node(6, 5); // 值6，層數5步驟4：從底層開始逐層插入
//由于隨機插入的層數是新的最高層
//所以逐層插入（在Level 4、Level 3、Level 2、Level 1、Level 0插入））- Level 4: header -> 6 -> null
- Level 3: header -> 6 -> 9
- Level 2: header -> 5 -> 6 -> 9
- Level 1: header -> 5 -> 6 -> 7 -> 9
- Level 0: header -> 3 -> 5 -> 6 -> 7 -> 9

為何這樣設計？

1. 查找需要從高層開始，因為高層跨度大
2. 插入需要從底層開始，因為需要維護指針關系

為何要限制最高層數：

1. 內存使用：防止層數過多導致內存浪費
2. 性能考慮：層數過多反而影響性能
3. 實用性：實際應用中很少需要超過32層
4. 概率分析：32層已經足夠處理大量數據