B樹和B+樹是很多資料庫索引采用的資料結構，為什麼會使用B樹，而不采用更常見的二叉樹的呢？
舉個例子,有這麼幾個數字：1,2,3,4,5,6,7,8,9,0,分别生成AVL樹，B樹
二叉樹生出的樹的度為4，而3階B樹高度隻是3.如果B樹的階數再多的話，就可以獲得更小的高度度。
(6階的B樹)
樹的度帶來更深入查詢，會帶來更多的IO讀寫。
除了二叉樹的深度太深的原因，二叉樹對于作業系統IO的讀取也不是特别的友好。二叉樹的節點過于簡單，資訊過于少。當作業系統進行IO操作的時候，最少讀取的位元組數是4K，為了保證IO的讀取性能，也可能進行預讀下個節點等等。
如果二叉樹的一個節點隻有1KB的話，作業系統每次讀取二叉樹的時候，隻有1KB的有效資訊，那這次IO操作的剩餘的3KB就是無效的讀取。
B樹
B樹又稱為多路平衡查找樹，在上面看到了B樹的簡單結構，在真正的檔案存儲結構如下：
B樹的結構可以保證樹的高度不會太高，節點都是一個單元的磁盤塊的資訊，可以充分的利用作業系統中的IO的讀寫和預讀的能力。
在Sqlserver中索引的存儲使用的是B樹 ，而在mysql中使用的是B+Tree.
B+樹
B+樹是B樹的加強形勢，用B+樹表示0-9十個數字結構如下：
B+樹有以下特點：
- 與B樹不同，資料都隻會存在葉子節點，非葉子節點不儲存資料，隻負責查找。
- B+樹葉子節點是有順序的，之間有互相的連接配接
比如在上面的圖檔中，我想找到5對應的資料，具體的查詢過程結果如下：
具體在磁盤上面的結構如下：
B+樹的優點
- 節點可以存儲比B樹更多的關鍵字資料，查詢更具有效率
- B+樹葉子存儲資料，可以做到局部順序的IO讀寫
- B+的葉子節點有順序，是以排序的能力更強
- 查詢複雜度和IO讀寫更加穩定(相對B樹)
(本文完)
點選右上角關注作者，有趣的人在等有趣的你