下面由Redis教程欄目給大家詳解Redis數(shù)據(jù)結(jié)構(gòu)之跳躍表，希望對(duì)需要的朋友有所幫助！

創(chuàng)新互聯(lián)堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都做網(wǎng)站、網(wǎng)站設(shè)計(jì)、外貿(mào)營(yíng)銷(xiāo)網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿(mǎn)足客戶(hù)于互聯(lián)網(wǎng)時(shí)代的若羌網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！前言

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

一、復(fù)習(xí)跳躍表1.1 什么是跳躍表

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

如果我們想要提高其查找效率，可以考慮在鏈表上建索引的方式。每?jī)蓚€(gè)結(jié)點(diǎn)提取一個(gè)結(jié)點(diǎn)到上一級(jí)，我們把抽出來(lái)的那一級(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è)例子里，我們看出，加來(lái)一層索引之后，查找一個(gè)結(jié)點(diǎn)需要遍的結(jié)點(diǎn)個(gè)數(shù)減少了，也就是說(shuō)查找效率提高了，同理再加一級(jí)索引。

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

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

二、Redis跳躍表

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

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

從上面我們可以知道，跳躍表在鏈表的基礎(chǔ)上增加了多級(jí)索引以提升查找的效率，但其是一個(gè)空間換時(shí)間的方案，必然會(huì)帶來(lái)一個(gè)問(wèn)題——索引是占內(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)，通過(guò)這個(gè)指針程序定位表頭節(jié)點(diǎn)的時(shí)間復(fù)雜度就為O(1)

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

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

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

結(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代表第二層,以此類(lèi)推。

每個(gè)層都帶有兩個(gè)屬性:前進(jìn)指針和跨度。前進(jìn)指針用于訪(fǎng)問(wèn)位于表尾方向的其他節(jié)點(diǎn),而跨度則記錄了前進(jìn)指針?biāo)赶蚬?jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的距離(跨度越大、距離越遠(yuǎn))。在上圖中,連線(xiàn)上帶有數(shù)字的箭頭就代表前進(jìn)指針,而那個(gè)數(shù)字就是跨度。當(dāng)程序從表頭向表尾進(jìn)行遍歷時(shí),訪(fǎng)問(wèn)會(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ì)象在字典序中的大小來(lái)進(jìn)行排序,成員對(duì)象較小的節(jié)點(diǎn)會(huì)排在前面(靠近表頭的方向),而成員對(duì)象較大的節(jié)點(diǎn)則會(huì)排在后面(靠近表尾的方向)。

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為跳躍表的長(zhǎng)度)刪除除跳躍表中包含給定成員和分值的節(jié)點(diǎn)平均O(logN),最壞O(logN)(N為跳躍表的長(zhǎng)度)返回給定成員和分值的節(jié)點(diǎn)再表中的排位平均O(logN),最壞O(logN)(N為跳躍表的長(zhǎng)度)返回在給定排位上的節(jié)點(diǎn)平均O(logN),最壞O(logN)(N為跳躍表的長(zhǎng)度)給定一個(gè)分值范圍,返回跳躍表中第一個(gè)符合這個(gè)范圍的節(jié)點(diǎn)O(1)給定一個(gè)分值范圍,返回跳躍表中最后一個(gè)符合這個(gè)范圍的節(jié)點(diǎn)平均O(logN),最壞O(logN)(N為跳躍表的長(zhǎng)度)給定一個(gè)分值范圍,除跳躍表中所有在這個(gè)范圍之內(nèi)的節(jié)點(diǎn)平均O(logN),最壞O(logN)(N為跳躍表的長(zhǎng)度)給定一個(gè)排位范圍,鼎除跳躍表中所有在這個(gè)范圍之內(nèi)的節(jié)點(diǎn)O(N),N為被除節(jié)點(diǎn)數(shù)量給定一個(gè)分值范固(range),比如0到15,20到28,諸如此類(lèi),如果跳氏表中有至少一個(gè)節(jié)點(diǎn)的分值在這個(gè)范間之內(nèi),那么返回1,否則返回0O(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)、長(zhǎng)度),而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)行排序。小結(jié)

跳躍表可能對(duì)我們來(lái)說(shuō)是一種的稍陌生的數(shù)據(jù)結(jié)構(gòu)。本篇文章簡(jiǎn)單介紹了跳躍表這種數(shù)據(jù)結(jié)構(gòu)，并且分析了Redis中跳躍表的使用。下篇文章將繼續(xù)分享Redis中用到的數(shù)據(jù)結(jié)構(gòu)整數(shù)集合。敬請(qǐng)關(guān)注!

分享標(biāo)題：詳解Redis數(shù)據(jù)結(jié)構(gòu)之跳躍表
標(biāo)題鏈接：http://m.rwnh.cn/article10/cgiedo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供域名注冊(cè)、網(wǎng)站排名、ChatGPT、網(wǎng)站收錄、電子商務(wù)、網(wǎng)站設(shè)計(jì)

廣告

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