前面介绍的BST(二叉排序树)和AVL(平衡二叉树)都是二叉树,用作内部查找的数据结构,即被查找的数据集不大,可以放在内存中。这篇博客将主要介绍B树,是非二叉树,用作外部查找的数据结构,其数据存放在外存中。 B-树又称为多路平衡查找树,是一种组织和维护外存文件系统非常有效的数据结构。具体讲解之前,有一点,强调一下:B-树,即为B树。因为B树的原英文名称为B-tree,而国内很多人喜欢把B-tree译作B-树,其实,这是个非常不好的直译,很容易让人产生误解。如人们可能会以为B-树是一种树,而B树又是一种一种树。而事实上是,B-tree就是指的B树。特此说明。
B-树
B-树中所有结点的孩子结点最大值称为B-树的阶,通常用m表示,从查找效率来说,要求m>=3.
一棵m阶B-树应满足的特性为:
1.树中每个结点最多含有m个孩子结点,即至多有m-1个关键字;
2.除根结点外,其它每个结点至少有[m / 2]个孩子结点,即至少有[m/2]-1个关键字。[m/2]是取大于m/2的最小整数;
3.若根结点不是叶子结点,则至少有两个孩子结点;
4.每个结点的结构为:
其中n为结点关键字个数,除根节点外,其它结点的n>=[m/2]-1&&n<=m-1;关键字是升序排列,即k1<k2<k3....。Pi指针所指的结点关键字大于等于Ki,小于Ki+1;
5.所有叶子结点都在同一层上,即B-树是所有平衡因子均为0的多路查找树。
上面的特性看起来晕晕的,下面用一个实例来分析。
引用典型的3阶B-树如下
看根结点A,其结点结构应为
阶是孩子结点的最大值,所以每个结点至多有3个孩子(分支),从结点结构来看,指针域比关键字多1,所以至多有3-1=2个关键字。
当阶树m=2时,就是二叉B树,即平衡二叉树
B-树的查找
来模拟下查找文件29的过程:
(1) 根据根结点指针找到文件目录的根磁盘块1,将其中的信息导入内存。【磁盘IO操作1次】
(2) 此时内存中有两个文件名17,35和三个存储其他磁盘页面地址的数据。根据算法我们发现17<29<35,因此我们找到指针p2。
(3) 根据p2指针,我们定位到磁盘块3,并将其中的信息导入内存。【磁盘IO操作2次】
(4) 此时内存中有两个文件名26,30和三个存储其他磁盘页面地址的数据。根据算法我们发现26<29<30,因此我们找到指针p2。
(5) 根据p2指针,我们定位到磁盘块8,并将其中的信息导入内存。【磁盘IO操作3次】
(6) 此时内存中有两个文件名28,29。根据算法我们查找到文件29,并定位了该文件内存的磁盘地址。
B-树的插入
重点判断是否满足n<=m-1。
插入方法步骤:
a.利用前述的B-树的查找算法查找关键字的插入位置。若找到,则说明该关键字已经存在,直接返回。否则查找操作必失败于某个最低层的非终端结点上。
b.判断该结点是否还有空位置。即判断该结点的关键字总数是否满足n<=m-1。若满足,则说明该结点还有空位置,直接把关键字k插入到该结点的合适位置上。若不满足,说明该结点己没有空位置,需要把结点分裂成两个。
分裂的方法是:生成一新结点。把原结点上的关键字和k按升序排序后,从中间位置把关键字(不包括中间位置的关键字)分成两部分。左部分所含关键字放在旧结点中,右部分所含关键字放在新结点中,中间位置的关键字连同新结点的存储位置插入到父结点中。如果父结点的关键字个数也超过(m-1),则要再分裂,再往上插。直至这个过程传到根结点为止。
例如:
B-树的删除
B-树特性,除根结点外,其它所有结点的关键字n>=[m/2]-1&&n<=m-1;
分三种情况删除:
a.如果被删关键字所在结点的原关键字个数n>=[m/2],说明删去该关键字后该结点仍满足B-树的定义。这种情况最为简单,只需从该结点中直接删去关键字即可。
b.如果被删关键字所在结点的关键字个数n等于[m/2]-1,说明删去该关键字后该结点将不满足B-树的定义,需要调整。
调整过程为:如果其左右兄弟结点中有“多余”的关键字,即与该结点相邻的右(左)兄弟结点中的关键字数目大于[m/2]-1。则可将右(左)兄弟结点中最小(大)关键字上移至双亲结点。而将双亲结点中小(大)于该上移关键字的关键字下移至被删关键字所在结点中。
c.如果左右兄弟结点中没有“多余”的关键字,即与该结点相邻的右(左)兄弟结点中的关键字数目均等于[m/2]-1。这种情况比较复杂。需把要删除关键字的结点与其左(或右)兄弟结点以及双亲结点中分割二者的关键字合并成一个结点,即在删除关键字后,该结点中剩余的关键字加指针,加上双亲结点中的关键字Ki一起,合并到Ai(即双亲结点指向该删除关键字结点的左(右)兄弟结点的指针)所指的兄弟结点中去。如果因此使双亲结点中关键字个数小于ceil(m/2)-1,则对此双亲结点做同样处理。以致于可能直到对根结点做这样的处理而使整个树减少一层。
相关推荐
定义B-树插入关键字函数、删除关键字函数、查找关键字函数以及按层次遍历输出B-树所有结点的函数。主函数定义菜单(1.插入关键字 2.删除关键字 3. 查找关键字 4.层次遍历输出B-树所有结点 5.结束程序)。
数据库-实验4-数据库操作的实现算法-B树-索引查找.pdf
想研究算法的可以参考一下, 本文所讨论的m路查找树多为可以动态调整的多路查找树
B-Trees 是一类满足特殊条件的M 路查找树。首先说明M 路查找树,M 路查找树是二元查找树的一般化,其结构如下图所示的3 路查找树:M 路查找树中的任一结点至多存放M-1个数据,并至多拥有M棵子树;每个结点中的数据按...
09-003二分查找的平均查找长度、查找树表 09-004动态查找表:二叉排序树的插入和删除操作 09-005查找的性能分析、平衡二叉树、B-树的定义 09-006B-树的查找过程、B+树的定义与查找 09-007键树的结构特点、哈希表的...
该设计要实现B-数的算法,要求输入一个序列,建立B-树,能够查找指定节点,并且能够遍历整个B-树,输出遍历序列结果。
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法框架出自一本书,书名记不得了。对其进行了实现和调试,用100+规模的数据测试通过。内附文档。
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法面试通关40讲完整课件 35-36 二分查找 算法面试通关40讲完整课件 35-36 二分查找 算法面试通关40讲完整课件 35-36 二分查找 算法面试通关40讲完整课件 35-36 二分查找 算法面试通关40讲完整课件 35-36 二分查找 ...
编写算法能将学生信息保存到文件中,能够为学生信息建立B-树索引,并能够利用B-树索引查找到指定学生的信息。建立B-树索引使用学号为关键字。( B-树中只含有学号和该记录在文件中的位置信息)
主要介绍了查找算法,包括顺序查找、折半查找、分块查找和树形查找。后面会继续更新树形查找的相关内容,包括红黑树、B树、B+树、散列表等。除了讲一下他的算法思想,也会对他做一定的性能分析
主要内容包括:面向对象编程的基本原理,判定算法效率的方法,堆栈、队列及其应用,对于多种递归的详细讨论,二叉树、B树、2-4树等的查找和遍历等,分析排序、散列等数据结构的应用,图、NP完整性,数据压缩算法、...
当数据庞杂时,B 树索引在查找效率和空间利用率方面还存在不足。针对该问题提出一种改进的B 树结构,首先通过调整叶子节点与非叶子节点的数量关系,以降低树的深度;然后优化原插入算法,在分裂节点前进行平衡处理...
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...
严蔚敏版数据结构所有算法的演示软件 非常好 是学习数据结构,帮忙理解数据结构的一个很好软件 其中包括平衡二叉树、B树的插入,删除,查找等等