m阶b树m指的什么意思 tree命令使用

毕业照2022-08-04 10:11:563309

在数据结构中m阶B树是什么意思呀？B-树的定义，二叉树的阶数是什么？“m阶B树”这里的“m阶”是什么意思？m阶b树是什么意思？b tree 和 b+ tree 的区别，什么是树的阶数？

本文导航

数据结构中树的深度与高度
多叉树的定义
二叉树的深度和层数一样吗
什么是一级树形
tree命令使用
树的直径以什么高度计算

数据结构中树的深度与高度

B-树的定义

　一棵m(m≥3)阶的B-树是满足如下性质的m叉树：

(1)每个结点至少包含下列数据域：

(j，P 0 ，K l ，P 1 ，K 2 ，…，K i ，P i )

其中：

j为关键字总数

K i (1≤i≤j)是关键字，关键字序列递增有序：K 1 <K 2 <…<K i 。

P i (0≤i≤j)是孩子指针。对于叶结点，每个P i 为空指针。

注意：

　 ①实用中为节省空间，叶结点中可省去指针域P i ，但必须在每个结点中增加一个标志域leaf，其值为真时表示叶结点，否则为

内部结点。

　 ②在每个内部结点中，假设用keys(Pi)来表示子树Pi中的所有关键字，则有：

　 keys(P 0 )<K 1 <keys(P 1 )<K 2 <…<K i <keys(P i )

即关键字是分界点，任一关键字Ki左边子树中的所有关键字均小于K i ，右边子树中的所有关键字均大于K i 。

(2)所有叶子是在同一层上，叶子的层数为树的高度h。

(3)每个非根结点中所包含的关键字个数j满足：

(4)若树非空，则根至少有1个关键字，故若根不是叶子，则它至少有2棵子树。根至多有m-1个关键字，故至多有m棵子树。

多叉树的定义

B-树是一种多路搜索树（并不一定是二叉的）1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树（或B-树、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-树中，每个结点中关键字从小到大排列，并且当该结点的孩子是非叶子结点时，该k-1个关键字正好是k个孩子包含的关键字的值域的分划。因为叶子结点不包含关键字，所以可以把叶子结点看成在树里实际上并不存在外部结点，指向这些外部结点的指针为空，叶子结点的数目正好等于树中所包含的关键字总个数加1。B-树中的一个包含n个关键字，n+1个指针的结点的一般形式为：（n,P0,K1,P1,K2,P2,…,Kn,Pn）其中，Ki为关键字，K1<K2<…<Kn, Pi 是指向包括Ki到Ki+1之间的关键字的子树的指针。

二叉树的深度和层数一样吗

二叉树的阶数是一个节点的子节点数目的最大值。对于一棵m阶B-tree，每个结点至多可以拥有m个子结点。

各结点的关键字和可以拥有的子结点数都有限制，规定m阶B-tree中，根结点至少有2个子结点，除非根结点为叶子节点；

相应的，根结点中关键字的个数为1~m-1，比节点数目少一个；非根结点至少有[m/2]（[]，向上取整）个子结点，相应的，关键字个数为[m/2]-1~m-1。

扩展资料

1、M为树的阶数，B-树或为空树，否则满足下列条件：定义任意非叶子结点最多只有M个儿子；且M>2；

2、根结点的儿子数为[2, M]；

3、除根结点以外的非叶子结点的儿子数为[M/2, M]；

4、每个结点存放至少M/2（取上整）-1和至多M-1个关键字；（至少2个关键字,根节点至少一个关键字）；

5、非叶子结点的关键字个数=指向儿子的指针个数-1；

6、非叶子结点的关键字：K[1], K[2], …, K[m-1]，m<M+1；且K[i]< K[i+1] ；

7、非叶子结点的指针：P[1], P[2], …, P[m]；其中P[1]指向关键字小于K[1]的子树，P[m]指向关键字大于K[m-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；

参考资料来源：百度百科-阶数

什么是一级树形

m阶为一节点至多有m棵子树

，也就是说B树上的结点最多只能有m棵子树。。。

tree命令使用

一、B树的起源

B树，最早是由德国计算机科学家Rudolf Bayer等人于1972年在论文《Organization and Maintenance of Large Ordered Indexes》提出的，不过我去看了看原文，发现作者也没有解释为什么就叫B-trees了，所以把B树的B，简单地解释为Balanced或者Binary都不是特别严谨，也许作者就是取其名字Bayer的首字母命名的也说不定啊……

二、B树长啥样

还是直接看图比较清楚，图中所示，B树事实上是一种平衡的多叉查找树，也就是说最多可以开m个叉（m>=2），我们称之为m阶b树，为了体现本博客的良心之处，不同于其他地方都能看到2阶B树，这里特意画了一棵5阶B树。

总的来说，m阶B树满足以下条件：

每个节点至多可以拥有m棵子树

根节点，只有至少有2个节点（要么极端情况，就是一棵树就一个根节点，单细胞生物，即是根，也是叶，也是树)

非根非叶的节点至少有的Ceil(m/2)个子树(Ceil表示向上取整，图中5阶B树，每个节点至少有3个子树，也就是至少有3个叉)

非叶节点中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]，，其中n表示该节点中保存的关键字个数，K为关键字且Ki<Ki+1，A为指向子树根节点的指针

从根到叶子的每一条路径都有相同的长度，也就是说，叶子节在相同的层，并且这些节点不带信息，实际上这些节点就表示找不到指定的值，也就是指向这些节点的指针为空

B树的查询过程和二叉排序树比较类似，从根节点依次比较每个结点，因为每个节点中的关键字和左右子树都是有序的，所以只要比较节点中的关键字，或者沿着指针就能很快地找到指定的关键字，如果查找失败，则会返回叶子节点，即空指针

例如查询图中字母表中的K

从根节点P开始，K的位置在P之前，进入左侧指针

左子树中，依次比较C、F、J、M，发现K在J和M之间