m叉树

在计算机科学中，m叉树定义为节点的集合，通常以如下层次结构方式表示。

• 树从根节点开始。
• 树的每个节点都维护一个指向其子节点的指针列表。
• 子节点的数量小于或等于m。

m叉树的典型表示实现了一个包含m个引用（或指针）的数组来存储子节点（注意，m是子节点数量的上限）。

m路搜索树

a. 为空，或者

b. 由包含b (1<=b<m) 个键kb的根节点和一组子树Ta (a = 0..b) 组成，使得

• 如果k是T0中的键，则k <= k1
• 如果k是Ta (0<a<b) 中的键，则ka <= k <= ka+1
• 如果k是Tb中的键，则k > kb，并且
• 所有Ta都是非空的m路搜索树，或者所有Ta都是空的

m叉树图像

与n个节点相关的完全m叉树的高度为ceiling(log_mn)。

m阶B树是m路树，其中

a. 所有叶子都应该在同一层，并且

b. 除根节点和叶子节点外的所有节点至少有m/2个子节点，最多有m个子节点。根节点至少有2个子节点，最多有m个子节点。

Arnab Chakraborty

更新于：2020年1月2日

2K+ 浏览量

开启你的职业生涯

完成课程获得认证

开始学习