百度百科： > B-tree（多路搜索樹，并不是二叉的）是一種常見的數據結構。使用B-tree結構可以顯著減少定位記錄時所經歷的中間過程，從而加快[存取速度]。按照翻譯，B 通常認為是Balance的簡稱。這個數據結構一般用于數據庫的索引，綜合效率較高。 > B-tree中，每個結點包含： * 1、本結點所含關鍵字的個數； * 2、指向父結點的指針； * 3、關鍵字； * 4、指向子結點的指針； 對于一棵m階B-tree，每個結點至多可以擁有m個子結點。各結點的關鍵字和可以擁有的子結點數都有限制，規定m階B-tree中，根結點至少有2個子結點，除非根結點為葉子節點，相應的，根結點中關鍵字的個數為1~m-1；非根結點至少有[m/2]（[]，向上取整）個子結點，相應的，關鍵字個數為[m/2]-1~m-1。 ## 性能 B-tree有以下特性： * 1、關鍵字集合分布在整棵樹中； * 2、任何一個關鍵字出現且只出現在一個結點中； * 3、搜索有可能在非葉子結點結束； * 4、其搜索性能等價于在關鍵字全集內做一次二分查找； * 5、自動層次控制； 由于限制了除根結點以外的非葉子結點，至少含有M/2個兒子，確保了結點的至少利用率，其最低搜索性能為： 其中，M為設定的非葉子結點最多子樹個數，N為關鍵字總數； 所以B-樹的性能總是等價于二分查找（與M值無關），也就沒有B樹平衡的問題； 由于M/2的限制，在插入結點時，如果結點已滿，需要將結點分裂為兩個各占M/2的結點；刪除結點時，需將兩個不足M/2的兄弟結點合并。 ## 用途 鑒于B-tree具有良好的定位特性，其常被用于對檢索時間要求苛刻的場合，例如： * 1、B-tree索引是數據庫中存取和查找文件(稱為記錄或鍵值)的一種方法。 * 2、硬盤中的結點也是B-tree結構的。與內存相比，硬盤必須花成倍的時間來存取一個數據元素，這是因為硬盤的機械部件讀寫數據的速度遠遠趕不上純電子媒體的內存。與一個結點兩個分支的二元樹相比，B-tree利用多個分支（稱為子樹）的結點，減少獲取記錄時所經歷的結點數，從而達到節省存取時間的目的。 ## B+樹 另外還有一種與此類似的樹結構叫B+樹，像 Berkerly DB , sqlite , mysql 數據庫都使用了B+樹算法處理索引。 B+和B-（即B）是因為每個結點上的關鍵字不同。一個多一個，一個少一個。 對于B+樹，其結點結構與B-tree相同，不同的是各結點的關鍵字和可以擁有的子結點數。如m階B+樹中，每個結點至多可以擁有m個子結點。非根結點至少有[m/2]個子結點，而關鍵字個數比B-tree多一個，為[m/2]~m。 這兩種處理索引的數據結構的不同之處： * 1。B樹中同一鍵值不會出現多次，并且它有可能出現在葉結點，也有可能出現在非葉結點中。而B+樹的鍵一定會出現在葉結點中，并且有可能在非葉結點中也有可能重復出現，以維持B+樹的平衡。 * 2。因為B樹鍵位置不定，且在整個樹結構中只出現一次，雖然可以節省存儲空間，但使得在插入、刪除操作復雜度明顯增加。B+樹相比來說是一種較好的折中。 * 3。B樹的查詢效率與鍵在樹中的位置有關，最大時間復雜度與B+樹相同(在葉結點的時候)，最小時間復雜度為1(在根結點的時候)。而B+樹的時間復雜度對某建成的樹是固定的。