十七、B树（B-tree、B-树）

作者: 咸鱼Jay | 来源:发表于2022-01-29 18:27 被阅读0次

B树、B+树、B*树
B-Tree/多路搜索树
十七、B树（B-tree、B-树）
算法漫画阅读摘要
b树、b+树原理
数据结构之BBST
【恋上数据结构与算法一】(十)B树
Mysql学习笔记：存储引擎MyISAM和InnoDB的区别
12-B树
漫画算法：什么是 B 树？

1、B树（B-tree、B-树）介绍

了解B树是最终理解红黑树的关键

B树

$\color{#00afef}{B树}$ 是一种平衡的 $\color{#ed7d30}{多路}$ 搜索树，多用于文件系统、数据库的实现

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

1 个节点可以存储超过 2 个元素、可以拥有超过 2 个子节点

拥有二叉搜索树的一些性质

平衡，每个节点的所有子树高度一致

比较矮

2、m阶B树的性质（m≥2）

假设一个节点存储的元素个数为 $\color{green}{x}$
- 根节点： $\color{red}{1} ≤ \color{green}{x} ≤ \color{red}{m -1}$
- 非根节点： $\color{red}{_┌ m/2 _┐ − 1} ≤ \color{green}{x} ≤ \color{red}{m -1}$
注意：这个┌ ┐表示ceilling向上取整
- 如果有子节点，子节点个数
  - 根节点： $\color{red}{2} ≤ \color{green}{y} ≤ \color{red}{m}$
  - 非根节点：
    - 比如 $m = 3，\color{red}{2} ≤ \color{green}{y} ≤ \color{red}{3}$ ，因此可以称为（2, 3）树、2-3树
    - 比如 $m = 4，\color{red}{2} ≤ \color{green}{y} ≤ \color{red}{4}$ ，因此可以称为（2, 4）树、2-3-4树
    - 比如 $m = 5，\color{red}{3} ≤ \color{green}{y} ≤ \color{red}{5}$ ，因此可以称为（3, 5）树
    - 比如 $m = 6，\color{red}{3} ≤ \color{green}{y} ≤ \color{red}{6}$ ，因此可以称为（3, 6）树
    - 比如 $m = 7，\color{red}{4} ≤ \color{green}{y} ≤ \color{red}{7}$ ，因此可以称为（4, 7）树

思考：如果 m = 2，那B树是什么样子？
如果m =2，那么根节点的子节点个数是2，非根节点的子节点个数是1或者2，那么不就是二叉搜索树嘛。

猜猜数据库实现中一般用几阶B树？
一般是200 ~ 300阶

3、B树 VS 二叉搜索树

$\color{#00afef}{B树}$ 和二叉搜索树，在逻辑上是等价的
多代节点合并，可以获得一个超级节点
- 2代合并的超级节点(例如：18和12、33合并)，最多拥有 4 个子节点（至少是 4阶B树）
- 3代合并的超级节点(例如：18和12、33和10、5、13、48合并)，最多拥有 8 个子节点（至少是 8阶B树）
- n代合并的超级节点，最多拥有 $2^n$ 个子节点（至少是 $2^n$ 阶B树）
m阶B树，最多需要 $log_2m$ 代合并

多代节点合并：18和33合并成一个超级节点。
2代合并的超级节点：18和12、33合并，他们拥有最多子节点是12和33节点的左右子节点之和。

4、搜索

跟二叉搜索树的搜索类似

先在节点内部从小到大开始搜索元素
如果命中，搜索结束
如果未命中，再去对应的子节点中搜索元素，重复步骤 1

5、添加

新添加的元素必定是添加到叶子节点
插入55

插入55
插入95

插入95
再插入 98 呢？（假设这是一棵4阶B树）
最右下角的叶子节点的元素个数将超过限制
这种现象可以称之为： $\color{#ed7d30}{上溢（overflow）}$

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

上溢节点的元素个数必然等于 $\color{green}{m}$
假设上溢节点最中间元素的位置为 $\color{green}{k}$
- 将 $\color{green}{k}$ 位置的元素向上与父节点合并
- 将 [] 和 [] 位置的元素分裂成 2 个子节点
  - 这 2 个子节点的元素个数，必然都不会低于最低限制（ $\color{red}{_┌ m/2_ ┐ − 1}$ ）
一次分裂完毕后，有可能导致父节点上溢，依然按照上述方法解决
最极端的情况，有可能一直分裂到跟节点

下图中依次添加98、52、54

插入98
插入98
插入52
插入52
插入54
插入54

6、删除

6.1、删除 – 叶子节点

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

删除30

6.2、删除 – 非叶子节点

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

删除60

删除60后就剩下一个40元素了，那么一个元素怎么能拥有三个子节点呢？

先找到前驱或后继元素，覆盖所需删除元素的值

再把前驱或后继元素删除

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

6.3、删除 – 下溢

删除 22 ？（假设这是一棵 5阶B树）
- 叶子节点被删掉一个元素后，元素个数可能会低于最低限制（ $≥ \color{red}{_┌ m/2_ ┐ − 1}$ ）
- 这种现象称为： $\color{#ed7d30}{下溢（underflow）}$

6.4、删除 – 下溢的解决

下溢节点的元素数量必然等于 $\color{red}{_┌ m/2_ ┐ − 2}$

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

将父节点的元素 $\color{green}{b}$ 插入到下溢节点的 $\color{red}{0}$ 位置（最小位置）

用兄弟节点的元素 $\color{green}{a}$ （最大的元素）替代父节点的元素 $\color{green}{b}$

这种操作其实就是： $\color{orange}{旋转}$

如果下溢节点临近的兄弟节点，只有 $\color{red}{_┌ m/2_ ┐ − 1}$ 个元素

将父节点的元素 $\color{green}{b}$ 挪下来跟左右子节点进行 $\color{orange}{合并}$

合并后的节点元素个数等于 $\color{red}{_┌ m/2_ ┐ + _┌ m/2 _┐ − 2}$ ，不超过 $\color{red}{m − 1}$

这个操作可能会导致父节点下溢，依然按照上述方法解决，下溢现象可能会一直往上传播

上溢可能会让树变高，下溢可能会让树变矮。

7、4阶B树

如果先学习 $\color{#00afef}{4阶B树}$ （ $\color{#00afef}{2-3-4树}$ ），将能更好地学习理解 $\color{#00afef}{红黑树}$
$\color{#00afef}{4阶B树}$ 的性质
- 所有节点能存储的元素个数 $\color{green}{x}$ ： $\color{red}{1}$ ≤ $\color{green}{x}$ ≤ $\color{red}{3}$
- 所有非叶子节点的子节点个数 $\color{green}{y}$ ： $\color{red}{2}$ ≤ $\color{green}{y}$ ≤ $\color{red}{4}$
添加
从 1 添加到 22，就会是一个 $\color{#00afef}{4阶B树}$

4阶B树

B树、B+树、B*树
B-树，就是B树，B树的原英文名是B-tree,所以很多翻译为B-树,就会很多人误以为B-树是一种树、B树是另外一...
B-Tree/多路搜索树
B-Tree/多路搜索树 B-Tree 又叫 B树/B-树，- 是连接符号，不是减号，不能读做 B减树，常用做文件...
十七、B树（B-tree、B-树）
1、B树（B-tree、B-树）介绍了解B树是最终理解红黑树的关键是一种平衡的搜索树，多用于文件系统、数据库的...
算法漫画阅读摘要
记录一下个人对于公众号算法爱好者和程序员小灰的阅读摘要，目录如下， B-树（B-tree） B-树就是B树，中间的...
b树、b+树原理
首先，b树和b-树是一种东西，不存在什么“b减树”。“B-tree，B即Balanced，平衡的意思。因为B树的原...
数据结构之BBST
目录： 1.B-树与B+树2.红黑树文章参考：关于B-tree的科普文，很有趣什么是B-树？关于B+树的科普...
【恋上数据结构与算法一】(十)B树
B树(B-tree、B-树) ◼ B树是一种平衡的多路搜索树，多用于文件系统、数据库的实现 ◼ 仔细观察B树，有什...
Mysql学习笔记：存储引擎MyISAM和InnoDB的区别
在整理文章《Mysql索引的理解：B-Tree(B-树)和B+Tree(B+树)》时，突然对“MyISAM和Inn...
12-B树
B树(B-tree，B-树) B树是一种平衡的多路搜索树，多用于文件系统，数据库的实现仔细观察B树，有什么眼前一...
漫画算法：什么是 B 树？
本文提到的「B-树」，就是「B树」，都是 B-tree 的翻译，里面不是减号-，是连接符-。因为有人把 B-tre...