跳躍表

• • 1. 跳躍表的用處
  • 2. 跳躍表的具體示例
  • • 跳躍表的查找
  • 跳躍表的具體實現
  • 本文重點

1. 跳躍表的用處

有序集合(zset)的底層可以采用數組, 鏈表, 平衡樹等結果來實現, 但是他們都有各自的缺點 . 數組方便查詢, 但不便于插入和刪除, 鏈表方便插入和刪除, 但是不利于查找, 平衡樹/紅黑樹效率高但是實現起來很復雜

所以Redis自己實現了跳躍表來來當做有序集合(zset)的底層實現, 他的查詢復雜度平均O(logN), 最壞O(N), 堪比紅黑樹, 但實現起來遠比紅黑樹簡單

2. 跳躍表的具體示例

我們先來看一下如果用有序鏈表來實現有序集合

插入和刪除為O(1), 但是查找的復雜度為O(N)
但是我們看跳躍表的實現

我們從有序鏈表中選取部分節點, 組成一個新的鏈表如圖中的10 -> 30 -> 50 -> 70 -> null, 當做一級索引
如果一級索引中節點還是很多, 我們可以再從一級索引中選取部分節點, 再組成一個新的鏈表, 并以此作為原始鏈表的二級索引10 -> 50 -> null

跳躍表的查找

那么跳躍表是如何進行查找的呢

優先從高層查找

若當前節點的值, 小于要查找的值, 并且next指針指向大于目標值的節點, 就要降一級尋找, 或者next指針指向了null, 那么也需要降一級查找

跳躍表的具體實現

跳躍表底層使用了zskiplist, 和zskiplistnode兩個結構體來實現
zskiplist

typedef struct zskiplist {struct zskiplistNode *header, *tail;unsigned long length;int level; } zskiplist;

• header 指向跳躍表表頭節點, tail指向表尾節點
• length:記錄跳躍表的長度,也即是,跳躍表目前包含節點的數量(表頭節點不計算在內)
• level:記錄目前跳躍表內,層數最大的那個節點的層數(表頭節點的層數不計算在內)，通過這個屬性可以在O(1)的時間復雜度內獲取層數最高的節點的層數。

typedef struct zskiplistNode {sds ele;double score;// 后退指針struct zskiplistNode *backward;// 層struct zskiplistLevel {// 前進指針struct zskiplistNode *forward;/*** 跨度實際上是用來計算元素排名(rank)的，* 在查找某個節點的過程中，將沿途訪過的所有層的跨度累積起來，* 得到的結果就是目標節點在跳躍表中的排位*/unsigned long span;} level[]; } zskiplistNode;

• backward 指針指向前一個節點, 用于方便尋找數據

• sds動態字符串存儲內容, score存儲分數, 用來排序使用

• level(每個節點的層數) :
  節點中用1、2、L3等字樣標記節點的各個層,L1代表第一層,L代表第二層,以此類推.

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

相當于這是三個節點第一個節點處于第0層, 第二個節點他是可以處于三層, 第三個節點可以處于5層

下圖是根據具體一點的一個跳躍表實現

header指向的是一個層高為32的偽頭結點, 實際鏈表的開端是這個偽頭結點的后一個節點, 根據這個偽頭結點就可以快速的找到層數最高的, 因為其他節點的層數都是要比32小的

本文重點

• 跳躍表基于單鏈表加索引的方式實現
• 跳躍表以空間換時間的方式提升了查找速度
• Redis有序集合在節點元素較大或者元素數量較多時使用跳躍表實現
• Redis的跳躍表實現由 zskiplist和 zskiplistnode兩個結構組成,其中 zskiplist用于保存跳躍表信息(比如表頭節點、表尾節點、長度),而zskiplistnode則用于表示跳躍表節點
• Redis每個跳躍表節點的層高都是1至32之間的隨機數

總結

以上是生活随笔為你收集整理的Redis之跳跃表(面试重点容易考)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。