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

B+樹進(jìn)化具有的優(yōu)點(diǎn)

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

B+樹的檢索過程

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

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

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

將所有的記錄分成幾個(gè)組， 每組會(huì)存儲(chǔ)多條記錄，頁目錄存儲(chǔ)的是槽（slot），槽相當(dāng)于分組記錄的索引，每個(gè)槽指針指向了不同組的最后一個(gè)記錄我們通過槽定位到組，再查看組中的記錄

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

延伸閱讀：

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

因?yàn)閮?nèi)存的易失性。一般情況下，我們都會(huì)選擇將 user 表中的數(shù)據(jù)和索引存儲(chǔ)在磁盤這種外圍設(shè)備中。

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

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

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

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

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

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