B树的插入、删除操作

电玩女神 2022-09-10 14:28 166阅读 0赞

一、简介

1.  B树是什么？

> 1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树（或B-树、B\_树）。  
> 一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：  
> 1、`根结点`至少有两个子女；  
> 2、每个`非根节点`所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；  
> 3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：┌m/2┐ <= k <= m ；  
> 4、每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。  
> 5、所有的`叶子结点都位于同一层`。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAYWR2ZW50dXJlLkxp_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

**关键点理解：**

1.能够清晰各节点的名称，分清 叶子节点、外部节点、根节点。（如上图）  
2.m阶代表 最多的子女树的数量，例如三阶 最多只能三个子女树，而 思考一下 m个子女树 ，是不是只需要 m-1个关键字则可满足。（原因关键字的左右边界可以导致多一个插入位）因此 m阶最多只能m-1一个关键字。  
3.除根节点外节点的关键码 >= ceil(m/2)-1 ，此处需要结合后面的插入以及应用。  
4.思考为什么要保持叶子节点同一层（保持查找效率，结合二叉搜索树思考（二叉搜索树就是2阶多路搜索树））？

1.  B树的应用

> B树大量应用在**数据库和文件系统**（此类软件 文件数量巨大，使用普通的查找效率极低，因此使用B树，一般B树  
> 的关键码会在100以上）当中。它的设计思想是，将相关数据尽量集中在一起，以便一次读取多个数据，减少硬盘操作次数。B树算法减少定位记录时所经历的中间过程，从而加快存取速度。

假定一个节点可以容纳100个值，那么3层的B树可以容纳100万个数据，如果换成二叉查找树，则需要20层！假定操作系统一次读取一个节点，并且根节点保留在内存中，那么B树在100万个数据中查找目标值，只需要读取两次硬盘。如mongoDB数据库使用，单次查询平均快于Mysql（但侧面来看Mysql至少平均查询耗时差不多）

二、基本操作

1.  插入操作

> 插入的思路比较简单，但一定也需要动手去画画，这样才会更加理解B树的原理和目标。

（1） 如果该结点的关键字个数没有到达m-1个，那么直接插入即可；

（2）如果该结点的关键字个数已经到达了m-1个，那么根据B树的性质显然无法满足，需要将其进行分裂。`分裂的规则`是该结点分成两半（这也是为什么 除根节点外 其他节点关键码 >= ceil(m/2）- 1 的原因所在），将中间的关键字进行提升，加入到父亲结点中，但是这又可能存在父亲结点也满员的情况，则不得不向上进行回溯，甚至是要对根结点进行分裂，那么整棵树都加了一层。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAYWR2ZW50dXJlLkxp_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]  
注意点：插入关键字最终落脚点在叶子结点。

1.  删除操作

> 删除操作，较为复杂一点，需要反复思考、分清不同情况（即 本身关键码够？不够那么兄弟节点够？ 兄弟节点都不够那么说明和兄弟合并可以满足小于等于m-1则需要合并 也可能会导致树的缩短）。

具体步骤如下：

（1）判断删除位置（很多博客没有考虑，可能觉得只讲关键步骤更为重要，但是我还是详细列出，更好进行理解）  
a. 若删除关键字key在根节点，且无子女树，那么直接删除。

b. 若删除关键字key在非叶子节点，那么拿 该关键字的后继（前继也可以，优先后继，后面的向兄弟节点借也优先右兄弟）`覆盖`删除关键字key且删除后继。然后落脚点变为删除了叶子节点的某个关键字（即该关键字key的后继或前继）。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAYWR2ZW50dXJlLkxp_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 2]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAYWR2ZW50dXJlLkxp_size_13_color_FFFFFF_t_70_g_se_x_16_pic_center]  
由b步骤，我们可以知道 所有的删除都可以归结在删除叶子节点了。那么再接着讨论以下情况：

（2）讨论删除该关键字的后果。

a. 删除之后相安无事，无需任何处理：在 后继关键字（或前继，看个人选择，后面统一选择后继）所在叶子节点删除该关键字之后，依然满足 关键字数量 >= ceil(m/2)-1 ,则无需调整。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAYWR2ZW50dXJlLkxp_size_13_color_FFFFFF_t_70_g_se_x_16_pic_center 1]

b.删除之后不能自保了，考虑向 `兄弟节点`（优先右兄弟，右兄弟无则左兄弟）借。如果兄弟也不够借，那么就 合并。  
借的规则：兄弟关键字上移给父亲节点，父亲关键字下移给该节点。  
合并规则：父亲节点关键字下移与兄弟节点合并。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAYWR2ZW50dXJlLkxp_size_13_color_FFFFFF_t_70_g_se_x_16_pic_center 2]  
合并的情况（以上图为例删除40）：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAYWR2ZW50dXJlLkxp_size_13_color_FFFFFF_t_70_g_se_x_16_pic_center 3]  
合并之后，发现 父亲节点为空了，则需要重复以上步骤，合并50，再50,60,80合并则如下图。（合并之后会出现考虑分裂的情况，结合插入情况的分裂规则 进行分裂）

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAYWR2ZW50dXJlLkxp_size_12_color_FFFFFF_t_70_g_se_x_16_pic_center]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAYWR2ZW50dXJlLkxp_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220829/5186a45ff4984db6bd1754a8ce31be92.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAYWR2ZW50dXJlLkxp_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]: /images/20220829/943f00af6dbd4829827186ec9aec9f49.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAYWR2ZW50dXJlLkxp_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 2]: /images/20220829/092f91413b4a474dabcbf36e3ee871cc.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAYWR2ZW50dXJlLkxp_size_13_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220829/54936e9a86014c499f26c01a8b947c91.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAYWR2ZW50dXJlLkxp_size_13_color_FFFFFF_t_70_g_se_x_16_pic_center 1]: /images/20220829/f40aa3912a1f460abd7b3ff22b4edcf0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAYWR2ZW50dXJlLkxp_size_13_color_FFFFFF_t_70_g_se_x_16_pic_center 2]: /images/20220829/7b0b9325d2d849679bc4cc82b2214d02.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAYWR2ZW50dXJlLkxp_size_13_color_FFFFFF_t_70_g_se_x_16_pic_center 3]: /images/20220829/e380d574b5424847bcdf84c49a17dbea.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAYWR2ZW50dXJlLkxp_size_12_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220829/e29b91528bd34d7d948406c1c5a77491.png