雅乐网

计算机技术、学习成长

计算机 » 数据结构 » 常用数据结构C++实现(6):B树

常用数据结构C++实现(6):B树

本文介绍的数据结构英文是B-tree,中文写作B-树,其中 – 并不是减号,而是连接符,读作B树。

B-树是一种平衡搜索树,但它的每个结点包含的元素可以多于2个,因此并不是严格意义上的二叉树。

B-树的结点类似如下:

scrn20160117104547

这可以看做二叉搜索树通过多层合并得到的

scrn20160117111953

 

相比与二叉树,B树显得更矮,更胖。它的每个结点包含多个数据,这特别适合于对外存的访问。由于硬盘等设备访问速度和内存相比非常慢,而从硬盘读取1个数据和读取10个数据用时几乎一样,这非常适合使用B-树这种结构。每个结点数据很多,就可以从磁盘依次取出大量数据,矮的特点可以减少磁盘的IO次数。

定义

B-树的所有叶子结点都位于同一深度,同时对每个结点的分支数也有限制。一个m阶B-树满足

1. 每个结点的分支数最多m个,因此每个结点元素个数最多m-1个。

2. 除根节点外,每个结点的分支树最少 ⌈m/2⌉ 个(向上取整)。根节点例外,根节点可以只有2个分支。

这样,m阶B-树也可以叫做 (⌈m/2⌉ , m) -树 。

查找

B树的查找和二分查找类似,只不多这里是多分的。详见代码。

插入

插入元素总是插入到叶节点,如果插入后节点数多余m-1,则要修复上溢。

发生上溢时,有m个结点,则分裂为左右两部分和中间轴点,左半部分有 m/2  个结点,中间1个结点,有半部分有⌈m/2⌉-1 个结点。 中间节点上升一层。父节点可能因此继续上溢。

scrn20160117114224

删除

通过和中序后继交换,实现删除元素总是位于叶子。删除后如果分支数小于要求,则称下溢。

发生下溢时,可以先看左右兄弟是否可借出一个孩子

scrn20160117115122

如果左右兄弟都不能借出,也就是都具有最少的结点,则可以进行合并。

scrn20160117122722

C++实现

BTree.h

BTree.cpp

 

如果文章对你有帮助,欢迎点赞或打赏(金额不限)。你的打赏将全部用于支付网站服务器费用和提高网站文章质量,谢谢支持。

版权声明:

本文由 原创,商业转载请联系作者获得授权。
非商业转载请注明作者 雅乐网 ,并附带本文链接:
http://www.yalewoo.com/data_structure_cpp_6_b-tree.html

上一篇:

下一篇:

我要评论

验证码*: 4 + 2 =