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

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

目前創(chuàng)新互聯(lián)公司已為1000多家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)絡(luò)空間、網(wǎng)站托管運(yùn)營、企業(yè)網(wǎng)站設(shè)計(jì)、宣威網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

前言

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

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

1.1 什么是跳躍表

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

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

這個(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)。原先我們在單鏈表中找到8這個(gè)節(jié)點(diǎn)要遍歷8個(gè)節(jié)點(diǎn)，而現(xiàn)在有了一級索引后只需要遍歷五個(gè)節(jié)點(diǎn)。

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

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

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

二、Redis跳躍表

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

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

從上面我們可以知道，跳躍表在鏈表的基礎(chǔ)上增加了多級索引以提升查找的效率，但其是一個(gè)空間換時(shí)間的方案，必然會帶來一個(gè)問題——索引是占內(nèi)存的。原始鏈表中存儲的有可能是很大的對象，而索引結(jié)點(diǎn)只需要存儲關(guān)鍵值值和幾個(gè)指針，并不需要存儲對象，因此當(dāng)節(jié)點(diǎn)本身比較大或者元素?cái)?shù)量比較多的時(shí)候，其優(yōu)勢必然會被放大，而缺點(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í),訪問會沿著層的前進(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)按各自所保存的分值從小到大排列。

• 成員對象(oj):

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

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

操作	時(shí)間復(fù)雜度
創(chuàng)建一個(gè)跳躍表	O(1)
釋放給定跳躍表以及其中包含的節(jié)點(diǎn)	O(N)
添加給定成員和分值的新節(jié)點(diǎn)	平均O(logN),最壞O(logN)(N為跳躍表的長度)
刪除除跳躍表中包含給定成員和分值的節(jié)點(diǎn)	平均O(logN),最壞O(logN)(N為跳躍表的長度)
返回給定成員和分值的節(jié)點(diǎn)再表中的排位	平均O(logN),最壞O(logN)(N為跳躍表的長度)
返回在給定排位上的節(jié)點(diǎn)	平均O(logN),最壞O(logN)(N為跳躍表的長度)
給定一個(gè)分值范圍,返回跳躍表中第一個(gè)符合這個(gè)范圍的節(jié)點(diǎn)	O(1)
給定一個(gè)分值范圍,返回跳躍表中最后一個(gè)符合這個(gè)范圍的節(jié)點(diǎn)	平均O(logN),最壞O(logN)(N為跳躍表的長度)
給定一個(gè)分值范圍,除跳躍表中所有在這個(gè)范圍之內(nèi)的節(jié)點(diǎn)	平均O(logN),最壞O(logN)(N為跳躍表的長度)
給定一個(gè)排位范圍,鼎除跳躍表中所有在這個(gè)范圍之內(nèi)的節(jié)點(diǎn)	O(N),N為被除節(jié)點(diǎn)數(shù)量
給定一個(gè)分值范固(range),比如0到15,20到28,諸如此類,如果跳氏表中有至少一個(gè)節(jié)點(diǎn)的分值在這個(gè)范間之內(nèi),那么返回1,否則返回0	O(N),N為被除節(jié)點(diǎn)數(shù)量

本文重點(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)的成員對象必須是唯一的跳躍表中的節(jié)點(diǎn)按照分值大小進(jìn)行排序,當(dāng)分值相同時(shí),節(jié)點(diǎn)按照成員對象的大小進(jìn)行排序。

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

本文名稱：Redis數(shù)據(jù)結(jié)構(gòu)之跳躍表是什么
鏈接地址：http://bm7419.com/article6/pcojig.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、Google、品牌網(wǎng)站制作、定制網(wǎng)站、虛擬主機(jī)、網(wǎng)站收錄

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)