B-Tree的性质介绍
发布时间：2022-03-16 11:59:48 所属栏目：MySql教程 来源：互联网
导读：B-树是一种常见的数据结构。和他一起的还有B+树。 在这里，需要澄清一下概念。B树，B-树，B+树有什么区别？他们有什么关系呢？ 其实，从数据结构来讲只有2种，也就是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的插空的位置，所以，插空处的指针指向的子节点的元素的值，就理所当然的应该大于指针左边的元素，小于指针右边的元素。 4，B-树是严格的平衡查找树，它的左右子树的高度是相等的。且叶子节点处于同一层，并且可以用空节点表示。 总结 以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值 （编辑：鹰潭站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
