对于b树来说，高度的计算有时候也是必须要掌握的，小伙伴们知道b树的高度一般该怎么计算吗?让小编带你了解一下吧。
一、解析
一般来说，B-树上的操作时间通常由存取磁盘的时间和CPU计算时间这两部分构成。B-树上大部分基本操作所需访问盘的次数都是取决于树高h。在关键字总数相同的情况下B-树的高度越小，磁盘I/O所花的时间就越少。
相比高速的CPU计算来说，磁盘I/O是要慢得多的，因此它有时会忽略CPU的计算时间，只分析算法所需的磁盘访问次数(。
1)、b-树高度
定理9.1 若n≥1，m≥3，则对任意一棵具有n个关键字的m阶B-树，其树高h至多为：logt((n+1)/2)+1。
由上述定理可知：B-树的高度为O(logtn)。于是在B-树上查找、插入和删除的读写盘的次数为O(logtn)，CPU计算时间为O(mlogtn)。
2)、性能分析
a)、n个结点的平衡的二叉排序的高度H(即lgn)比B-树的高度h约大lgt倍。
例：若m=1024，则lgt=lg512=9。此时若B-树高度为4，则平衡的二叉排序树的高度约为36。显然，若m越大，则B-树高度越小。
b)、若要作为内存中的查找表，B-树却不一定比平衡的二叉排序树好，尤其当m较大时更是如此。
因为查找等操作的CPU计算时间在B-树上是
O(mlogtn)=0(lgn·(m/lgt))
而m/lgt>1，所以m较大时O(mlogtn)比平衡的二叉排序树上相应操作的时间O(lgn)大得多。因此，仅在内存中使用的B-树必须取较小的m。(通常取最小值m=3，此时B-树中每个内部结点可以有2或3个孩子，这种3阶的B-树称为2-3树)。
二、b 树最大高度计算
想要B树的高度达到最大，就意味着在每个节点中，关键字的个数必须要达到最小，这样在容纳相同个数的关键字的B树中，它的高度才能达到最大。
以上就是今天文章的全部内容，更多详细java架构师相关内容可以持续关注本网站了解详情。
推荐阅读：