## 1. **B樹和B+樹** 一般來說，數據庫的存儲引擎都是采用B樹或者B+樹來實現索引的存儲。首先來看B樹，如圖所示。  B樹是一種多路平衡樹，用這種存儲結構來存儲大量數據，它的整個高度會相比二叉樹來說，會矮很多。 而對于數據庫而言，所有的數據都將會保存到磁盤上，而磁盤I/O的效率又比較低，特別是在隨機磁盤I/O的情況下效率更低。 所以 高度決定了磁盤I/O的次數，磁盤I/O次數越少，對于性能的提升就越大，這也是為什么采用B樹作為索引存儲結構的原因，如圖所示。 而MySQL的InnoDB存儲引擎，它用了一種增強的B樹結構，也就是B+樹來作為索引和數據的存儲結構。 相比較于B樹結構來說，B+樹做了兩個方面的優化，如圖所示。  1. B+樹的所有數據都存儲在葉子節點，非葉子節點只存儲索引。 2. 葉子節點中的數據使用雙向鏈表的方式進行關聯。 ## 2. **原因分析** 我認為，MySQL索引結構采用B+樹，有以下4個原因：  1. **從磁盤I/O效率方面來看：** B+樹的非葉子節點不存儲數據，所以樹的每一層就能夠存儲更多的索引數量，也就是說，B+樹在層高相同的情況下，比B樹的存儲數據量更多，間接會減少磁盤I/O的次數。 2. **從范圍查詢效率方面來看：** 在MySQL中，范圍查詢是一個比較常用的操作，而B+樹的所有存儲在葉子節點的數據使用了雙向鏈表來關聯，所以B+樹在查詢的時候只需查兩個節點進行遍歷就行，而B樹需要獲取所有節點，因此，B+樹在范圍查詢上效率更高。 3. **從全表掃描方面來看：** 因為，B+樹的葉子節點存儲所有數據，所以B+樹的全局掃描能力更強一些，因為它只需要掃描葉子節點。而B樹需要遍歷整個樹。 4. **從自增ID方面來看：** 基于B+樹的這樣一種數據結構，如果采用自增的整型數據作為主鍵，還能更好的避免增加數據的時候，帶來葉子節點分裂導致的大量運算的問題。 ## 3. **總結** 總體來說，我認為技術方案的選型，更多的要根據具體的業務場景來決定，并不一定是說B+樹就是最好的選擇，就像MongoDB里面采用B樹結構，本質上來說，其實是關系型數據庫和非關系型數據庫的差異