`
hm4123660
  • 浏览: 282418 次
  • 性别: Icon_minigender_1
  • 来自: 广州
博客专栏
Dea4ce76-f328-3ab2-b24a-fb268e1eeb75
数据结构
浏览量:69994
社区版块
存档分类
最新评论

查找算法--树表查找之B树

阅读更多

        前面介绍的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,则对此双亲结点做同样处理。以致于可能直到对根结点做这样的处理而使整个树减少一层。



 

4
1
分享到:
评论

相关推荐

    B- B-树算法实现

    B-树(B-tree)是一种自平衡的树数据结构,特别适用于大型数据库和文件系统,因为它能够保持数据有序,便于快速查找、插入和删除操作。在本项目中,我们将深入探讨B- B-树(通常指的是B-树或B+树)的实现,并以C语言...

    数据结构实验报告-查找-B-树基本操作的实现2017.docx

    通过这个实验,目的是让学生掌握B-树插入、删除和查找的基本算法,理解B-树的自平衡性质及其在大数据存储中的优势。 **算法设计简要描述** 1. 插入操作涉及查找插入位置,如果导致节点超过最大关键字数,则分裂节点...

    数据结构实验报告-查找-B-树基本操作的实现 实验报告(含完整代码及测试)

    实验的主要目的是让学生深入理解B-树的插入、删除和查找算法,以及层次遍历的实现方式,巩固数据结构的知识,并提高实际编程能力。 在实现过程中,应考虑算法的效率和正确性,确保B-树的性质在整个操作过程中得到...

    数据库-实验4-数据库操作的实现算法-B树-索引查找.pdf

    数据库-实验4-数据库操作的实现算法-B树-索引查找.pdf

    数据结构实验报告10-查找-B-树基本操作的实现-实验内容与要求.docx

    B-树是一种自平衡的树数据结构,它保持了数据的有序性,使得查找、插入和删除操作都非常高效。在数据库和文件系统中广泛应用。B-树的每个节点可以拥有多个子节点,这有助于减少树的高度,从而提高查找效率。 ### ...

    数据结构-算法-B树

    想研究算法的可以参考一下, 本文所讨论的m路查找树多为可以动态调整的多路查找树

    算法-理论基础- 树- 树的存储结构(包含源程序).rar

    在计算机科学领域,树是一种非常重要的数据结构,它在算法设计和分析中起着核心作用。树的概念源自数学,但在编程中,我们通常需要通过特定的存储结构来表示和操作树。这个压缩包"算法-理论基础- 树- 树的存储结构...

    数据结构--查找--二叉排序树

    - **B树和B+树**:适用于磁盘等外部存储,减少磁盘I/O操作,提高查找效率。 5. **应用**: - 数据库索引:二叉排序树常用于数据库索引,提高数据查询速度。 - 文件系统:在文件系统中,文件和目录的存储可以通过...

    算法学习:B-树与B+树

    在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]所指的子树继续查找...

    数据结构和算法-思维导图.pdf

    - 线性表查找和树结构查找,广度优先搜索和深度优先搜索,A*启发式搜索,贪心算法,分治算法,回溯算法,枚举算法,动态规划算法。 - 常见的位运算公式和多个hash函数映射。 5. **查找和搜索**: - 二叉搜索树、...

    B树索引算法 VC实现

    B树(B-tree)是一种自平衡的树数据结构,它能够保持数据排序,常用于数据库和文件系统中。B树的主要特点是每个节点可以有多个子节点,这使得它在处理大量数据时能有效地进行查找、插入和删除操作,尤其适合于磁盘等...

    数据结构实验报告-查找-B-树基本操作的实现10分-实验内容与要求.docx

    实验的目的是让学生掌握B-树插入、删除和查找算法,加深对数据结构的理解。 B-树的核心特性包括: 1. 每个节点最多有m个子节点,m通常为一个较大的数值。 2. 根节点如果不是叶子节点,至少有两个子节点。 3. 除了根...

    查找算法ppt哈工大

    查找算法通常根据数据的存储方式和查找方法进行分类,常见的查找算法包括线性查找、二分查找、分块查找、基于树的查找(例如二叉查找树BST、平衡树AVL树、B树和B+树)以及散列技术等。 查找算法的学习目标包括理解...

    算法-理论基础- 查找(包含源程序).rar

    《算法-理论基础- 查找(包含源程序)》这个压缩包文件主要涵盖了关于查找算法的基础理论,并且提供了源程序供学习者实践和理解。查找算法是计算机科学中非常重要的一部分,它涉及到如何在数据结构中有效地寻找特定...

    算法-理论基础- 索引- 2-3 树(包含源程序).rar

    2-3树是B树的一种特殊形式,它在查找、插入和删除等操作中保持了数据的有序性,同时通过内部节点的2个或3个子节点来提高平衡性能。以下将详细介绍2-3树的概念、特性、操作以及在实际中的应用。 1. **2-3树的概念** ...

    算法-树形结构- 树与二叉树.rar

    在数据库索引中,B树和B+树用于快速查询;在编译器中,语法分析树用于解析源代码。 7. **树的运算**:包括查找、插入、删除等操作,以及树的复制、合并等高级操作。这些运算的效率直接影响到程序的性能。 8. **树...

    算法-树形结构- 树与二叉树- 树的数据生成器.rar

    3. **树的类型**:包括但不限于二叉搜索树、完全二叉树、满二叉树、平衡二叉树(如AVL树和红黑树)、B树和B+树等,每种类型的树有其特定的性质和应用场景。 4. **树的数据生成**:生成树的数据通常涉及随机生成算法...

    数据结构基础内容与B-树的详解

    查找算法包括顺序查找、二分查找和哈希查找,其中哈希表提供了近乎常数时间的查找效率。 5. **动态规划**:用于解决具有重叠子问题和最优子结构的问题,如背包问题、最长公共子序列等。 6. **贪心算法**:通过每...

    算法-理论基础- 树(包含源程序).rar

    在IT领域,算法是解决问题的核心工具之一,而树作为一种数据结构,是算法研究的重要组成部分。树数据结构在计算机科学中的应用广泛,包括操作系统、数据库、编译器、网络路由等众多方面。本压缩包“算法-理论基础- ...

Global site tag (gtag.js) - Google Analytics