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

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

手機站
千鋒教育

千鋒學(xué)習(xí)站 | 隨時隨地免費學(xué)

千鋒教育

掃一掃進入千鋒手機站

領(lǐng)取全套視頻
千鋒教育

關(guān)注千鋒學(xué)習(xí)站小程序
隨時隨地免費學(xué)習(xí)課程

當前位置:首頁  >  技術(shù)干貨  > 為什么B+樹索引比順序索引文件效率要高?

為什么B+樹索引比順序索引文件效率要高?

來源:千鋒教育
發(fā)布人:xqq
時間: 2023-10-11 04:52:37 1696971157

一、為什么B+樹索引比順序索引文件效率要高

B+樹進化具有的優(yōu)點

索引節(jié)點沒有數(shù)據(jù),比較小,能夠完全加載到內(nèi)存中而且葉子節(jié)點之間都是鏈表的結(jié)構(gòu),所以B+Tree也是可以支持范圍查詢的,而B樹每個節(jié)點key和data在一起,則無法區(qū)間查找B+樹中因為數(shù)據(jù)都在葉子節(jié)點,每次查詢的時間復(fù)雜度是穩(wěn)定的,因此穩(wěn)定性保證了

B+樹的檢索過程

我們再來看下B+樹的檢索過程

從B+樹的根開始,逐層找到葉子節(jié)點。找到葉子節(jié)點為對應(yīng)的數(shù)據(jù)頁,將數(shù)據(jù)葉加載到內(nèi)存中,通過頁目錄的槽采用二分查找的方式先找到一個粗略的記錄分組。在分組中通過鏈表遍歷的方式進行記錄的查找。

B+樹頁節(jié)點結(jié)構(gòu)

將所有的記錄分成幾個組, 每組會存儲多條記錄,頁目錄存儲的是槽(slot),槽相當于分組記錄的索引,每個槽指針指向了不同組的最后一個記錄我們通過槽定位到組,再查看組中的記錄

頁的主要作用是存儲記錄,在頁中記錄以單鏈表的形式進行存儲。
單鏈表優(yōu)點是插入、刪除方便,缺點是檢索效率不高,最壞的情況要遍歷鏈表所有的節(jié)點。因此頁目錄中提供了二分查找的方式,來提高記錄的檢索效率。所以B+樹索引比順序索引文件效率要高。

延伸閱讀:

二、為什么要從AVL樹變成B樹

因為內(nèi)存的易失性。一般情況下,我們都會選擇將 user 表中的數(shù)據(jù)和索引存儲在磁盤這種外圍設(shè)備中。

但是和內(nèi)存相比,從磁盤中讀取數(shù)據(jù)的速度會慢上百倍千倍甚至萬倍,所以,我們應(yīng)當盡量減少從磁盤中讀取數(shù)據(jù)的次數(shù)。

另外,從磁盤中讀取數(shù)據(jù)時,都是按照磁盤塊來讀取的,并不是一條一條的讀。

如果我們能把盡量多的數(shù)據(jù)放進磁盤塊中,那一次磁盤讀取操作就會讀取更多數(shù)據(jù),那我們查找數(shù)據(jù)的時間也會大幅度降低。

如果我們用樹這種數(shù)據(jù)結(jié)構(gòu)作為索引的數(shù)據(jù)結(jié)構(gòu),那我們每查找一次數(shù)據(jù)就需要從磁盤中讀取一個節(jié)點,也就是我們說的一個磁盤塊。

我們都知道平衡二叉樹可是每個節(jié)點只存儲一個鍵值和數(shù)據(jù)的。那說明什么?說明每個磁盤塊僅僅存儲一個鍵值和數(shù)據(jù)!那如果我們要存儲海量的數(shù)據(jù)呢?

可以想象到二叉樹的節(jié)點將會非常多,高度也會極其高,我們查找數(shù)據(jù)時也會進行很多次磁盤 IO,我們查找數(shù)據(jù)的效率將會極低

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

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

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是針對車這個垂直領(lǐng)域,(軟件)產(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
快速通道