b樹（Balanced Tree）多路平衡查找樹
所有關鍵字和數(shù)據(jù)分布在整個樹中。
任何關鍵字出現(xiàn)且只出現(xiàn)在一個節(jié)點中。
因為數(shù)據(jù)在所有的節(jié)點上，所以搜索有可能在非葉子節(jié)點結束。
在關鍵字全集內做一次查找，性能逼近二分查找算法。

image.png

B+Tree (B+樹是 B 樹的變體)
數(shù)據(jù)都存儲在葉子節(jié)點上,非葉子節(jié)點數(shù)據(jù)只是主鍵
葉子節(jié)點相互之間又鏈指針,范圍查找效率更高

image.png

mysql為什么使用了b+樹而不是b-樹
由于非葉子節(jié)點不存儲 data，所以一個存儲頁(默認為16k)可以存儲更多的非葉子節(jié)點，也就是說使用 b+樹單次磁盤 I/O拿到的同大小存儲頁中包含的信息量相比 b-樹更大，所以減少了同樣數(shù)據(jù)量下每次查詢的io次數(shù)。
MySQL 是關系型數(shù)據(jù)庫，經常會按照區(qū)間來訪問某個索引列，B+樹的葉子節(jié)點間按順序建立了鏈指針，加強了區(qū)間訪問性，所以 B+樹對索引列上的區(qū)間范圍查詢很友好。而 B 樹的查找,需要子節(jié)點返回到父節(jié)點的查找,效率低.