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

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

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

一.B树定义与性质

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

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

一棵B树可以是一棵空树，也可以是满足如下性质的树：

        设有一颗m阶B树，则有：

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

2.若根节点不是叶子结点，则至少存在2棵子树；

3.除根节点外所有非叶子结点至少有棵子树；

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

二.B树最大最小高度

给出推导

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

以上

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

---

这篇好文章是转载于：学新通技术网