【数据结构】B树

男娘i 2023-01-05 12:52 148阅读 0赞

### 目录 ###

*  B树（B-tree、B-树）
 *  m阶B树的性质
 *  B树 vs 二叉搜索树
 *  搜索
 *  添加 – 上溢
 *   *  添加 – 上溢的解决(假设5阶)
     *  添加演示\[上溢\]
 *  删除
 *   *  删除 – 叶子节点
     *  删除 – 非叶子节点
     *  删除 – 下溢
     *  删除 – 下溢的解决
     *  删除演示\[下溢\]
 *  4阶B树

# B树（B-tree、B-树） #

B树是一种平衡的多路搜索树，多用于文件系统、数据库的实现；

仔细观察B树，有什么眼前一亮的特点？

*  `1 个节点`可以存储超过 2 个元素、可以拥有超过 2 个子节点
 *  拥有二叉搜索树的一些性质
 *  平衡，每个节点的所有子树高度一致
 *  比较矮

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 2]

# m阶B树的性质 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 3]  
数据库实现中一般用几阶B树？

*  200 ~ 300

# B树 vs 二叉搜索树 #

B树 和 二叉搜索树，在逻辑上是等价的；

多代节点合并，可以获得一个超级节点

*  2 代（当前节点 和 左右子节点）合并的超级节点，最多拥有 4 个子节点（至少是 4 阶B树）
 *  3 代（当前节点 和 左右子节点 的 孙子节点）合并的超级节点，最多拥有 8 个子节点（至少是 8 阶B树）
 *  n 代合并的超级节点，最多拥有  2 n 2^n 2n 个子节点（ 至少是  2 n 2^n 2n 阶B树）

m 阶 B树，最多需要  l o g 2 m log\_2m log2m 代合并；  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 4]

# 搜索 #

跟二叉搜索树的搜索类似：  
![在这里插入图片描述][20210113102423655.png]

1.  先在节点内部从小到大（从左到右）开始搜索元素
2.  如果命中，搜索结束
3.  如果未命中，再去对应的子节点中搜索元素，然后重复步骤 1

# 添加 – 上溢 #

4阶B树

新添加的元素必定是添加到叶子节点：  
![在这里插入图片描述][20210113104415671.png]  
插入 55：  
![在这里插入图片描述][20210113104929433.png]  
插入 95：  
![在这里插入图片描述][20210113104950169.png]  
再插入 98 呢？（假设这是一棵 4阶B树）

*  最右下角的叶子节点的元素个数将超过限制
 *  这种现象可以称之为：上溢（overflow）

## 添加 – 上溢的解决(假设5阶) ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 5]  
上溢节点的元素个数必然等于 m；

假设上溢节点最中间元素的位置为 k

1.  将 k 位置的元素向上与父节点合并
2.  将  \[ 0 , k − 1 \] \[0, k - 1\] \[0,k−1\] 和  \[ k + 1 , m − 1 \] \[k + 1, m - 1\] \[k\+1,m−1\] 位置的元素分裂成 2 个子节点
3.  这2 个子节点的元素个数，必然都不会低于最低限制（ ┌ m / 2 ┐ − 1 ┌ m/2 ┐ − 1 ┌m/2┐−1）\[m 除以 2 向上取整 减 1\]

一次分裂完毕后，有可能导致父节点上溢，依然按照上述方法解决

*  最极端的情况，有可能一直分裂到根节点  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 6]

## 添加演示\[上溢\] ##

假设这是一颗 4阶B树 ，依次添加 98、52、54  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 7]

# 删除 #

## 删除 – 叶子节点 ##

假如需要删除的元素在叶子节点中，那么直接删除即可；

例：删除 30  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 8]

## 删除 – 非叶子节点 ##

假如需要删除的元素在非叶子节点中

1.  先找到前驱或后继元素，覆盖所需删除元素的值
2.  再把前驱或后继元素删除

非叶子节点的前驱或后继元素，必定在叶子节点中；

*  所以这里删除的前驱或后继元素 ，就是最开始提到的情况：删除的元素在叶子节点中
 *  真正的删除元素都是发生在叶子节点中；

例：删除 60  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 9]

## 删除 – 下溢 ##

![在这里插入图片描述][20210113113840665.png]  
删除 22 ？（假设这是一棵 5阶B树）

*  叶子节点被删掉一个元素后，元素个数可能会低于最低限制（  ≥ ┌ m / 2 ┐ − 1 ≥ ┌ m/2 ┐ − 1 ≥┌m/2┐−1 ）
 *  这种现象称为：下溢（underflow）

## 删除 – 下溢的解决 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 11]

下溢节点的元素数量必然等于  ┌ m / 2 ┐ − 2 ┌ m/2 ┐ − 2 ┌m/2┐−2

如果下溢节点临近的兄弟节点，有至少  ┌ m / 2 ┐ ┌ m/2 ┐ ┌m/2┐ 个元素，可以向其借一个元素

*  将父节点的元素 b 插入到下溢节点的 0 位置（最小位置）
 *  用兄弟节点的元素 a（最大的元素）替代父节点的元素 b
 *  这种操作其实就是：旋转  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 12]

如果下溢节点临近的兄弟节点，只有  ┌ m / 2 ┐ − 1 ┌ m/2 ┐ − 1 ┌m/2┐−1 个元素

*  将父节点的元素 b 挪下来跟左右子节点进行合并
 *  合并后的节点元素个数等于  ┌ m / 2 ┐ + ┌ m / 2 ┐ − 2 ┌ m/2 ┐ + ┌ m/2 ┐ − 2 ┌m/2┐\+┌m/2┐−2，不超过 m − 1
 *  这个操作可能会导致父节点下溢，依然按照上述方法解决，下溢现象可能会一直往上传播  
    ![在这里插入图片描述][20210113115459872.png]

## 删除演示\[下溢\] ##

假设这是一棵 5阶B树 ，删除22，会导致20，30下溢  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 13]

# 4阶B树 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 14]  
4阶B树的性质：

*  所有节点能存储的元素个数 x ：1 ≤ x ≤ 3
 *  所有非叶子节点的子节点个数 y ：2 ≤ y ≤ 4

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]: /images/20221119/22383c3751bc48a7a9638d4c124d95cd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 1]: /images/20221119/3d18bdd45feb44e2a4b737f7769ff585.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 2]: /images/20221119/f43e1662f2d94fc6bdea36fa22d8944c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 3]: /images/20221119/51aa8ee76c18449db103dec508fe0eee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 4]: /images/20221119/d5abe4677f804311a761ad2688abfbf4.png
[20210113102423655.png]: /images/20221119/fc4dd421fc764c1b94e004181c87fcba.png
[20210113104415671.png]: /images/20221119/baec028146ce4d6e828fef58a71d05ab.png
[20210113104929433.png]: /images/20221119/c49fdbed719246479ccad1a525c9f6b2.png
[20210113104950169.png]: /images/20221119/c3d910cd677f4b9a822817718d36bbe7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 5]: /images/20221119/ea3d5e0f75a940f88e9d2bd366aad292.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 6]: /images/20221119/934f56b7bb97412c83d60423a2239d3d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 7]: /images/20221119/573dc1bad9ac418abd48df6dac392db5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 8]: /images/20221119/d3a5664023ed41d0ad8ba7249d7142c0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 9]: /images/20221119/482d4264ed7a4ddd81db08cac90640ff.png
[20210113113840665.png]: /images/20221119/32b6a42de27644ebb358a16a5faad407.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 10]: /images/20221119/6e655c3f0fc44e95a141fc26e88ed2f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 11]: /images/20221119/ac933237a439474997512528be4d6226.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 12]: /images/20221119/6191b73bab4147caa37a9168e3e5da4d.png
[20210113115459872.png]: /images/20221119/c2ce357eeb4f4f7485e7c0e9ced5a986.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 13]: /images/20221119/2135a4d88f484e1ebc3eaa681653df4e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 14]: /images/20221119/4fad6812f45d41338c96c7a3bb5c2ec7.png