B-树-高效的多路平衡搜索树

2017-06-11 10:50 阅读 855 次 评论 0 条

B树是为磁盘或其他直接存取的辅助设备而设计的一种多路平衡搜索树,许多数据库系统使用B树或B树的变种来存储信息。

引入B树的原因

前面我们介绍了高效的二叉搜索树AVL树、红黑树,为什么还要出现B树?当你使用AVL、红黑树时,一次只能获取一个键值的信息,鉴于计算机的局部性原理,B树可以至多存储M-1个键值的信息

数据规模大到内存已不足以容纳时,常规的平衡二叉树效率是很低的。因为查找过程对外存的访问次数过多,读取物理地址连续的1000个字节,与读取单个字节几乎没有区别。通过B树这种多路搜索树可以减少定位记录时所经历的中间过程,从而加快存取速度。

B-树的性质

一棵M阶(M>2)的B树,是一棵平衡的M路平衡搜索树,可以是空树或者满足以下性质(理解透了再向下看):

1)根节点至少有两个孩子。

2)每个非根节点至少有M/2(上取整)个孩子,至多有M个孩子。

3)每个非根节点至少有M/2 - 1(上取整)个关键字,至多有M-1个关键字,并且以升序排列。

4)key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间。

5)所有的叶子结点都在同一层。

B-树的结构

B-树的查找

我们使用pair构建一个模板类,第一个数据类型为Node*,表示结点的地址,第二个数据类型为int,表示在B树某个结点的下标。

设计思路:与二叉搜索树的查找类似,如果寻找的key值大于当前节点的值,则向右偏移;若小于节点的值,则到这个节点左边的孩子节点去找。如果节点已经存在,则返回当前节点及下标,若节点不存在,返回当前节点及-1。

调整节点内的元素并插入

我们以插入{10,30,20,40,50,38}为例,取M = 3,即关键字个数最多有两个,图示如下:

B-树的中序遍历

B树的中序遍历思想与二叉搜索树基本一致,从最左边递归遍历即可,但是在循环内部是无法对根节点最后一个元素的子树进行递归,即40,38,50,因此跳出循环后,需要再多递归一次。

销毁B树

B树的销毁与B树的中序遍历思想一模一样,注意节点的最后一个元素就不会出错。

源代码及注释

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:B-树-高效的多路平衡搜索树 | 术与道的分享
分类:编程素养 标签:, ,
1024do.com导航_术与道导航平台

发表评论


表情