概述

這裡續一下上次講索引時提的問題：為什麼說B+樹比B樹更適合做文件索引呢？下面先從兩張圖來介紹下B樹和B+樹，然後再說下原因。

兩張圖

B樹：

B+樹：

從上面兩張圖我們可以發現以下區別：

1、結構上

B樹中關鍵字集合分佈在整棵樹中，葉節點中不包含任何關鍵字信息，而B+樹關鍵字集合分佈在葉子結點中，非葉節點只是葉子結點中關鍵字的索引；
B樹中任何一個關鍵字只出現在一個結點中，而B+樹中的關鍵字必須出現在葉節點中，也可能在非葉結點中重複出現；

2、性能上

不同於B樹只適合隨機檢索，B+樹同時支持隨機檢索和順序檢索；
B+樹的磁盤讀寫代價更低。B+樹的內部結點並沒有指向關鍵字具體信息的指針，其內部結點比B樹小，盤塊能容納的結點中關鍵字數量更多，一次性讀入內存中可以查找的關鍵字也就越多，相對的，IO讀寫次數也就降低了。而IO讀寫次數是影響索引檢索效率的最大因素。
B+樹的查詢效率更加穩定。B樹搜索有可能會在非葉子結點結束，越靠近根節點的記錄查找時間越短，只要找到關鍵字即可確定記錄的存在，其性能等價於在關鍵字全集內做一次二分查找。而在B+樹中，順序檢索比較明顯，隨機檢索時，任何關鍵字的查找都必須走一條從根節點到葉節點的路，所有關鍵字的查找路徑長度相同，導致每一個關鍵字的查詢效率相當。
（數據庫索引採用B+樹的主要原因是，）B-樹在提高了磁盤IO性能的同時並沒有解決元素遍歷的效率低下的問題。B+樹的葉子節點使用指針順序連接在一起，只要遍歷葉子節點就可以實現整棵樹的遍歷。而且在數據庫中基於範圍的查詢是非常頻繁的，而B樹不支持這樣的操作（或者說效率太低）。

B+樹比B樹更適合做文件索引原因

1、B+樹空間利用率更高，可減少I/O次數

，

一般來說，索引本身也很大，不可能全部存儲在內存中，因此索引往往以索引文件的形式存儲的磁盤上。這樣的話，索引查找過程中就要產生磁盤I/O消耗。而因為B+樹的內部節點只是作為索引使用，而不像B-樹那樣每個節點都需要存儲硬盤指針。

也就是說：B+樹中每個非葉節點沒有指向某個關鍵字具體信息的指針，所以每一個節點可以存放更多的關鍵字數量，即一次性讀入內存所需要查找的關鍵字也就越多，減少了I/O操作。

e.g.假設磁盤中的一個盤塊容納16bytes，而一個關鍵字2bytes，一個關鍵字具體信息指針2bytes。一棵9階B-tree(一個結點最多8個關鍵字)的內部結點需要2個盤快。而B+ 樹內部結點只需要1個盤快。當需要把內部結點讀入內存中的時候，B 樹就比B+ 樹多一次盤塊查找時間(在磁盤中就是盤片旋轉的時間)。

2、增刪文件（節點）時，效率更高，

因為B+樹的葉子節點包含所有關鍵字，並以有序的鏈表結構存儲，這樣可很好提高增刪效率。

3、B+樹的查詢效率更加穩定，

因為B+樹的每次查詢過程中，都需要遍歷從根節點到葉子節點的某條路徑。所有關鍵字的查詢路徑長度相同，導致每一次查詢的效率相當。

MySQL的B-Tree索引（技術上說B+Tree）

在MySQL 中，主要有四種類型的索引，分別為： B-Tree 索引， Hash 索引， Fulltext 索引和 R-Tree 索引。我們主要分析B-Tree 索引。

B-Tree 索引是 MySQL 數據庫中使用最為頻繁的索引類型，除了 Archive 存儲引擎之外的其他所有的存儲引擎都支持 B-Tree 索引。Archive 引擎直到 MySQL 5.1 才支持索引，而且只支持索引單個 AUTO_INCREMENT 列。

不僅僅在 MySQL 中是如此，實際上在其他的很多數據庫管理系統中B-Tree 索引也同樣是作為最主要的索引類型，這主要是因為 B-Tree 索引的存儲結構在數據庫的數據檢索中有非常優異的表現。

一般來說， MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的結構來存儲的，也就是所有實際需要的數據都存放於 Tree 的 Leaf Node(葉子節點) ，而且到任何一個 Leaf Node 的最短路徑的長度都是完全相同的，所以我們大家都稱之為 B-Tree 索引。當然，可能各種數據庫（或 MySQL 的各種存儲引擎）在存放自己的 B-Tree 索引的時候會對存儲結構稍作改造。如 Innodb 存儲引擎的 B-Tree 索引實際使用的存儲結構實際上是 B+Tree，也就是在 B-Tree 數據結構的基礎上做了很小的改造，在每一個Leaf Node 上面出了存放索引鍵的相關信息之外，還存儲了指向與該 Leaf Node 相鄰的後一個 LeafNode 的指針信息（增加了順序訪問指針），這主要是為了加快檢索多個相鄰 Leaf Node 的效率考慮。

篇幅有限，關於B+與B樹索引之間的區別就介紹到這了，大家有空也可以做下相關的實驗來做個驗證。後面會分享更多關於DBA方面的內容，感興趣的朋友可以關注下！！