學習筆記-Redis設計與實作-跳躍表 5.1 跳躍表的實作 5.2 跳躍表API 5.3 重點回顧

跳躍表(skiplist)是一種有序資料結構，它通過在每個節點中維持多個指向其他節點的指針，進而達到快速通路節點的目的。

跳躍表支援平均O(logN)、最壞O(N)複雜度的節點查找，還可以通過順序性操作來批量處理節點。

Redis使用跳躍表作為有序結合鍵的底層實作之一，如果一個有序集合包含的元素數量比較多，又或者有序集合中元素的成員(member)是比較長的字元串時，Redis就會使用跳躍表來作為有序集合見的底層實作。

<a href="https://s4.51cto.com/wyfs02/M00/8D/78/wKioL1idXK6gtn1KAAQNSmuPXHY976.png" target="_blank"></a>

zskiplist結構，包含以下屬性：

header：指向跳躍表的表頭節點

tail：指向跳躍表的表尾節點。

level：記錄目前跳躍表内，層數最大的哪個節點的層數(表頭節點的層數不計算在内)。

length：記錄跳躍表的長度，即，跳躍表目前包含節點的數量(表頭節點不計算在内)。

zskiplistNode結構，包含以下屬性：

層(level)：每個層都帶有兩個屬性：前進指針和跨度。前進指針用于通路位于表尾的其他方向的其他節點，而跨度則記錄了前進指針所指向節點和目前節點的距離。

後退(backward)指針：節點中用BW字樣标記節點的後退指針，它指向位于目前節點的前一個節點。後退指針在程式從表尾向表頭周遊時使用。

分值(score)：在跳躍表中，節點按各自所儲存的分值從小到大排列。

成員對象(obj)

表頭節點和其他節點的構造時一樣的。

跳躍表是有序集合的底層實作之一。

Redis的跳躍表實作zskiplist和zskiplistNode兩個結構組成，其中zskiplist用于儲存跳躍表資訊，而zskiplistNode則用于表示跳躍表節點。

每個跳躍表節點的層高都是1至32之間的随機數。

在同一個跳躍表中，多個節點可以包含相同的分值，但每個節點的成員對象必須是唯一的。

跳躍表中的節點按照分值大小進行排序，當分值相同時，節點按照成員對象的大小進行排序。

本文轉自 許大樹 51CTO部落格，原文連結：http://blog.51cto.com/abelxu/1896679，如需轉載請自行聯系原作者