詳解Redis資料結構之跳躍表

下面由Redis教學專欄給大家詳解Redis資料結構之跳躍表，希望對需要的朋友有幫助！

前言

      跳躍表是有序的資料結構，它透過在每個節點中維持多個指向其他節點的指針，從而達到快速存取節點的目的。這麼說，我們可能很難理解，我們可以先回想一下鍊錶。

一、複習跳躍表

1.1 什麼是跳躍表

    對於單鍊錶來講，即使鍊錶中儲存的資料是有順序的，如果我們要想在其中尋找某個數據，也只能從頭到尾遍歷鍊錶。這樣查找效率就會很低，時間複雜度會很高，是 O(n)。

    如果我們想要提升其尋找效率，可以考慮建立在鍊錶上索引的方式。每兩個結點提取一個結點到上一級，我們把抽出來的那一級叫作索引。

    這個時候，我們假設要找節點8，我們可以先在索引層遍歷，當遍歷到索引層中值為7 的結點時，發現下一個節點是9，那麼要查找的節點8肯定就在這兩個節點之間。我們下降到鍊錶層繼續遍歷就找到了8這個節點。原先我們在單鍊錶中找到8這個節點要遍歷8個節點，而現在有了一級索引後只需要遍歷五個節點。

    從這個例子裡，我們看出，加來一層索引之後，查找一個結點需要遍的結點個數減少了，也就是說查找效率提高了，同理再加一級索引。

    從圖中我們可以看出，尋找效率又有提升。在例子中我們的資料很少，當有大量的資料時，我們可以增加多層索引，其查找效率可以明顯提升。

    像這種鍊錶加上多層索引的結構，就是跳躍表！

二、Redis跳躍表

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

    這裡我們需要思考一個問題－為什麼元素數量比較多​​或成員是比較長的字串的時候Redis要使用跳躍表來實現？

    從上面我們可以知道，跳躍表在鍊錶的基礎上增加了多層索引以提升查找的效率，但其是一個空間換時間的方案，必然會帶來一個問題——索引是佔記憶體的。原始鍊錶中儲存的有可能是很大的對象，而索引結點只需要儲存關鍵值值和幾個指針，並不需要儲存對象，因此當節點本身比較大或元素數量比較多​​的時候，其優勢必然會被放大，而缺點則可以忽略。

2.1 Redis中跳躍表的實作

    Redis的跳躍表由詳解Redis資料結構之跳躍表和skiplist兩個結構定義,其中詳解Redis資料結構之跳躍表結構用於表示跳躍表節點,而zskiplist結構則用於保存跳躍表節點的相關資訊,例如節點的數量,以及指向表頭節點和表尾節點的指標等等。

      上圖展示了一個跳躍表示例,其中最左邊的是 skiplist結構,這個結構包含下列屬性。

• header:指向跳躍表的表頭節點，透過這個指標程式定位表頭節點的時間複雜度就為O(1)

• tail:指向跳躍表的表尾節點,透過這個指標程式定位表尾節點的時間複雜度就為O(1)

• level:記錄目前跳躍表內,層數最大的那個節點的層數(表頭節點的層數不計算在內)，透過這個屬性可以再O(1)的時間複雜度內取得層高最好的節點的層數。

• length:記錄跳躍表的長度,也即是,跳躍表目前包含節點的數量(表頭節點不計算在內)，透過這個屬性，程式可以再O(1)的時間複雜度內返回跳躍表的長度。

  結構右邊的是四個詳解Redis資料結構之跳躍表結構,該結構包含以下屬性

• #層(level):

      節點中用1、2 、L3等字樣標記節點的各層,L1代表第一層,L代表第二層,以此類推。

      每層都有兩個屬性:前進指標和跨度。前進指標用於存取位於表尾方向的其他節點,而跨度則記錄了前進指標所指向節點和當前節點的距離(跨度越大、距離越遠)。在上圖中,連線上帶有數字的箭頭就代表前進指針,而那個數字就是跨度。當程式從表頭向表尾進行遍歷時,訪問會沿著層的前進指標進行。

      每次創建一個新跳躍表節點的時候,程式都根據冪次定律(powerlaw,越大的數出現的機率越小)隨機產生一個介於1和32之間的值作為level數組的大小,這個大小就是層的「高度」。

• 後退(backward)指標：

      節點中以BW字樣標記節點的後退指標,它指向位於目前節點的前一個節點。後退指針在程式從表尾向表頭遍歷時使用。與前進指針不同的是每個節點只有一個後退指針，因此每次只能後退一個節點。

• 分數(score):

      各節點中的1.0、2.0、3.0是節點所保存的分數。在跳躍表中,節點依各自所保存的分數從小到大排列。

• 成員物件(oj):

      各節點中的o1、o2、o3是節點所保存的成員物件。在同一個跳躍表中,各個節點保存的成員物件必須是唯一的,但是多個節點保存的分值卻可以是相同的:分值相同的節點將按照成員物件在字典序中的大小來進行排序,成員物件較小的節點會排在前面(靠近表頭的方向),而成員物件較大的節點則會排在後面(靠近表尾的方向)。

2.2 Redis跳躍表常用操作的時間複雜度

操作	時間複雜度
建立一個跳躍表	O(1)
釋放給定跳躍表以及其中包含的節點	O(N)
#新增給定成員和分數的新節點	平均O (logN),最壞O(logN)(N為跳躍表的長度)
#刪除除跳躍表中包含給定成員和分數值的節點	平均O(logN),最壞O(logN)(N為跳躍表的長度)
#傳回給定成員和分數的節點再表中的排位	平均O(logN),最壞O(logN)(N為跳躍表的長度)
在給定排位上傳回的節點	平均O(logN),最壞O(logN)(N為跳躍表的長度)
給定一個分數範圍,返回跳躍表中第一個符合這個範圍的節點	O(1)
給定一個分數範圍,返回跳躍表中最後一個符合這個範圍的節點	平均O( logN),最壞O(logN)(N為跳躍表的長度)
#給定一個分數範圍,除跳躍表中所有在這個範圍之內的節點	平均O(logN),最壞O(logN)(N為跳躍表的長度)
給定一個排位範圍,鼎除跳躍表中所有在這個範圍內的節點	O(N),N為被除節點數量
給定一個分數範式(range),例如0到15 ,20到28,諸如此類,如果跳氏表中有至少一個節點的分值在這個範間之內,那麼返回1,否則返回0	O(N),N為被除節點數

本文重點

• 跳躍表基於單鍊錶加索引的方式實現
• 跳躍表以空間換時間的方式提升了查找速度
• Redis有序集合在節點元素較大或元素數量較多時使用跳躍表實現
• Redis的跳躍表實作由zskiplist和zskiplistnode兩個結構組成,其中zskiplist用於保存跳躍表資訊(例如表頭節點、表尾節點、長度),而zskiplistnode則用來表示跳躍表節點
• Redis每個跳躍表節點的層高都是1至32之間的隨機數
• 在同一個跳躍表中,多個節點可以包含相同的分數,但每個節點的成員物件必須是唯一的跳躍表中的節點按照分數大小進行排序,當分數相同時,節點按照成員物件的大小進行排序。

小結

    跳躍表可能對我們來說是一種的稍微陌生的資料結構。本篇文章簡單介紹了跳躍表這種資料結構，並且分析了Redis中跳躍表的使用。下篇文章將繼續分享Redis中所用到的資料結構整數集合。請關注!

以上是詳解Redis資料結構之跳躍表的詳細內容。更多資訊請關注PHP中文網其他相關文章！