六、跳表（Skiplist）

跳表是一種高效的動態數據結構，可以用于實現有序集合（Sorted Set，Zset）。與平衡樹相比，跳表具有實現簡單、效率高的優點，因此被 Redis 選用作為有序集合的底層數據結構之一。

1. 跳表的結構設計

跳表通過多級鏈表的形式實現，每一級鏈表都跳過一些元素，從而在查詢時能夠快速跳過不必要的元素。跳表的每個節點包含一個或多個前進指針，這些前進指針指向不同級別的節點，使得跳表具有高效的查詢性能。

節點結構

跳表節點的結構定義如下：

typedef?struct?zskiplistNode?{struct?zskiplistNode?*backward;?// 后退指針，指向前一個節點double?score;???????????????????// 節點的分值，用于排序sds ele;????????????????????????// 節點的元素struct?zskiplistLevel?{struct?zskiplistNode?*forward;?// 前進指針，指向下一個節點unsigned?int?span;?????????????// 跨度，表示當前節點和下一個節點之間的距離} level[];?// 按級別劃分的前進指針數組
} zskiplistNode;

跳表結構

跳表的結構定義如下：

typedef?struct?zskiplist?{struct?zskiplistNode?*header, *tail;?// 跳表的頭節點和尾節點unsigned?long?length;????????????????// 跳表的長度，即節點數量int?level;???????????????????????????// 跳表的最大級別
} zskiplist;

2. 跳表的操作

跳表支持多種操作，包括插入、刪除、查找等。以下是一些常見操作的實現示例：

插入操作

插入新節點時，首先確定新節點的級別，然后在每一級鏈表中找到插入位置，將新節點插入到相應的位置。

zskiplistNode *zslInsert(zskiplist *zsl,?double?score, sds ele)?{zskiplistNode *update[ZSKIPLIST_MAXLEVEL];unsigned?int?rank[ZSKIPLIST_MAXLEVEL];int?i, level;zskiplistNode *x;x = zsl->header;for?(i = zsl->level-1; i >=?0; i--) {rank[i] = i == (zsl->level-1) ??0?: rank[i+1];while?(x->level[i].forward &&?(x->level[i].forward->score < score ||?(x->level[i].forward->score == score &&?sdscmp(x->level[i].forward->ele,ele) <?0))) {rank[i] += x->level[i].span;x = x->level[i].forward;}update[i] = x;}level = zslRandomLevel();if?(level > zsl->level) {for?(i = zsl->level; i < level; i++) {rank[i] =?0;update[i] = zsl->header;update[i]->level[i].span = zsl->length;}zsl->level = level;}x = zslCreateNode(level,score,ele);for?(i =?0; i < level; i++) {x->level[i].forward = update[i]->level[i].forward;update[i]->level[i].forward = x;x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);update[i]->level[i].span = (rank[0] - rank[i]) +?1;}for?(i = level; i < zsl->level; i++) {update[i]->level[i].span++;}x->backward = (update[0] == zsl->header) ??NULL?: update[0];if?(x->level[0].forward)?x->level[0].forward->backward = x;elsezsl->tail = x;zsl->length++;return?x;
}

查找操作

在跳表中查找目標節點時，從最高級別的鏈表開始，通過前進指針逐級向下查找，直到找到目標節點或確認目標節點不存在。

zskiplistNode *zslFind(zskiplist *zsl,?double?score, sds ele)?{zskiplistNode *x;int?i;x = zsl->header;for?(i = zsl->level-1; i >=?0; i--) {while?(x->level[i].forward &&?(x->level[i].forward->score < score ||?(x->level[i].forward->score == score &&?sdscmp(x->level[i].forward->ele,ele) <?0))) {x = x->level[i].forward;}}x = x->level[0].forward;if?(x && score == x->score && sdscmp(x->ele,ele) ==?0) {return?x;}?else?{return?NULL;}
}

刪除操作

刪除節點時，通過查找操作確定節點位置，然后在每一級鏈表中移除該節點，并調整相關節點的前進指針和跨度。

int?zslDelete(zskiplist *zsl,?double?score, sds ele, zskiplistNode **node)?{zskiplistNode *update[ZSKIPLIST_MAXLEVEL];zskiplistNode *x;int?i;x = zsl->header;for?(i = zsl->level-1; i >=?0; i--) {while?(x->level[i].forward &&?(x->level[i].forward->score < score ||?(x->level[i].forward->score == score &&?sdscmp(x->level[i].forward->ele,ele) <?0))) {x = x->level[i].forward;}update[i] = x;}x = x->level[0].forward;if?(x && score == x->score && sdscmp(x->ele,ele) ==?0) {for?(i =?0; i < zsl->level; i++) {if?(update[i]->level[i].forward == x) {update[i]->level[i].span += x->level[i].span -?1;update[i]->level[i].forward = x->level[i].forward;}?else?{update[i]->level[i].span -=?1;}}if?(x->level[0].forward) {x->level[0].forward->backward = x->backward;}?else?{zsl->tail = x->backward;}while?(zsl->level >?1?&& zsl->header->level[zsl->level-1].forward ==?NULL)zsl->level--;zsl->length--;if?(node) *node = x;else?zslFreeNode(x);return?1;}?else?{return?0;}
}

3. 跳表的優點

1. 高效查詢：跳表的查詢性能接近于平衡樹，時間復雜度為 O(log N)。
2. 實現簡單：與紅黑樹等平衡樹相比，跳表的實現相對簡單，容易理解和維護。
3. 動態調整：跳表能夠高效地進行插入和刪除操作，同時保持整體結構的有序性。

4. 跳表的使用示例

以下是一些使用 Redis 跳表實現有序集合的示例，展示了如何利用跳表進行數據的存儲和操作。

插入數據

ZADD myzset 1?"one"
ZADD myzset 2?"two"
ZADD myzset 3?"three"

獲取數據

ZRANGE myzset 0 -1 WITHSCORES
# 1) "one"
# 2) "1"
# 3) "two"
# 4) "2"
# 5) "three"
# 6) "3"

刪除數據

ZREM myzset?"two"
ZRANGE myzset 0 -1 WITHSCORES
# 1) "one"
# 2) "1"
# 3) "three"
# 4) "3"

結論

通過上述解析，我們可以更好地理解跳表的設計思想和實現原理，從而在實際開發中更好地利用跳表提供的優勢。在 Redis 中，跳表通過高效的多級鏈表結構，實現了有序集合的快速插入、刪除和查詢操作，適用于需要有序數據存儲的場景。了解跳表的內部實現，可以幫助我們在實際應用中更好地利用 Redis 的性能和功能。