一、B+樹(shù)查詢(xún)的穩(wěn)定性為什么重要

首先最大的優(yōu)勢(shì)還是磁盤(pán)IO和范圍，從我個(gè)人的看法看，穩(wěn)定性（每次查詢(xún)必須從根走到葉子節(jié)點(diǎn)）這意味行為可預(yù)估，這在引擎內(nèi)部建立執(zhí)行計(jì)劃時(shí)會(huì)方便控制變量。

為了實(shí)現(xiàn)動(dòng)態(tài)多層索引，通常采用 B-樹(shù) 和 B+樹(shù)。但是，用于索引的 B-樹(shù) 存在缺陷，它的所有中間結(jié)點(diǎn)均存儲(chǔ)的是數(shù)據(jù)指針（指向包含鍵值的磁盤(pán)文件塊的指針），與該鍵值一起存儲(chǔ)在B-樹(shù)的結(jié)點(diǎn)中。這就會(huì)導(dǎo)致可以存儲(chǔ)在 B-樹(shù)中的結(jié)點(diǎn)目數(shù)極大地減少了，從而增加 B-樹(shù)的層數(shù)，進(jìn)而增加了記錄的搜索時(shí)間。

B+樹(shù)通過(guò)僅在樹(shù)的葉子結(jié)點(diǎn)中存儲(chǔ)數(shù)據(jù)指針而消除了上述缺陷。因此，B+樹(shù)的葉結(jié)點(diǎn)的結(jié)構(gòu)與 B-樹(shù)的內(nèi)部結(jié)點(diǎn)的結(jié)構(gòu)完全不同。在這里應(yīng)該注意，由于數(shù)據(jù)指針僅存在于葉子結(jié)點(diǎn)中，因此葉子結(jié)點(diǎn)必須將所有鍵值及其對(duì)應(yīng)的數(shù)據(jù)指針存儲(chǔ)到磁盤(pán)文件塊以便訪(fǎng)問(wèn)。此外，葉子結(jié)點(diǎn)被鏈接磁盤(pán)的某個(gè)位置，以提供對(duì)記錄的有序訪(fǎng)問(wèn)。因此，葉子結(jié)點(diǎn)形成名列前茅級(jí)索引，而內(nèi)部結(jié)點(diǎn)形成多層索引的其他層。葉子結(jié)點(diǎn)的某些關(guān)鍵字 key 也出現(xiàn)在內(nèi)部結(jié)點(diǎn)中，充當(dāng)控制搜索記錄的媒介。

與 B-樹(shù)不同，B+樹(shù)中的結(jié)點(diǎn)存在兩個(gè)階（order）：對(duì)于階 “a” 和 “ b”，一個(gè)用于內(nèi)部結(jié)點(diǎn)，另一個(gè)用于外部（或葉）結(jié)點(diǎn)。

延伸閱讀：

二、B+樹(shù)的優(yōu)點(diǎn)

同為h層的 B-樹(shù)和 B+樹(shù)，B+樹(shù)可以存儲(chǔ)更多的結(jié)點(diǎn)元素，更加 ”矮胖“。這也是 B+樹(shù)最大的優(yōu)勢(shì)坐在，極大地改善了 B-樹(shù)的查找效率。對(duì)于同樣多的記錄，B+樹(shù)的高度會(huì)更矮，并且指針的出現(xiàn)可以幫助 B+樹(shù)快速訪(fǎng)問(wèn)磁盤(pán)記錄且效率非常高?？傊?，就是 B+樹(shù)比 B-樹(shù)更加好，B+樹(shù)的磁盤(pán) I / O 會(huì)更少，相比于 B-樹(shù)的中序遍歷，B+樹(shù)只需要像遍歷單鏈表一樣掃描一遍葉子結(jié)點(diǎn)。