首页 / Mysql / B-Tree的性质介绍

B-Tree的性质介绍

B-树是一种常见的数据结构。和他一起的还有B+树。在这里,需要澄清一下概念。B树,B-树,B+树有什么区别?他们有什么关系呢?

B-树是一种常见的数据结构。和他一起的还有B+树。

在这里,需要澄清一下概念。B树,B-树,B+树有什么区别?他们有什么关系呢?

其实,从数据结构来讲只有2种,也就是B-树和B+树。有时候,B-树又称为B树,他们是一个东西。请注意,B-树中间的“-”是连字符,而不是“减号”。英文中是B-Tree,翻译成中文后,也就是B树,有的翻译喜欢把连字符“-”也带着,于是就成了B-树,而B-树被有些读者误读为B减树。

介绍B-树之前,首先看一下一个重要的概念:阶。

一个树的阶,就是这个树中各个节点的子节点个数的最大值。也就是说,如果有的节点有2个子节点,有的节点有4个子节点,最多的有5个子节点,那么,这个树的阶就是5.

从这个角度来讲,二叉树的阶是2.

接下来,我们介绍一下B-树的主要性质。我们假定B-树的阶为m。一个m阶的B-树,要么是一个空树,要么是具有如下性质的树:

1,每个节点最多有m个子节点。最少有m/2(向上取整)个节点。或者这么表述:m/2 <= 子节点个数<= m。但是根节点是例外的,根节点可以最少有2个子节点。

2,每个节点的子节点的个数,比该节点中保存的关键字的个数多1. 也就是,当节点中保存k个关键字时,该节点会有k + 1个子节点(子树)。

3,每个节点中的k个关键字是按照从小到到排列的,分别记为k1,k2,k3,……kk。那么该节点会有k+1个指针,记为p0,p1,p2,……pk。并且,p3所指向的子节点中的所有元素,都大于k3,且都小于k4. 如下图所示。这一点也比较容易理解和记忆,各个指针p整好位于关键字k的插空的位置,所以,插空处的指针指向的子节点的元素的值,就理所当然的应该大于指针左边的元素,小于指针右边的元素。

B-Tree的性质介绍

4,B-树是严格的平衡查找树,它的左右子树的高度是相等的。且叶子节点处于同一层,并且可以用空节点表示。

一个B-树的例子:

B-Tree的性质介绍

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对我是攻城狮的支持。如果你想了解更多相关内容请查看下面相关链接

本文来自网络,不代表我是攻城狮立场,转载请注明出处:https://www.54gcs.cn/sql/mysql/4867.html

helwo作者

上一篇
下一篇

为您推荐

发表评论

联系我们

联系我们

在线咨询: QQ交谈

邮箱: web@5vo.cn

工作时间:周一至周五,9:00-17:30,节假日休息
关注微信
微信扫一扫关注我们

微信扫一扫关注我们

手机访问
手机扫一扫打开网站

手机扫一扫打开网站

返回顶部
跳至工具栏