m取幾就是幾叉平衡樹
描述一顆 B樹時需要指定它的階數,階數表示了一個結點 最多 有多少個孩子結點,一般用字母 M 表示階數。
當 M取 2 時,就是我們常見的二叉搜尋樹。
而B樹,根結點的階數M >= 2(至少有兩個子節點),其他節點數必須 >= 3 。
其實,M階 就是 M樹。
一顆 M樹上,最多有 M 個子樹。例如
2(叉)樹,即內含 1個數據項 和 2 個子樹(這裏的子樹 也叫做 引用、連結等)
3(叉)樹,即內含 2個數據項 和 3 個子樹
4(叉)樹,即內含 3個數據項 和 4 個子樹
5(叉)樹,即內含 4個數據項 和 5 個子樹
故,M(叉)樹,即內含(M-1)個數據項 和 M 個子樹
所以,M階 可理解爲 M(叉)樹,即內含(M-1)個數據項和 M 個子樹。
注意:
在B樹中,M>=3,所以B樹至少是 3(叉)樹(不太嚴謹的說法)
M階,確切的是指 平衡的 M 路查找樹 。