国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質(zhì)的職業(yè)教育機構(gòu)

手機站
千鋒教育

千鋒學習站 | 隨時隨地免費學

千鋒教育

掃一掃進入千鋒手機站

領取全套視頻
千鋒教育

關注千鋒學習站小程序
隨時隨地免費學習課程

當前位置:首頁  >  技術干貨  > 為什么Redis一定要用跳表來實現(xiàn)有序集合?

為什么Redis一定要用跳表來實現(xiàn)有序集合?

來源:千鋒教育
發(fā)布人:xqq
時間: 2023-10-11 04:40:06 1696970406

一、為什么Redis一定要用跳表來實現(xiàn)有序集合

跳表的全稱是跳躍表,它的基礎是有序鏈表,在有序鏈表的基礎上,增加多級索引,實現(xiàn)快速查找。跳表的所有額外索引結(jié)點總數(shù)為 n2+n4+n8+…+4+2=n?2n2+n4+n8+…+4+2=n?2,所以跳表的空間復雜度為 O(n)O(n)。

用跳表查找效率到底可以提升多少

前面我講過,算法的執(zhí)行效率可以通過時間復雜度來度量,這里依舊可以用。我們知道,在一個單鏈表中查詢某個數(shù)據(jù)的時間復雜度是 O(n)。那在一個具有多級索引的跳表中,查詢某個數(shù)據(jù)的時間復雜度是多少呢?

這里先來看一個問題,如果鏈表里有 n 個結(jié)點,會有多少級索引呢?

按照我們剛才講的,每兩個結(jié)點會抽出一個結(jié)點作為上一級索引的結(jié)點,那名列前茅級索引的結(jié)點個數(shù)大概就是 n/2,第二級索引的結(jié)點個數(shù)大約就是 n/4,第三級索引的結(jié)點個數(shù)大約就是 n/8,依次類推,也就是說,第 k 級索引的結(jié)點個數(shù)是第 k-1 級索引的結(jié)點個數(shù)的 1/2,那第 k 級索引結(jié)點的個數(shù)就是 n/(2k)。

假設索引有 h 級,較高級的索引有 2 個結(jié)點。通過上面的公式,我們可以得到 n/(2h)=2,從而求得 h=log2n-1。如果包含原始鏈表這一層,整個跳表的高度就是 log2n。

我們在跳表中查詢某個數(shù)據(jù)的時候,如果每一層都要遍歷 m 個結(jié)點,那在跳表中查詢一個數(shù)據(jù)的時間復雜度就是 O(m*logn)。那這個 m 的值是多少呢?按照前面這種索引結(jié)構(gòu),我們每一級索引都非常多只需要遍歷 3 個結(jié)點,也就是說 m=3,為什么是 3 呢?這里解釋一下:

假設我們要查找的數(shù)據(jù)是 x,在第 k 級索引中,我們遍歷到 y 結(jié)點之后,發(fā)現(xiàn) x 大于 y,小于后面的結(jié)點 z,所以我們通過 y 的 down 指針,從第 k 級索引下降到第 k-1 級索引。在第 k-1 級索引中,y 和 z 之間只有 3 個結(jié)點(包含 y 和 z),所以,我們在 K-1 級索引中非常多只需要遍歷 3 個結(jié)點,依次類推,每一級索引都非常多只需要遍歷 3 個結(jié)點。通過上面的分析,我們得到 m=3,所以在跳表中查詢?nèi)我鈹?shù)據(jù)的時間復雜度就是 O(logn)。這個查找的時間復雜度跟二分查找是一樣的。換句話說,我們其實是基于單鏈表實現(xiàn)了二分查找,但是,有一個比較雞肋的地方就是:這種查詢效率的提升,前提是建立了很多級索引,即需要占用額外的內(nèi)存空間。

延伸閱讀:

二、跳表內(nèi)存使用情況

比起單純的單鏈表,跳表需要存儲多級索引,肯定要消耗更多的存儲空間。下面來看下跳表的空間復雜度。

假設原始鏈表大小為 n,那名列前茅級索引大約有 n/2 個結(jié)點,第二級索引大約有 n/4 個結(jié)點,以此類推,每上升一級就減少一半,直到剩下 2 個結(jié)點。如果我們把每層索引的結(jié)點數(shù)寫出來,就是一個等比數(shù)列。

原始鏈表大小為n,每2個節(jié)點取1個,則每層索引的節(jié)點數(shù):n/2, n/4, n/8, … , 8, 4, 2。

這幾級索引的結(jié)點總和就是 n/2+n/4+n/8…+8+4+2=n-2。所以,跳表的空間復雜度是 O(n)。也就是說,如果將包含 n 個結(jié)點的單鏈表構(gòu)造成跳表,我們需要額外再用接近 n 個結(jié)點的存儲空間。那我們有沒有辦法降低索引占用的內(nèi)存空間呢?我們前面都是每兩個結(jié)點抽一個結(jié)點到上級索引,如果我們每三個結(jié)點或五個結(jié)點,抽一個結(jié)點到上級索引,這樣是不是就不用那么多索引結(jié)點了呢?

通過等比數(shù)列求和公式,總的索引結(jié)點大約就是 n/3+n/9+n/27+…+9+3+1=n/2。盡管空間復雜度還是 O(n),但比上面的每兩個結(jié)點抽一個結(jié)點的索引構(gòu)建方法,要減少了一半的索引結(jié)點存儲空間。

實際上,在程序開發(fā)中,我們一般不必太在意索引占用的額外空間。因為當對象比索引結(jié)點大很多時,那索引占用的額外空間就可以忽略了。

聲明:本站稿件版權均屬千鋒教育所有,未經(jīng)許可不得擅自轉(zhuǎn)載。
10年以上業(yè)內(nèi)強師集結(jié),手把手帶你蛻變精英
請您保持通訊暢通,專屬學習老師24小時內(nèi)將與您1V1溝通
免費領取
今日已有369人領取成功
劉同學 138****2860 剛剛成功領取
王同學 131****2015 剛剛成功領取
張同學 133****4652 剛剛成功領取
李同學 135****8607 剛剛成功領取
楊同學 132****5667 剛剛成功領取
岳同學 134****6652 剛剛成功領取
梁同學 157****2950 剛剛成功領取
劉同學 189****1015 剛剛成功領取
張同學 155****4678 剛剛成功領取
鄒同學 139****2907 剛剛成功領取
董同學 138****2867 剛剛成功領取
周同學 136****3602 剛剛成功領取
相關推薦HOT
計算機網(wǎng)絡管理軟件有哪些好用?

1、Nagios CoreNagios Core在全球范圍內(nèi)用于幫助監(jiān)控網(wǎng)絡和跟蹤各種基礎設施。它的主動監(jiān)控功能可以檢測它負責監(jiān)控的服務器上的網(wǎng)絡設備、服務...詳情>>

2023-10-11 06:33:55
oa系統(tǒng)怎么注冊?

一、選擇合適的OA系統(tǒng)首先,需要選擇一款適合自己公司的OA系統(tǒng)。市面上有很多OA系統(tǒng),如用友、金蝶等,不同的OA系統(tǒng)有不同的功能和價格。在選擇...詳情>>

2023-10-11 06:32:35
大整數(shù)類型和一般的整數(shù)類型相比各有什么優(yōu)劣?

一、大整數(shù)類型和一般的整數(shù)類型相比大整數(shù)類型和一般的整數(shù)類型相比優(yōu)點是不會溢出,能表示任意長度的數(shù)字做各種精度的運算。缺點是沒有直接的...詳情>>

2023-10-11 06:22:59
功能安全開發(fā)與ASPICE和CMMI之間有什么樣的聯(lián)系?

一、功能安全開發(fā)與ASPICE和CMMI之間的聯(lián)系CMMI是產(chǎn)品和系統(tǒng)開發(fā)的通用模型,ASPICE是針對車這個垂直領域,(軟件)產(chǎn)品和系統(tǒng)開發(fā)的標準。ASPI...詳情>>

2023-10-11 05:59:32
在C語言下數(shù)組array與鏈表linklist各自的優(yōu)點和缺陷是什么?

一、在C語言下數(shù)組array與鏈表linklist各自的優(yōu)點和缺陷數(shù)組可以通過下標訪問,隨機訪問效率高,鏈表需要通過指針遍歷,訪問效率低。數(shù)組在分配...詳情>>

2023-10-11 05:43:25