Debug客栈
做一个爱分享的程序猿
Debug客栈
数据结构 B加树

B+树定义

一颗 m 阶的 B+树和 m 阶的 B-树的差异在于:

  • 有 n 棵子树的结点中含有 n 个关键字;

在上一节中,在 B-树中的每个结点关键字个数 n 的取值范围为⌈m/2⌉ -1≤n≤m-1,而在 B+树中每个结点中关键字个数 n 的取值范围为:⌈m/2⌉≤n≤m

  • 所有的叶子结点中包含了全部关键字的信息,及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
  • 所有的非终端结点(非叶子结点)可以看成是索引部分,结点中仅含有其子树(根结点)中的最大(或最小)关键字。

例如,下图中所示的就是一棵深度为 4 的 3 阶 B+树:

https://www.debuginn.cn/wp-content/uploads/2019/02/001-4.png

如上图所示,B+树中含有两个头指针,一个指向整棵树的根结点,另一个指向关键字最小的叶子结点。同时所有的叶子结点依据其关键字的大小自小而大顺序链接,所有的叶子结点构成了一个 sqt 指针为头指针的链表。

所有,B+树可以进行两种查找运算:一种是利用 sqt 链表做顺序查找,另一种是从树的根结点开始,进行类似于二分查找的查找方式。

在 B+树中,所有非终端结点都相当于是终端结点的索引,而所有的关键字都存放在终端结点中,所有在从根结点出发做查找操作时,如果非终端结点上的关键字恰好等于给定值,此时并不算查找完成,而是要继续向下直到叶子结点。

B+树的查找操作,无论查找成功与否,每次查找操作都是走了一条从根结点到叶子结点的路径。

B+树中插入关键字

在B+树中插入关键字时,需要注意以下几点:

  • 插入的操作全部都在叶子结点上进行,且不能破坏关键字自小而大的顺序;
  • 由于 B+树中各结点中存储的关键字的个数有明确的范围,做插入操作可能会出现结点中关键字个数超过阶数的情况,此时需要将该结点进行“分裂”;

B+树中做插入关键字的操作,有以下 3 种情况:

  1. 若被插入关键字所在的结点,其含有关键字数目小于阶数 M,则直接插入结束; 例如,在上图中插入关键字13,其结果如下图所示:
  2. 若被插入关键字所在的结点,其含有关键字数目等于阶数 M,则需要将该结点分裂为两个结点,一个结点包含⌊M/2⌋,另一个结点包含⌈M/2⌉。同时,将⌈M/2⌉的关键字上移至其双亲结点。假设其双亲结点中包含的关键字个数小于 M,则插入操作完成。 例如,在开始的图的基础上插入关键字 95,其插入后的 B+树如下图所示:
  3. 在第 2 情况中,如果上移操作导致其双亲结点中关键字个数大于 M,则应继续分裂其双亲结点。 例如,在开始的图的B+树中插入关键字 40,则插入后的 B+树如下图所示: 注意:如果插入的关键字比当前结点中的最大值还大,破坏了B+树中从根结点到当前结点的所有索引值,此时需要及时修正后,再做其他操作。例如,在图 1 的 B+树种插入关键字 100,由于其值比 97 还大,插入之后,从根结点到该结点经过的所有结点中的所有值都要由 97 改为 100。改完之后再做分裂操作。

B+树中删除关键字

在 B+树中删除关键字时,有以下几种情况:

  1. 找到存储有该关键字所在的结点时,由于该结点中关键字个数大于⌈M/2⌉,做删除操作不会破坏 B+树,则可以直接删除。 例如,在起始图所示的 B+树中删除关键字 91,删除后的 B+树如下图所示:
  2. 当删除某结点中最大或者最小的关键字,就会涉及到更改其双亲结点一直到根结点中所有索引值的更改。 例如,在起始图的 B+树中删除关键字 97,删除后的 B+树如下图所示:
  3. 当删除该关键字,导致当前结点中关键字个数小于⌈M/2⌉,若其兄弟结点中含有多余的关键字,可以从兄弟结点中借关键字完成删除操作。 例如,在起始图的 B+树中删除关键字 51,由于其兄弟结点中含有 3 个关键字,所以可以选择借一个关键字,同时修改双亲结点中的索引值,删除之后的 B+树如下图所示:
  4. 第 3 种情况中,如果其兄弟结点没有多余的关键字,则需要同其兄弟结点进行合并。 例如,在图 7 的 B+树种删除关键字 59,删除后的 B+树为:
  5. 当进行合并时,可能会产生因合并使其双亲结点破坏 B+树的结构,需要依照以上规律处理其双亲结点。 例如,在B+树中删除关键字 63,当删除后该结点中只剩关键字 72,且其兄弟结点中只有 2 个关键字,无法实现借的操作,只能进行合并。但是合并后,合并后的效果图如下图所示: 如上图所示,其双亲结点中只有一个关键字,而其兄弟结点中有 3 个关键字,所以可以通过借的操作,来满 足 B+树的性质,最终的 B+树如下图所示:

总之,在 B+树中做删除关键字的操作,采取如下的步骤:

  1. 删除该关键字,如果不破坏 B+树本身的性质,直接完成操作;
  2. 如果删除操作导致其该结点中最大(或最小)值改变,则应相应改动其父结点中的索引值;
  3. 在删除关键字后,如果导致其结点中关键字个数不足,有两种方法:一种是向兄弟结点去借,另外一种是同兄弟结点合并。(注意这两种方式有时需要更改其父结点中的索引值。)

感谢

本贝壳编写借鉴了一些经验,表示感谢。

B+树 严长生

赞赏
本文链接:https://www.debuginn.cn/108.html
本文采用 CC BY-NC-SA 3.0 Unported 协议进行许可,转载请保留文章链接
Debug客栈  |  Debug客栈引导页  |  Debug客栈交流群  |  赞助本站  |  博主微博  |  音乐下载器

发表评论

textsms
account_circle
email

Debug客栈

数据结构 B加树
B+树定义 一颗 m 阶的 B+树和 m 阶的 B-树的差异在于: 有 n 棵子树的结点中含有 n 个关键字; 在上一节中,在 B-树中的每个结点关键字个数 n 的取值范围为⌈m/2⌉ -1≤n≤m-1,…
扫描二维码继续阅读
2017-11-23
文章日历
2019年七月
« 6月    
1234567
891011121314
15161718192021
22232425262728
293031  
近期评论
统计数据
  • 1
  • 290
  • 9,318
  • 4,740
  • 1
  • 284
  • 190
  • 2019年7月13日
本站存活