重庆市建设工程节能中心网站,重庆市今天最新消息,网站的效果图,成品网站建设咨询B-Tree (多路查找树)学习-20230503
前言
B-树是一类多路查询树#xff0c;它主要用于文件系统和某些数据库的索引#xff0c;如果采用二叉平衡树访问文件里面的数据#xff0c;最坏情况下#xff0c;磁头可能需要进行O(h)次对磁盘的读写#xff0c;其中h为树的高度…B-Tree (多路查找树)学习-20230503
前言
B-树是一类多路查询树它主要用于文件系统和某些数据库的索引如果采用二叉平衡树访问文件里面的数据最坏情况下磁头可能需要进行O(h)次对磁盘的读写其中h为树的高度此时如果采用B-树由于它的多路访问特性可显著降低树的高度所以对磁盘读写次数将大幅减少。
为了更清楚表述我们引入经典的二次储存系统为了增加储存容量通常由多个磁盘构成如果可以多路对磁盘进行访问那么通过一次读取很快可以定位数据的储存区域。 B-Tree 的定义
根据《数据结构》严蔚敏定义一颗m阶的B-tree或为空树或满足下列特性的m叉树,
树中每个结点至多有m棵树它定义节点中包含数据的上限值此值和每个track的容量相关由于B-tree的节点即储存键值又储存子树指针一般情况下键值会占据大量的数据空间尤其是键值为结构体数据类型的时候空间占据会急剧增加为了应对这类挑战人们发明了Btree的数据结构若根节点不是叶子节点则至少有两棵树。此约束保证了B-tree不会退化为线性表最坏情况下允许退化为二叉树这是最后的底线除根节点之外的非终端节点至少有[m/2]棵子树其中[m/2]取上限值为了后续的程序操作方便定义非终端结点包含下列数据信息的数据 ( n , A 0 , K 1 , A 1 , K 2 , A 2 , . . . , K n , A n ) ; (n,A_0,K_1,A_1,K_2,A_2,...,K_n,A_n); (n,A0,K1,A1,K2,A2,...,Kn,An);
其中Ki为关键字且K[i]K[i1],并且A[i-1]所指向的节点里面的关键字均小于K[i]关键字A[i1]所指向节点里面的关键字均大于K[i]n为关键字的数量([m/2]-1nm)
所有的叶子节点都在同一层次上并且不带信息
B-Tree 基本操作
3.1 查询操作
B-Tree树的查询操作与二叉查询树的查询操作类似。它实际上上分为两部分第一部分需要找到值所在的节点的指针然后在节点中可以采用顺序表搜索或者折半查找的方式定位待查询的值或者值所在的子树指针它是查找节点和在节点中搜索关键字的交叉进行的过程。 具体看一个例子假定要查找key99的值从根节点出发由于9935,那么顺着A1指针指向的结点进行搜索在A1指向的结点中由于9978继续在A2所指的结点中搜索在A2结点当中恰好K199搜索完毕。
3.2 插入操作
B-Tree的生成是不断通过插入操作实现的增加B-Tree高度唯一的途径是根节点的分裂每次根节点分类事件发生B-Tree的深度就增加1。除此之外其它的插入也可能差生节点的分裂但只要根节点不产生分裂那么B-tree的深度就保持不变。
由于节点内关键字数目的限制插入操作可能会导致节点分裂这也导致了插入过程的复杂化。具体而言插入某个值可以采用两个策略当中的任意一个策略1 首先在最底层的某个非终端节点条件一个关键字若该节点的数目不超过m-1则插入完成否则要产生节点的分裂策略1实际上采用的是自下而上的方法先从根节点出发找到需要插入节点在最底层非终端节点上位置然后执行插入如果必要则自下而上进行不断分裂。
具体看一个例子。对于m3阶B-Tree,[m/2]2。 假定需要依次插入关键字30,2685和7首先查找确定关键字应该插入的最底层结点的位置。通过查找得知30应该插入在结点d所在位置插入完成后由于插入后的关键字数量小于m无需任何分裂插入作业完成。 同样查找关键字26亦应插入在d结点当中由于d结点中关键在数目超过2此时需要将d分裂成为两个结点关键字26及其前后指针仍然保留在d结点中而关键字37及其前后指针需要储存到新产生的结点d’当中。同时将中间关键字30和d’指针一起插入到双亲结点中。由于更新后的b结点关键字未超过2则插入完成。 结点d分裂为d和d’两个不同的结点。 类似地在g中插入85后需要分裂为两个结点而当70插入到e结点当中去由于e中的结点数目超过2需要继续分裂直到70插入到a结点中插入结束。
85关键字插入后g节点关键字数目不满足b-tree节点数目的基本要求需要进行分裂中间关键字70需要往移动到上一层节点e中去。由于70关键字的插入导致 e结点关键字数量超过2对于e结点需要继续分裂中间关键字70继续往上移动至 结点a当中。 e结点分裂后的B-tree. 采用相同的思路插入关键字7通过查找关键字7应当插入至底层结点c当中插入c后由于c结点中的关键字数量大于2需要分裂关键字7移动至结点b当中类似地b结点中的关键字数量大于2中间关键字24继续向上插入至根节点由于根节点关键字数量大于2根节点需要分裂B-tree深度增加1至此插入结束。
3.3 删除操作
B-Tree的删除操作比较复杂其主要约束来自于B-tree特性的保持一般情况下则首先找到待删除关键字所在的结点如果关键字所在结点为最下层的非终端节点如果关键字数目不小于[m/2]直接删除即可否则就需要自下而上进行结点的合并。倘若删除关键字为非终端结点Ki,则可以用指针Ai所指的树的最小关键字Y代替Ki,然后在相应的结点中删除Y即可。所以只需讨论删除最下层非终端结点的关键字即可。
有下列三种情况
1 被删除关键字结点中的关键字数量不小于[m/2]则直接删除Ki和Ai即可树的其它部分保持不变化。从树中删除关键字12就属于此类型。 删除12后树的其它部分保持不变。 (2)被删除关键字所在的结点关键字数目为[m/2]-1而与该节点相邻的右左兄弟结点的关键字数目大于[m/2]-1,则需将相邻右兄弟结点中最小最大的关键字上移至双亲结点中而将双亲结点中小于大于且紧靠该上移关键字的关键字下移至被删除的结点当中。删除B-tree的关键字50便是如此情形。 3被删除关键字所在结点的左右子树关键字的数目都等于[m/2]-1, 假设该节点有右兄弟且右兄弟结点由双亲结点中的Ai指针所指那么在删除关键字之后它所在的结点剩余的关键字和指针另外加上双亲结点的Ki关键字合并到Ai所指的有兄弟结点中去。合并至左节点的逻辑亦相同。
删除关键字53便是上述情形。 小结
由于B-tree的定义限制导致 B-tree在插入和操作的时候需要分裂或合并结点造成整体程序实现的复杂性。其实现方式通常采用自下而上根据约束条件不断进行分裂或合并直至根节点。另外B-tree深度增加的唯一途径就是根节点的分裂B-tree深度减低的唯一途径就是根节点的合并。
参考文献
并结点造成整体程序实现的复杂性。其实现方式通常采用自下而上根据约束条件不断进行分裂或合并直至根节点。另外B-tree深度增加的唯一途径就是根节点的分裂B-tree深度减低的唯一途径就是根节点的合并。
对于代码实现如果有时间我们将另外篇幅描述。
参考文献
《数据结构》 严蔚敏
