有讀者在 mysql索引為啥要選擇B+樹 (上) 上篇文章中留言總結了選擇 B+ 樹的原因，大體上說對了，今天我們再一起來看看具體的原因。

• 索引為什么要保存在硬盤中

首先要明白幾個概念，服務器存儲一般分內存和硬盤，內存的大小相對于硬盤來說是很小的。內存的訪問速度是納秒級別的，非常快，而硬盤的訪問速度相對內存來說就比較慢了。

不管是訪問內存還是硬盤數據，操作系統都是按數據頁來讀取數據的，即每訪問一次硬盤或內存，只讀取一頁大小的數據，一頁的大小約等于 4 kb，向硬盤讀取數據的操作叫做磁盤 IO。

看到這里你或許會知道了 mysql 索引為啥不保存在內存中了吧，一方面是雖然內存訪問速度快但容量一般都比較小，存不了多少數據，再一個 mysql 需要讓數據持久化，如果服務器斷電或異常重啟會導致數據丟失。

• 怎么讓二叉搜索樹支持區間查詢

上篇文章中提到過二叉搜索樹，為了讓二叉搜索樹也支持區間查詢，我們把二叉樹的葉子節點通過一個雙向鏈表來連接，并且這個鏈表是有序的，注意葉子節點和普通節點是不一樣的，注意看下面的圖。

因此只需要先找到區間的起始值在鏈表中的位置，然后再往后遍歷，直到遍歷到區間的終止值，即可完成區間查詢。如下圖查找 7-30 這個區間的數據。

• 如何提升查詢速度

因為二叉搜索樹保存在硬盤中，我們每訪問一個節點，就對應著一次硬盤 IO 操作，上面有說過向硬盤讀取數據速度比較慢。因此樹的高度就代表硬盤 IO 操作的次數，所以我們要想辦法讓樹的高度變矮，來減少硬盤 IO。

要想樹變矮一些，那就把樹多分一些叉來吧，變成一顆多叉樹。下面分別用二叉樹和五叉樹來存儲 16 條數據，看下樹的高度又怎樣的變化。

根節點一般存儲在內存中，普通節點和葉子結點保存在硬盤中，因此顯然二叉樹的高度為 5，需要 5 次硬盤 IO，而五叉樹的高度為 2，查詢一個數據只需要 2 次硬盤 IO。

當然這僅僅是一個小數據的例子，如果有一億條數據，我們構建一個 100 叉樹，這棵樹的高度也只有 3，因此多叉樹能大大降低硬盤 IO，提升查詢速度。

那么問題又來了，對于相同的數據量，是不是構建的多叉樹的叉越多越好呢，因為叉越多樹的高度就會越矮。

上面有說過操作系是按數據頁大小來訪問硬盤的，每次 IO 只讀取一個數據頁大小的數據，如果要讀取的數據大于一個數據頁，則會導致多次 IO。因此我們要盡量讓每個節點的數據大小剛好等于一個數據頁大小，即每訪問一個節點只需一次 IO。

• 插入和刪除數據怎么辦

上面講的其實都是為了提高查詢性能的，mysql 通常還有插入和刪除操作的，這里我們再簡單說一下 B+ 樹如何處理插入和刪除節點的操作。

這里我們把多叉樹稱作 m 叉樹，這個 m 值是通過數據頁大小和節點數計算出來的，盡量保證每訪問一個節點就是一個數據頁的大小，而且每個節點最多只有 m 個子節點。

現在我們要往數據庫中插入新的數據，即要往 m 叉樹中插入新的節點，這可能就會導致某些節點的子節點個數大于 m，也就會導致該節點大小大于一個數據頁，訪問該節點就需要多次 IO。

為了解決這個問題，m 叉樹會把該節點分裂成兩個節點，然后改分裂操作又會導致其父節點的子節點數可能超過 m，我們再用同樣的方法分裂節點，一直影響到根節點。

刪除操作也是類似的思想，如果有頻繁的刪除節點，就會導致某些節點的子節點過少，就會浪費存儲空間并降低查詢效率。所以就要想辦法讓這些節點合并起來，合并的話就有可能會導致其子節點數超過 m，超過的話就再用上面的分裂方法分裂子節點。

關于節點分裂和合并操作就簡單說這些了，也不畫圖了，知道這個處理思想就好了。

下面再總結一下 B+ 樹：

B+ 樹就是一種多叉樹，是由二叉搜索樹不斷演變過來的，為了滿足區間快速查詢，B+ 樹的葉子節點通過雙向鏈表串聯起來。

這里使用雙向鏈表是為了支持順序和倒序查詢，雖然雙向鏈表相對于單向鏈表雖然會浪費一倍的指針空間，但是在硬盤中這點空間幾乎微乎其微，用這點空間換時間是一件很值得的事情。

B+ 樹的子節點數不超過 m 個，同時也不能少于 m/2 個，一旦超過就需要分裂，一旦少于就需要合并。

關于 mysql InnoDB 引擎為啥要選擇 B+ 樹就寫到這了，文中圖片來源于極客時間《數據結構與算法之美》專欄。對文章如有疑問，歡迎留言交流，如文章有描述不當之處，也希望大家批評指出。如文章對你有幫助，點個贊再走哈，感謝支持。