Redis數(shù)據(jù)結(jié)構(gòu)之跳躍表是什么

小編給大家分享一下Redis數(shù)據(jù)結(jié)構(gòu)之跳躍表是什么，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

前言

跳躍表是一種有序的數(shù)據(jù)結(jié)構(gòu)，它通過在每個(gè)節(jié)點(diǎn)中維持多個(gè)指向其他節(jié)點(diǎn)的指針，從而達(dá)到快速訪問節(jié)點(diǎn)的目的。這么說，我們可能很難理解，我們可以先回憶一下鏈表。

一、復(fù)習(xí)跳躍表

1.1 什么是跳躍表

對(duì)于一個(gè)單鏈表來講，即便鏈表中存儲(chǔ)的數(shù)據(jù)是有序的，如果我們要想在其中查找某個(gè)數(shù)據(jù)，也只能從頭到尾遍歷鏈表。這樣查找效率就會(huì)很低，時(shí)間復(fù)雜度會(huì)很高，是 O(n)。

如果我們想要提高其查找效率，可以考慮在鏈表上建索引的方式。每?jī)蓚€(gè)結(jié)點(diǎn)提取一個(gè)結(jié)點(diǎn)到上一級(jí)，我們把抽出來的那一級(jí)叫作索引。

這個(gè)時(shí)候，我們假設(shè)要查找節(jié)點(diǎn)8，我們可以先在索引層遍歷，當(dāng)遍歷到索引層中值為 7 的結(jié)點(diǎn)時(shí)，發(fā)現(xiàn)下一個(gè)節(jié)點(diǎn)是9，那么要查找的節(jié)點(diǎn)8肯定就在這兩個(gè)節(jié)點(diǎn)之間。我們下降到鏈表層繼續(xù)遍歷就找到了8這個(gè)節(jié)點(diǎn)。原先我們?cè)趩捂湵碇姓业?這個(gè)節(jié)點(diǎn)要遍歷8個(gè)節(jié)點(diǎn)，而現(xiàn)在有了一級(jí)索引后只需要遍歷五個(gè)節(jié)點(diǎn)。

從這個(gè)例子里，我們看出，加來一層索引之后，查找一個(gè)結(jié)點(diǎn)需要遍的結(jié)點(diǎn)個(gè)數(shù)減少了，也就是說查找效率提高了，同理再加一級(jí)索引。

從圖中我們可以看出，查找效率又有提升。在例子中我們的數(shù)據(jù)很少，當(dāng)有大量的數(shù)據(jù)時(shí)，我們可以增加多級(jí)索引，其查找效率可以得到明顯提升。

像這種鏈表加多級(jí)索引的結(jié)構(gòu)，就是跳躍表！

二、Redis跳躍表

Redis使用跳躍表作為有序集合鍵的底層實(shí)現(xiàn)之一,如果一個(gè)有序集合包含的元素?cái)?shù)量比較多,又或者有序集合中元素的成員是比較長的字符串時(shí), Redis就會(huì)使用跳躍表來作為有序集合健的底層實(shí)現(xiàn)。

這里我們需要思考一個(gè)問題——為什么元素?cái)?shù)量比較多或者成員是比較長的字符串的時(shí)候Redis要使用跳躍表來實(shí)現(xiàn)？

從上面我們可以知道，跳躍表在鏈表的基礎(chǔ)上增加了多級(jí)索引以提升查找的效率，但其是一個(gè)空間換時(shí)間的方案，必然會(huì)帶來一個(gè)問題——索引是占內(nèi)存的。原始鏈表中存儲(chǔ)的有可能是很大的對(duì)象，而索引結(jié)點(diǎn)只需要存儲(chǔ)關(guān)鍵值值和幾個(gè)指針，并不需要存儲(chǔ)對(duì)象，因此當(dāng)節(jié)點(diǎn)本身比較大或者元素?cái)?shù)量比較多的時(shí)候，其優(yōu)勢(shì)必然會(huì)被放大，而缺點(diǎn)則可以忽略。

2.1 Redis中跳躍表的實(shí)現(xiàn)

Redis的跳躍表由zskiplistNode和skiplist兩個(gè)結(jié)構(gòu)定義,其中 zskiplistNode結(jié)構(gòu)用于表示跳躍表節(jié)點(diǎn),而 zskiplist結(jié)構(gòu)則用于保存跳躍表節(jié)點(diǎn)的相關(guān)信息,比如節(jié)點(diǎn)的數(shù)量,以及指向表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)的指針等等。

上圖展示了一個(gè)跳躍表示例,其中最左邊的是 skiplist結(jié)構(gòu),該結(jié)構(gòu)包含以下屬性。

• header:指向跳躍表的表頭節(jié)點(diǎn)，通過這個(gè)指針程序定位表頭節(jié)點(diǎn)的時(shí)間復(fù)雜度就為O(1)

• tail:指向跳躍表的表尾節(jié)點(diǎn),通過這個(gè)指針程序定位表尾節(jié)點(diǎn)的時(shí)間復(fù)雜度就為O(1)

• level:記錄目前跳躍表內(nèi),層數(shù)最大的那個(gè)節(jié)點(diǎn)的層數(shù)(表頭節(jié)點(diǎn)的層數(shù)不計(jì)算在內(nèi))，通過這個(gè)屬性可以再O(1)的時(shí)間復(fù)雜度內(nèi)獲取層高最好的節(jié)點(diǎn)的層數(shù)。

• length:記錄跳躍表的長度,也即是,跳躍表目前包含節(jié)點(diǎn)的數(shù)量(表頭節(jié)點(diǎn)不計(jì)算在內(nèi))，通過這個(gè)屬性，程序可以再O(1)的時(shí)間復(fù)雜度內(nèi)返回跳躍表的長度。

  結(jié)構(gòu)右方的是四個(gè) zskiplistNode結(jié)構(gòu),該結(jié)構(gòu)包含以下屬性

• 層(level):

  節(jié)點(diǎn)中用1、2、L3等字樣標(biāo)記節(jié)點(diǎn)的各個(gè)層,L1代表第一層,L代表第二層,以此類推。

  每個(gè)層都帶有兩個(gè)屬性:前進(jìn)指針和跨度。前進(jìn)指針用于訪問位于表尾方向的其他節(jié)點(diǎn),而跨度則記錄了前進(jìn)指針?biāo)赶蚬?jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的距離(跨度越大、距離越遠(yuǎn))。在上圖中,連線上帶有數(shù)字的箭頭就代表前進(jìn)指針,而那個(gè)數(shù)字就是跨度。當(dāng)程序從表頭向表尾進(jìn)行遍歷時(shí),訪問會(huì)沿著層的前進(jìn)指針進(jìn)行。

  每次創(chuàng)建一個(gè)新跳躍表節(jié)點(diǎn)的時(shí)候,程序都根據(jù)冪次定律(powerlaw,越大的數(shù)出現(xiàn)的概率越小)隨機(jī)生成一個(gè)介于1和32之間的值作為level數(shù)組的大小,這個(gè)大小就是層的“高度”。

• 后退(backward)指針：

  節(jié)點(diǎn)中用BW字樣標(biāo)記節(jié)點(diǎn)的后退指針,它指向位于當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。后退指針在程序從表尾向表頭遍歷時(shí)使用。與前進(jìn)指針?biāo)煌氖敲總€(gè)節(jié)點(diǎn)只有一個(gè)后退指針，因此每次只能后退一個(gè)節(jié)點(diǎn)。

• 分值(score):

  各個(gè)節(jié)點(diǎn)中的1.0、2.0和3.0是節(jié)點(diǎn)所保存的分值。在跳躍表中,節(jié)點(diǎn)按各自所保存的分值從小到大排列。

• 成員對(duì)象(oj):

  各個(gè)節(jié)點(diǎn)中的o1、o2和o3是節(jié)點(diǎn)所保存的成員對(duì)象。在同一個(gè)跳躍表中,各個(gè)節(jié)點(diǎn)保存的成員對(duì)象必須是唯一的,但是多個(gè)節(jié)點(diǎn)保存的分值卻可以是相同的:分值相同的節(jié)點(diǎn)將按照成員對(duì)象在字典序中的大小來進(jìn)行排序,成員對(duì)象較小的節(jié)點(diǎn)會(huì)排在前面(靠近表頭的方向),而成員對(duì)象較大的節(jié)點(diǎn)則會(huì)排在后面(靠近表尾的方向)。

2.2 Redis跳躍表常用操作的時(shí)間復(fù)雜度

本文重點(diǎn)

• 跳躍表基于單鏈表加索引的方式實(shí)現(xiàn)
• 跳躍表以空間換時(shí)間的方式提升了查找速度
• Redis有序集合在節(jié)點(diǎn)元素較大或者元素?cái)?shù)量較多時(shí)使用跳躍表實(shí)現(xiàn)
• Redis的跳躍表實(shí)現(xiàn)由 zskiplist和 zskiplistnode兩個(gè)結(jié)構(gòu)組成,其中 zskiplist用于保存跳躍表信息(比如表頭節(jié)點(diǎn)、表尾節(jié)點(diǎn)、長度),而zskiplistnode則用于表示跳躍表節(jié)點(diǎn)
• Redis每個(gè)跳躍表節(jié)點(diǎn)的層高都是1至32之間的隨機(jī)數(shù)
• 在同一個(gè)跳躍表中,多個(gè)節(jié)點(diǎn)可以包含相同的分值,但每個(gè)節(jié)點(diǎn)的成員對(duì)象必須是唯一的跳躍表中的節(jié)點(diǎn)按照分值大小進(jìn)行排序,當(dāng)分值相同時(shí),節(jié)點(diǎn)按照成員對(duì)象的大小進(jìn)行排序。

以上是Redis數(shù)據(jù)結(jié)構(gòu)之跳躍表是什么的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！