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-树是严格的平衡查找树，它的左右子树的高度是相等的。且叶子节点处于同一层，并且可以用空节点表示。
一个b-树的例子：
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对移动技术网的支持。如果你想了解更多相关内容请查看下面相关链接
如对本文有疑问， 点击进行留言回复！！
我要评论
网友评论