一、B树性质
1、初识B树
image
- B树是一种平衡的
多路搜索树，多用于文件系统，数据库的实现。 - B树特点：
- 一个节点可以存储超过
2个元素，可以拥有超过2个子节点。 - 拥有二叉树的一些性质。
- 平衡，每个节点的所有子树高度一致。
- 比较矮。
- 一个节点可以存储超过
2、m阶B树的性质（m >= 2）
- 假设一个节点存储的元素个数为
x。- 根节点个数：
1 <= x <= m-1，三阶B树根节点数大于等于1并且小于等于2。 - 非根节点：
(m / 2)(向下取整) - 1 <= x <= m - 1 - 如果有子节点，子节点个数
y = x + 1- 根节点：
2 <= y <= m - 非根节点：
(m / 2)(向下取整) <= y <= m
- 根节点：
- 根节点个数：
image
3、B树 VS 二叉搜索树
- 将
二叉搜索树的节点合并，可以成为B树。 -
多代（父和子）节点合并，可以获得一个超级节点（类似3阶B树中的18和33节点，23和30节点）。-
2代合并的超级节点，最多拥有4个子节点（至少是4阶B树）。 -
3代合并的超级节点，最多拥有8个子节点（至少是8阶B树）。 -
n代合并的超级节点，最多拥有2^n个子节点（至少是2^n阶B树）。
-
image
- 将
18和33合并，23和30合并，20和21合并，45和47合并，50和52合并。即将一个B树变为二叉搜索树。
image
二、B树的操作
1、搜索
- 先在节点内部
从小到大搜索元素。 - 如果命中，搜索结束。
- 如果未命中，再去对应的
子节点中搜索元素，重复步骤1。
image
- 假设搜索
72，首先在根节点做比较，72大于40，所以接着在根节点的右子树搜索，72大于60小于80，继续在60和80之间的子树寻找，因为72大于70，所以需要继续往70的右子树寻找，但是右子树为空，所以得出结论72不在该B树上。
2、添加
- 新添加的元素必定是添加到
叶子节点。
image
- 假设插入
55，首先在根节点做比较，55大于40，所以接着在根节点的右子树搜索，55小于60，继续在60的左子树寻找，55大于50，所以将55插入在节点50的右侧。
image
- 假设插入
95，首先在根节点做比较，95大于40，所以接着在根节点的右子树搜索，95大于80，继续在80的右子树寻找，95大于90小于100，所以将95插入在节点90和100的中间。
3、上溢
image
- 假设再插入
98呢？（假设这是一颗4阶B树）- 最右下角的叶子节点的元素个数将超过限制。
- 这种现象可以称之为：
上溢（overflow）。
4、上溢的解决
- 假设
5阶B树。
image
- 上溢节点的元素个数必然等于
m（5）。 - 假设上溢节点最
中间元素的位置为k（3）。 - 将
k位置的元素向上与父节点合并。 - 将
[0,k-1]和[k+1,m-1]位置的元素分裂成2个子节点，这2个子节点的元素个数，必然都不会低于最低限制（m / 2(向下取整) - 1）。
image
- 一次分裂完毕后，有可能导致
父节点上溢，依然按照上述方法解决。
image
- 最极端的情况，有可能一致分裂到
根节点。 - 添加元素导致的上溢，是唯一一种可能导致B树
长高的操作。
5、添加导致上溢的例子
image
- 插入
98
image
-
98大于根节点，继续往根节点右子树比较，98大于60和80，继续往80右子树比较，98大于90，95，小于100，所以将98插入在95和100中间。 - 插入
98之后，90 95 98 100节点溢出，需要上溢，将中间元素95或98向上与父节点合并，将90，98，100节点分裂成2个子节点。 - 插入
52
image
- 插入
54
image
6、删除
- 假如需要
删除的元素在叶子节点中，那么直接删除即可。
image
- 删除
30
image
- 假如需要
删除的元素在非叶子节点中。- 先找到前驱或后继元素，
覆盖所需删除元素的值。 - 再把前驱或后继元素删除。
- 先找到前驱或后继元素，
- 删除
60
image
-
60的前驱为55，将55从54和55节点中删除，并将55覆盖60。
image
-
非叶子节点的前驱或后继元素，必定在叶子节点中。- 所以这里的删除前驱或后继元素，就是最开始提到的情况：删除的元素在叶子节点中。
- 真正的删除元素都发生在叶子节点中。
7、下溢
image
- 假设一颗
5阶B树，删除22。 - 叶子节点被删除一个元素后，元素个数可能会低于最低限制
（>= m/2(向下取整) - 1）。 - 这种现象称为：
下溢（underflow）。
8、下溢的解决
- 下溢节点的元素数量必然等于
(m/2(向下取整) - 2)。 - 如果下溢节点临近的
兄弟节点，有至少m/2(向下取整)个元素，可以向其借一个元素。
image
- 绿色节点在删除一个元素后，节点元素个数低于最低限制
（>= m/2(向下取整) - 1）。- 为了使树继续满足B树的要求，需要对绿色节点进行
下溢操作。 - 将父节点的元素
b插入到下溢节点的0位置（最小位置）。 - 用兄弟节点的元素
a（最大的元素）替代父节点的元素b。 - 这种操作其实就是：
旋转。 - 注意子节点
d也需要调整。
- 为了使树继续满足B树的要求，需要对绿色节点进行
image
- 如果下溢节点临近的兄弟节点，只有
（>= m/2(向下取整) - 1）个元素。- 将父节点的元素b挪下来跟左右子节点进行
合并。 - 合并后的节点元素个数等于
m/2(向下取整) + m/2(向下取整) - 2，不超过m-1。 - 这个操作可能会导致父节点下溢，依然按照上述方法解决，下溢现象可能会一直往上传播。
- 将父节点的元素b挪下来跟左右子节点进行
- 添加元素导致的下溢，是唯一一种可能导致B树
变矮的操作。
网友评论