redis數據結構中跳躍表的示例分析

這篇文章將為大家詳細講解有關redis數據結構中跳躍表的示例分析，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

跳躍表定義:

跳躍表（skiplist）是一種有序數據結構，它通過在每個節點中維持多個指向其他節點的指針，從而達到快速訪問節點的目的。

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

跳躍表使用場景:

Redis使用跳躍表作為有序集合鍵的底層實現之一，如果一個有序集合包含的元素數量比較多，又或者有序集合中元素的成員（member）是比較長的字符串時，Redis就會使用跳躍表來作為有序集合鍵的底層實現, 和鏈表、字典等數據結構被廣泛地應用在Redis內部不同，Redis只在兩個地方用到了跳躍表，一個是實現有序集合鍵，另一個是在集群節點中用作內部數據結構，除此之外，跳躍表在Redis里面沒有其他用途。

跳躍表構成:

Redis的跳躍表由redis.h/zskiplistNode和redis.h/zskiplist兩個結構定義。

zskiplistNode結構用于表示跳躍表節點:

?層（level）：節點中用L1、L2、L3等字樣標記節點的各個層，L1代表第一層，L2代表第二層，以此類推。每個層都帶有兩個屬性：前進指針和跨度。前進指針用于訪問位于表尾方向的其他節點，而跨度則記錄了前進指針所指向節點和當前節點的距離。在上面的圖片中，連線上帶有數字的箭頭就代表前進指針，而那個數字就是跨度。當程序從表頭向表尾進行遍歷時，訪問會沿著層的前進指針進行。?后退（backward）指針：節點中用BW字樣標記節點的后退指針，它指向位于當前節點的前一個節點。后退指針在程序從表尾向表頭遍歷時使用。?分值（score）：各個節點中的1.0、2.0和3.0是節點所保存的分值。在跳躍表中，節點按各自所保存的分值從小到大排列。?成員對象（obj）：各個節點中的o1、o2和o3是節點所保存的成員對象。

zskiplist結構:用于保存跳躍表節點的相關信息，比如節點的數量，以及指向表頭節點和表尾節點的指針等等。

?header：指向跳躍表的表頭節點。?tail：指向跳躍表的表尾節點?level：記錄目前跳躍表內，層數最大的那個節點的層數（表頭節點的層數不計算在內）?length：記錄跳躍表的長度，也即是，跳躍表目前包含節點的數量（表頭節點不計算在內

跳躍表展示圖:

zskiplistNod 結構詳細介紹：

?結構定義：

跳躍表節點的level數組可以包含多個元素，每個元素都包含一個指向其他節點的指針，程序可以通過這些層來加快訪問其他節點的速度，一般來說，層的數量越多，訪問其他節點的速度就越快

查詢遍歷過程：

?1）迭代程序首先訪問跳躍表的第一個節點（表頭），然后從第四層的前進指針移動到表中的第二個節點。?2）在第二個節點時，程序沿著第二層的前進指針移動到表中的第三個節點。?3）在第三個節點時，程序同樣沿著第二層的前進指針移動到表中的第四個節點。?4）當程序再次沿著第四個節點的前進指針移動時，它碰到一個NULL，程序知道這時已經到達了跳躍表的表尾，于是結束這次遍歷。

舉個查詢例子：

假如要查詢 數值為3.0的位置，從頭節點出發遍歷到3.0, 沿途經歷的層：查找的過程只經過了一個層，并且層的跨度為3，所以目標節點在跳躍表中的位置為3。是不是很快！

zskiplist 結構詳細介紹：

?結構定義：

通過使用一個zskiplist結構來持有這些節點，程序可以更方便地對整個跳躍表進行處理，比如快速訪問跳躍表的表頭節點和表尾節點，或者快速地獲取跳躍表節點的數量（也即是跳躍表的長度）等信息

跳躍表常見api

關于“redis數據結構中跳躍表的示例分析”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。