B树(B树)最大最小高度的推导

如题 自用笔记        如有错误欢迎及时指正

首先给出B树的定义与几个重要性质

一.B树定义与性质

        B树又叫多路平衡查找树&＃xff0c;它克服了平衡二叉树(AVL)每个节点只能存储一个数据元素的弊端&＃xff08;当数据规模庞大时AVL高度过高导致查找性能下降&＃xff09;&＃xff0c;由此&＃xff0c;B树相当于通过减少读盘次数的方式大幅提高了在外存上的查找效率&＃xff0c;常用应用在文件系统索引与关系型数据库方面。

        B树中所有结点中&＃xff0c;其孩子结点个数的最大值称为B树的阶。

一棵B树可以是一棵空树&＃xff0c;也可以是满足如下性质的树&＃xff1a;

        设有一颗m阶B树&＃xff0c;则有&＃xff1a;

1.树中每一个结点至多有m(m>&＃61;2)棵子树;

2.若根节点不是叶子结点&＃xff0c;则至少存在2棵子树&＃xff1b;

3.除根节点外所有非叶子结点至少有棵子树&＃xff1b;

4.所有叶子结点均在同一层上&＃xff0c;并且不附带数据元素(可以看做是外部接点或查询失败的接点&＃xff0c;实际上这些结点不存在)&＃xff1b;

二.B树最大最小高度

给出推导

其核心思路是从B数关键字个数与结点数的关系出发&＃xff0c;列出等式&＃xff0c;解出高度h的表达式。

以上

参考文献&＃xff1a;严蔚敏《数据结构》清华大学出版社&＃xff1b;Thomas H.Cormen等《算法导论》机械工业出版社