與二叉樹，紅黑樹這樣的樹不同，B樹，B+樹，B*樹是n叉樹。

m階B樹的特性：

1. 每一個節(jié)點最多存儲的關(guān)鍵字[m/2+1,m-1]
2. 每一個節(jié)點的孩子節(jié)點的個數(shù)[m/2,m]
3. 根節(jié)點至少有兩個子節(jié)點
4. 每個節(jié)點包括m個指針（A0，A1，A2）和m-1個數(shù)據(jù)域（K0，K1，K2），指針k0表示小于關(guān)鍵字小于A0的記錄，k1表示A0，A1之間的記錄。
5. 每個節(jié)點的子樹中所有的節(jié)點值都小于根節(jié)點
6. 數(shù)據(jù)分布在所有節(jié)點中，如果要遍歷所有的數(shù)據(jù)，則需要進行一次中序遍歷，耗時較長
7. 在B樹中的查找相當于在數(shù)據(jù)中進行一次二分搜索。

m階B+樹：

每個節(jié)點包括m個指針（A0，A1，A2）和m個數(shù)據(jù)域（K0，K1，K2），指針k0指向最小值數(shù)據(jù)為A0的一個鏈表。
在B樹的基礎(chǔ)上，所有的節(jié)點值都在葉子節(jié)點上，通常是一個葉子節(jié)點有多個值，用鏈表連接。
所有的葉子節(jié)點在同一層，每個葉子節(jié)點之間用鏈表鏈接起來。查找全部記錄更加便捷。

m階B*樹：

是B+樹的變體，在相同層的節(jié)點之間用鏈表連接。

小結(jié)

二叉搜索樹：二叉樹，每個結(jié)點只存儲一個關(guān)鍵字，等于則命中，小于走左結(jié)點，大于走右結(jié)點；
B（B-）樹：多路搜索樹，每個結(jié)點存儲M/2到M個關(guān)鍵字，非葉子結(jié)點存儲指向關(guān)鍵字范圍的子節(jié)點。所有關(guān)鍵字在整顆樹中出現(xiàn)，且只出現(xiàn)一次，非葉子結(jié)點可以命中；
B+樹：在B-樹基礎(chǔ)上，為葉子結(jié)點增加鏈表指針，所有關(guān)鍵字都在葉子結(jié)點中出現(xiàn)，非葉子結(jié)點作為葉子結(jié)點的索引；B+樹總是到葉子結(jié)點才命中；
B*樹：在B+樹基礎(chǔ)上，為非葉子結(jié)點也增加鏈表指針，將結(jié)點的最低利用率從1/2提高到2/3；

https://blog.csdn.net/u013411246/article/details/81088914