B-tree（多路搜尋樹，并不是二叉的）是一種常見的資料結構。使用B-tree結構可以顯著減少定位記錄時所經曆的中間過程，進而加快存取速度。B-Tree中的B代表平衡（balance），而不是二叉（binary），因為B-Tree樹是從最早的平衡二叉樹演化而來的。這個資料結構一般用于資料庫的索引，綜合效率較高。
B-tree中，每個結點包含：
- 本結點所含關鍵字的個數；
- 指向父結點的指針；
- 關鍵字；
- 指向子結點的指針。
對于一棵m階B-tree，每個結點至多可以擁有m個子結點。各結點的關鍵字和可以擁有的子結點數都有限制，規定m階B-tree中，根結點至少有2個子結點，除非根結點為葉子節點，相應的，根結點中關鍵字的個數為1~m-1；非根結點至少有[m/2]（[]，向上取整）個子結點，相應的，關鍵字個數為[m/2]-1~m-1。
一棵m階的B-Tree有如下特性：
- 每個節點最多有m個孩子。
- 除了根節點和葉子節點外，其它每個節點至少有Ceil(m/2)個孩子。
- 若根節點不是葉子節點，則至少有2個孩子
- 所有葉子節點都在同一層，且不包含其它關鍵字資訊
- 每個非終端節點包含n個關鍵字資訊（P0,P1,…Pn, k1,…kn）
- 關鍵字的個數n滿足：ceil(m/2)-1 <= n <= m-1
- ki(i=1,…n)為關鍵字，且關鍵字升序排序。
-
Pi(i=1,…n)為指向子樹根節點的指針。P(i-1)指向的子樹的所有節點關鍵字均小于ki，但都大于k(i-1)
B-tree有以下特性：
- 關鍵字集合分布在整棵樹中；
- 任何一個關鍵字出現且隻出現在一個結點中；
- 搜尋有可能在非葉子結點結束；
- 其搜尋性能等價于在關鍵字全集内做一次二分查找；
- 自動層次控制。
由于限制了除根結點以外的非葉子結點，至少含有M/2個兒子，確定了結點的至少使用率，其最低搜尋性能為：O（log2N）（N為關鍵字總數）。
是以B-樹的性能總是等價于二分查找（與M值無關），也就沒有B樹平衡的問題；由于M/2的限制，在插入結點時，如果結點已滿，需要将結點分裂為兩個各占M/2的結點；删除結點時，需将兩個不足M/2的兄弟結點合并。
鑒于B-tree具有良好的定位特性，其常被用于對檢索時間要求苛刻的場合，例如：
- B-tree索引是資料庫中存取和查找檔案(稱為記錄或鍵值)的一種方法。
- 硬碟中的結點也是B-tree結構的。與記憶體相比，硬碟必須花成倍的時間來存取一個資料元素，這是因為硬碟的機械部件讀寫資料的速度遠遠趕不上純電子媒體的記憶體。與一個結點兩個分支的二進制樹相比，B-tree利用多個分支（稱為子樹）的結點，減少擷取記錄時所經曆的結點數，進而達到節省存取時間的目的。
資料來源：
B-Tree詳解
https://www.cnblogs.com/qixinbo/p/11048269.html深入了解索引的底層實作原理之BTree索引和B+Tree索引解析及差別
https://baijiahao.baidu.com/s?id=1635778645917488178&wfr=spider&for=pcMySQL索引原理及BTree（B-/+Tree）結構詳解
https://blog.csdn.net/u013967628/article/details/84305511![【MySQL資料庫】資料庫索引事務1.索引2.事務[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)