為什麼需要 SkipList（跳表）
在普通連結清單中查找元素的時候，因為需要周遊查找，是以查詢效率非常低，時間複雜度是O(N)。
是以我們需要跳表。跳表是在連結清單基礎上改進過來的，實作了一種 “多層” 的 有序 連結清單，這樣的好處是能快速定位資料。
跳表的結構設計
如下圖所示，這是一個層級為3的跳表
- 和普通的雙向連結清單一樣，SkipList 都有一個指向上一個節點的指針，也有一個指向下一個節點的指針。
- 但是你會發現，在層次為 3 的跳表中，會有三級指針的存在，而且 SkipList 中元素會按照 score 值升序排序（score 值一樣則按照 ele 排序）
- 一級指針普通連結清單一樣，指向下一個節點（圖中的 L0）
- 二級指針跨度為2，指向的節點與自己間隔了一個節點
- 三級指針跨度為3，指向的節點與自己間隔了兩個節點
這樣的設計會帶來什麼好處呢？
- 假設我們要在普通連結清單中查詢值為 3 的節點，我們需要從頭結點開始，向後周遊1 → 2 → 3 ，三個節點才能找到。時間複雜度為 O(n)O(n)O(n)
- 當使用了 SkipList 這個資料結構之後，我們可以直接通過三級指針（L2），直接找到這個節點（建立在元素有序的情況下，類似于二分查找一步一步縮小範圍）。時間複雜度為 O(logN)O(log N)O(logN)
跳表的節點（zskiplistNode ）
我們來看看跳表的結構體源碼
c複制代碼typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned long span;
} level[];
} zskiplistNode;
其中，
- ele，用于存儲該節點的元素
- score，用于存儲節點的分數（節點按照 score 值排序，score 值一樣則按照 ele 排序）
- *backward，指向上一個節點
而 level[] 就是實作跳表多層次指針的關鍵所在，level 數組中的每一個元素代表跳表的一層，比如 leve[0] 就表示第一層，leve[1] 就表示第二層。zskiplistLevel 結構體裡定義了指向下一個跳表節點的指針** *forward 和用來記錄兩個節點之間的距離 span，如圖所示，
span 跨度有什麼用？
第一眼看到跨度的時候，你可能以為是周遊操作有關，實際上并沒有任何關系，周遊操作隻需要用前向指針（struct zskiplistNode *forward）就可以完成了。
跨度實際上是為了計算這個節點在跳表中的位置。具體怎麼做的呢？
因為跳表中的節點都是按序排列的，那麼計算某個節點位置的時候，從頭節點點到該結點的查詢路徑上，将沿途通路過的所有層的跨度累加起來，得到的結果就是目标節點在跳表中的排位。
舉個例子，查找圖中節點 3 在跳表中的排位，從頭節點開始查找節點 3，查找的過程隻經過了一個層（L2），并且層的跨度是 3，所有節點 3 在跳表中的排位是 3。
跳表（zskiplist ）
跳表的結構如下
c複制代碼 typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
- zskiplistNode *header, *tail ，跳表的頭尾節點
- length，跳表的長度
- level，跳表的最大層數
跳表的查詢過程
- 在使用 ZRANGEBYSCORE key min max進行範圍查詢的時候
- redis 會調用 zslFirstInRange 或 zslLastInRange 函數擷取符合範圍條件的起始節點（正序調用**zslFirstInRange** ，逆序調用**zslLastInRange** ）
- 擷取起始節點之後，進入一個循環，每次疊代時都會檢查節點的分數是否仍在範圍内（如果存在偏移量，跳過指定數量的元素，而不進行分數的檢查），如果不在範圍内，則中止循環。
- 這樣就能擷取指定分數内的所有元素。
- 可在 t_zset.c#genericZrangebyscoreCommand(zrange_result_handler *handler, zrangespec *range, robj *zobj, long offset, long limit, int reverse) 檢視源碼
在 zslFirstInRange （zslLastInRange 類似）中，我們就能看到跳表根據 scroe 值的查詢過程，源碼如下：
c複制代碼 /* Find the first node that is contained in the specified range.
* Returns NULL when no element is contained in the range. */
zskiplistNode *zslFirstInRange(zskiplist *zsl, zrangespec *range) {
zskiplistNode *x;
int i;
/* If everything is out of range, return early. */
if (!zslIsInRange(zsl,range)) return NULL;
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
/* Go forward while *OUT* of range. */
while (x->level[i].forward &&
!zslValueGteMin(x->level[i].forward->score,range))
x = x->level[i].forward;
}
/* This is an inner range, so the next node cannot be NULL. */
x = x->level[0].forward;
serverAssert(x != NULL);
/* Check if score <= max. */
if (!zslValueLteMax(x->score,range)) return NULL;
return x;
}
該函數執行邏輯如下：
- 首先，通過調用 zslIsInRange 函數檢查整個有序集合是否都在範圍之外，如果是，則直接傳回空，表示範圍内不存在滿足條件的節點。
- 初始化變量 x 為跳表的頭節點。
- 從跳表的最高層級開始逆序周遊每個層級，直到達到最底層級。
- 在每個層級中，通過比較節點的分數（score）和範圍的最小值，向前周遊跳表，直到找到第一個在範圍内的節點。
- 最終，變量 x 存儲的是範圍内第一個節點的前一個節點。
- 使用 serverAssert 函數進行斷言，確定變量 x 的下一個節點不為空（如果跳表中存在節點，則下一個節點不應為空）。
- 更新變量 x 為下一個節點，即範圍内的第一個滿足條件的節點。
- 檢查變量 x 的score 是否小于等于範圍的最大值，如果大于最大值，則傳回空，表示範圍内不存在滿足條件的節點。
- 傳回變量 x，即範圍内的第一個滿足條件的節點。
簡單來說在 SkipList 中找到一個元素的步驟如下：
從跳表的頂層開始，從左到右周遊指針，直到找到一個指針指向的值大于或等于目标元素。記錄下該位置作為目前位置。 如果目前位置指向的值等于目标元素，則找到了目标元素，搜尋結束。 如果目前位置的下一個指針存在且指向的值小于目标元素，将目前位置向右移動到下一個指針所指向的位置。重複步驟1。 如果目前位置的下一個指針不存在或指向的值大于目标元素，将目前位置向下移動一層。重複步驟1。