b树高度计算要怎么实现?

TheDisguiser 2020-07-13 17:01:28 java常见问答 6183

对于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树中,它的高度才能达到最大。

b树高度计算

b树高度计算

以上就是今天文章的全部内容,更多详细java架构师相关内容可以持续关注本网站了解详情。

推荐阅读:

b树与b+树的区别是什么?各自有什么优点?

b树索引的组织结构是什么样的?

b树索引是什么?有哪些概念?