部分參考：B樹和B+樹的差別

MySQL為什麼使用樹結構？

1. 檔案很大，不可能全部存儲在記憶體中，故要存儲到磁盤上
2. 索引的結構組織要盡量減少查找過程中磁盤I/O的存取次數（為什麼使用B-/+Tree，還跟磁盤存取原理有關。）
3. 局部性原理與磁盤預讀，預讀的長度一般為頁（page）的整倍數，（在許多作業系統中，頁大小通常為4k）
4. 資料庫系統巧妙利用了磁盤預讀原理，将一個節點的大小設為等于一個頁，這樣每個節點隻需要一次I/O就可以完全載入，(由于節點中有兩個數組，是以位址連續)。而紅黑樹這種節構，高度明顯要深的多。由于邏輯上很近的節點（父子）實體上可能很遠，無法利用局部性。

B樹和B+樹的差別：

1. B樹的每個節點都存儲了key和data，而B+樹的data存儲在葉子節點上。

   B+樹非葉子節點僅存儲key不存儲data，這樣一個節點就可以存儲更多的key。可以使得B+樹相對B樹來說更矮（IO次數就是樹的高度），是以與磁盤交換的IO操作次數更少。

2. B+樹所有葉子節點構成一個有序連結清單，按主鍵排序來周遊全部記錄，能更好支援範圍查找。

   由于資料順序排列并且相連，是以便于區間查找和搜尋。而B樹則需要進行每一層的遞歸周遊。相鄰的元素可能在記憶體中不相鄰，是以緩存命中性沒有B+樹好。