一 數(shù)據(jù)庫為什么使用B+樹

1. 與二叉樹相比
二叉樹相比于順序查找的確減少了查找次數(shù)，但是在最壞情況下，二叉樹有可能退化為順序查找。而且就二叉樹本身來說，當(dāng)數(shù)據(jù)庫的數(shù)據(jù)量特別大時，其層數(shù)也將特別大。二叉樹的高度一般是log_2^n，B樹的高度是log_t^((n+1)/2) + 1，其高度約比B樹大lgt倍。n是節(jié)點(diǎn)總數(shù)，t是樹的最小度數(shù)。

假如每個盤塊可以正好存放一個B樹的結(jié)點(diǎn)（正好存放2個文件名）。那么一個BTNODE結(jié)點(diǎn)就代表一個盤塊，而子樹指針就是存放另外一個盤塊的地址。

下面，咱們來模擬下B樹索引查找文件29的過程：

• 根據(jù)根結(jié)點(diǎn)指針找到文件目錄的根磁盤塊1，將其中的信息導(dǎo)入內(nèi)存。【磁盤IO操作 1次】
• 此時內(nèi)存中有兩個文件名17、35和三個存儲其他磁盤頁面地址的數(shù)據(jù)。根據(jù)算法我們發(fā)現(xiàn)：17<29<35，因此我們找到指針p2。
• 根據(jù)p2指針，我們定位到磁盤塊3，并將其中的信息導(dǎo)入內(nèi)存?！敬疟PIO操作 2次】
• 此時內(nèi)存中有兩個文件名26，30和三個存儲其他磁盤頁面地址的數(shù)據(jù)。根據(jù)算法我們發(fā)現(xiàn)：26<29<30，因此我們找到指針p2。
• 根據(jù)p2指針，我們定位到磁盤塊8，并將其中的信息導(dǎo)入內(nèi)存。【磁盤IO操作 3次】

此時內(nèi)存中有兩個文件名28，29。根據(jù)算法我們查找到文件名29，并定位了該文件內(nèi)存的磁盤地址。

2. 與B樹相比
B樹在提高IO性能的同時，并沒與解決元素遍歷時效率低下的問題，正是為了解決這個問題，B+數(shù)應(yīng)運(yùn)而生。B+數(shù)只需遍歷葉子節(jié)點(diǎn)即可實(shí)現(xiàn)整棵樹的遍歷，而B樹必須使用中序遍歷按序掃庫，B+樹支持范圍查詢非常方便。這才是數(shù)據(jù)庫選用B+樹的主要原因。

另外，最后說一下，并不是說B+樹就比B樹好，有很多基于頻率的搜索是選用B樹，越頻繁query的結(jié)點(diǎn)越往根上走，前提是需要對query做統(tǒng)計(jì)，而且要對key做一些變化。
無論是B樹還是B+樹由于前邊幾層反復(fù)query，因此早已被加載入內(nèi)存，不會出現(xiàn)讀磁盤IO。一般啟動的時候，就會主動換入內(nèi)存。在內(nèi)存中B+樹并沒有優(yōu)勢，只有在磁盤中B+樹的威力才能顯現(xiàn)。

參考文獻(xiàn)：

B樹高度計(jì)算
B+樹和B樹讀取磁盤過程

總結(jié)

以上是生活随笔為你收集整理的为什么MySQL索引更适合B+树而不是二叉树、B树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。