前面介绍的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-tree)是一种自平衡的树数据结构,特别适用于大型数据库和文件系统,因为它能够保持数据有序,便于快速查找、插入和删除操作。在本项目中,我们将深入探讨B- B-树(通常指的是B-树或B+树)的实现,并以C语言...
通过这个实验,目的是让学生掌握B-树插入、删除和查找的基本算法,理解B-树的自平衡性质及其在大数据存储中的优势。 **算法设计简要描述** 1. 插入操作涉及查找插入位置,如果导致节点超过最大关键字数,则分裂节点...
实验的主要目的是让学生深入理解B-树的插入、删除和查找算法,以及层次遍历的实现方式,巩固数据结构的知识,并提高实际编程能力。 在实现过程中,应考虑算法的效率和正确性,确保B-树的性质在整个操作过程中得到...
数据库-实验4-数据库操作的实现算法-B树-索引查找.pdf
B-树是一种自平衡的树数据结构,它保持了数据的有序性,使得查找、插入和删除操作都非常高效。在数据库和文件系统中广泛应用。B-树的每个节点可以拥有多个子节点,这有助于减少树的高度,从而提高查找效率。 ### ...
想研究算法的可以参考一下, 本文所讨论的m路查找树多为可以动态调整的多路查找树
在计算机科学领域,树是一种非常重要的数据结构,它在算法设计和分析中起着核心作用。树的概念源自数学,但在编程中,我们通常需要通过特定的存储结构来表示和操作树。这个压缩包"算法-理论基础- 树- 树的存储结构...
- **B树和B+树**:适用于磁盘等外部存储,减少磁盘I/O操作,提高查找效率。 5. **应用**: - 数据库索引:二叉排序树常用于数据库索引,提高数据查询速度。 - 文件系统:在文件系统中,文件和目录的存储可以通过...
在B-树中查找关键字k的算法为: 1. 将k与根结点中的key[i](1≤i≤n)进行比较。 2. 若k=key[i],则查找成功。 3. 若k[1],则沿着指针ptr[0]所指的子树继续查找。 4. 若key[i][i+1],则沿着指针ptr[i]所指的子树继续查找...
- 线性表查找和树结构查找,广度优先搜索和深度优先搜索,A*启发式搜索,贪心算法,分治算法,回溯算法,枚举算法,动态规划算法。 - 常见的位运算公式和多个hash函数映射。 5. **查找和搜索**: - 二叉搜索树、...
B树(B-tree)是一种自平衡的树数据结构,它能够保持数据排序,常用于数据库和文件系统中。B树的主要特点是每个节点可以有多个子节点,这使得它在处理大量数据时能有效地进行查找、插入和删除操作,尤其适合于磁盘等...
实验的目的是让学生掌握B-树插入、删除和查找算法,加深对数据结构的理解。 B-树的核心特性包括: 1. 每个节点最多有m个子节点,m通常为一个较大的数值。 2. 根节点如果不是叶子节点,至少有两个子节点。 3. 除了根...
查找算法通常根据数据的存储方式和查找方法进行分类,常见的查找算法包括线性查找、二分查找、分块查找、基于树的查找(例如二叉查找树BST、平衡树AVL树、B树和B+树)以及散列技术等。 查找算法的学习目标包括理解...
《算法-理论基础- 查找(包含源程序)》这个压缩包文件主要涵盖了关于查找算法的基础理论,并且提供了源程序供学习者实践和理解。查找算法是计算机科学中非常重要的一部分,它涉及到如何在数据结构中有效地寻找特定...
2-3树是B树的一种特殊形式,它在查找、插入和删除等操作中保持了数据的有序性,同时通过内部节点的2个或3个子节点来提高平衡性能。以下将详细介绍2-3树的概念、特性、操作以及在实际中的应用。 1. **2-3树的概念** ...
在数据库索引中,B树和B+树用于快速查询;在编译器中,语法分析树用于解析源代码。 7. **树的运算**:包括查找、插入、删除等操作,以及树的复制、合并等高级操作。这些运算的效率直接影响到程序的性能。 8. **树...
3. **树的类型**:包括但不限于二叉搜索树、完全二叉树、满二叉树、平衡二叉树(如AVL树和红黑树)、B树和B+树等,每种类型的树有其特定的性质和应用场景。 4. **树的数据生成**:生成树的数据通常涉及随机生成算法...
查找算法包括顺序查找、二分查找和哈希查找,其中哈希表提供了近乎常数时间的查找效率。 5. **动态规划**:用于解决具有重叠子问题和最优子结构的问题,如背包问题、最长公共子序列等。 6. **贪心算法**:通过每...
在IT领域,算法是解决问题的核心工具之一,而树作为一种数据结构,是算法研究的重要组成部分。树数据结构在计算机科学中的应用广泛,包括操作系统、数据库、编译器、网络路由等众多方面。本压缩包“算法-理论基础- ...