B 樹是一種多路平衡查找樹
二叉樹，每個節點支援兩個分支的樹結構，相比于單向連結清單，多了一個分支。
二叉查找樹，在二叉樹的基礎上增加了一個規則，左子樹的所有節點的值都小于它的根節點，右子樹的所有子節點都大于它的根節點。
二叉查找樹會出現斜樹問題，導緻時間複雜度增加，是以又引入了一種平衡二叉樹，它具有二叉查找樹的所有特點，同時增加了一個規則：” 它的左右兩個子樹的高度差的絕對值不超過 1“。平衡二叉樹會采用左旋、右旋的方式來實作平衡。
B 樹是一種多路平衡查找樹
它滿足平衡二叉樹的規則，但是它可以有多個子樹，子樹的數量取決于關鍵字的數量，比如這個圖中根節點有兩個關鍵字 3 和 5，那麼它能夠擁有的子路數量 = 關鍵字數 + 1 。
是以從這個特征來看，在存儲同樣資料量的情況下，平衡二叉樹的高度要大于 B 樹。
B + 樹，其實是在 B 樹的基礎上做的增強
最大的差別有兩個：
- B 樹的資料存儲在每個節點上，而 B + 樹中的資料是存儲在葉子節點，并且通過連結清單的方式把葉子節點中的資料進行連接配接。
- B + 樹的子路數量等于關鍵字數
這個是 B 樹的存儲結構，從 B 樹上可以看到每個節點會存儲資料。
這個是 B + 樹，B + 樹的所有資料是存儲在葉子節點，并且葉子節點的資料是用雙向連結清單關聯的。
B 樹和 B + 樹，一般都是應用在檔案系統和資料庫系統中，用來減少磁盤 IO 帶來的性能損耗。
以 Mysql 中的 InnoDB 為例，當我們通過 select 語句去查詢一條資料時，InnoDB 需要從磁盤上去讀取資料，這個過程會涉及到磁盤 IO 以及磁盤的随機 IO
我們知道磁盤 IO 的性能是特别低的，特别是随機磁盤 IO。
因為，磁盤 IO 的工作原理是，首先系統會把資料邏輯位址傳給磁盤，磁盤控制電路按照尋址邏輯把邏輯位址翻譯成實體位址，也就是确定要讀取的資料在哪個磁道，哪個扇區。
為了讀取這個扇區的資料，需要把磁頭放在這個扇區的上面，為了實作這一個點，磁盤會不斷旋轉，把目标扇區旋轉到磁頭下面，使得磁頭找到對應的磁道，這裡涉及到尋道事件以及旋轉時間。
很明顯，磁盤 IO 這個過程的性能開銷是非常大的，特别是查詢的資料量比較多的情況下。
是以在 InnoDB 中，幹脆對存儲在磁盤塊上的資料建立一個索引，然後把索引資料以及索引列對應的磁盤位址，以 B + 樹的方式來存儲。
如圖所示，當我們需要查詢目标資料的時候，根據索引從 B + 樹中查找目标資料即可，由于 B + 樹分路較多，是以隻需要較少次數的磁盤 IO 就能查找到。