m阶b树是什么意思

问题描述

精选答案

m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：

1、根结点至少有两个子女；

2、每个非根节点所包含的关键字个数 j 满足：┌m/2┐-1≤ j≤ m-1；

3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数k 满足：┌m/2┐≤k≤m ；

4、所有的叶子结点都位于同一层。

在B树中查找给定关键字的方法是，首先把根结点取来，在根结点所包含的关键字K1，…，Kn查找给定的关键字（可用顺序查找或二分查找法），若找到等于给定值的关键字，则查找成功。

否则，一定可以确定要查找的关键字在Ki与Ki+1之间，Pi为指向子树根节点的指针，此时取指针Pi所指的结点继续查找，直至找到，或指针Pi为空时查找失败。

B+树为B树的一种变形，比B树具有更广泛的应用，m阶B+树有如下特征：

1、每个结点的关键字个数与孩子个数相等，所有非最下层的内层结点的关键字是对应子树上的最大关键字，最下层内部结点包含了全部关键字。

2、除根结点以外，每个内部结点有m/2到m个孩子。

3、所有叶结点在树结构的同一层，并且不含任何信息(可看成是外部结点或查找失败的结点)，因此，树结构总是树高平衡的。

其他回答

勤劳的工程师

描述一颗 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 路查找树 。

如图所示：