Skip to content

Latest commit

 

History

History
288 lines (148 loc) · 9.8 KB

7-B树.md

File metadata and controls

288 lines (148 loc) · 9.8 KB
Raw

B树

1. B树简介

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

可能现在我们还不清楚B树是干啥的，但等我学完了之后如果有人再问我们

请问你心里有B树吗？

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

B树长这样（即最多拥有几个结点就叫几阶B树）：

image-20220419181727793

image-20220419181807820

通过我们对B树的仔细观察，我们似乎能发现一些B树的特点：

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

为什么叫B树呢？有一种说法是因为非常平衡(Balance)，可以看到B树的高度都很矮

那怎么区分是几阶B树呢? 我们看结点最多拥有多少个子结点，它就是多少阶B树

2. m阶B树的性质(m > 2)

假设一个结点存储的元素个数为x

我们有以下性质：

  • 如果该结点是根结点，那么它的元素个数x满足：1 <= x <= m-1

    例如上面的四阶B树，我们可以推断出其根结点元素个数必须大于等于1且小于等于3

  • 如果该结点是非根结点，其元素个数x满足：┌ m/2 ┐ − 1 ≤ x ≤ m − 1(m/2向上取整)

  • 如果有子结点，子结点个数 y = x + 1，即分支个数等于当前结点元素个数+1

    • 根结点的子结点满足：2 <= y <=m
    • 非根结点的子结点满足：┌ m/2 ┐ ≤ y ≤ m

我们举两个例子：

  • 比如 m = 3，2 ≤ y ≤ 3，因此可以称为（2, 3）树、2-3树
  • 比如 m = 4，2 ≤ y ≤ 4，因此可以称为（2, 4）树、2-3-4树
  • 比如 m = 5，3 ≤ y ≤ 5，因此可以称为（3, 5）树
  • 比如 m = 6，3 ≤ y ≤ 6，因此可以称为（3, 6）树
  • 比如 m = 7，4 ≤ y ≤ 7，因此可以称为（4, 7）树

思考：如果 m = 2，那B树是什么样子？

很显然根结点的子结点：2 <= y <=2，非根结点的子结点：1<= y <=2，显然就是一棵BST

你猜数据库实现中一般用几阶B树？

数据库里的B树一般是200 ~ 300阶，即一个结点能存储200到300个元素

3. B树 VS 二叉搜索树

我们先来看同一组数字组成的B树和BST树

image-20220420143841062

其实我们可以看到我们将BST简单处理就能得到3阶B树

image-20220420144137185

所以我们将BST的某些父子结点合并就能将其变成一棵B树

我们可以的出一些重要的结论：

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

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

    超级结点指的是B树上这种能同时存储多个数据的结点，即普通BST可以通过将子父祖结点合并从而得到超级结点

    这里我们也有一些结论：

    • 2代合并的超级节点，最多拥有 4 个子节点（至少是 4阶B树）
    • 3代合并的超级节点，最多拥有 8 个子节点（至少是 8阶B树）
    • n代合并的超级节点，最多拥有 2 n个子节点（ 至少是 2^n阶B树）

  • m阶B树，最多需要 log2m 代合并

4. B树搜索、添加

搜索

其实B树的搜索和BST的搜索过程非常类似

image-20220420145139634

具体过程为：

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

添加

我们首先需要知道：

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

这点性质和BST一样，BST插入一定会插入到叶子结点中，因为BST排序的性质，之前的元素都是排序好的

我们演示一下：

image-20220420150100975

image-20220420150116806

如果我们现在还要插入98呢？（假设这是一棵 4阶B树）

我们首先由B树的性质可以知道，四阶B树的叶子结点内存放的元素个数最多为3个，插入98显然会出现问题：

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

5. 上溢问题&解决（以五阶B树为例）

为了更好的分析上溢问题，这里以五阶B树进行举例

我们知道五阶B树一个结点中最多存储4个结点，如果超出了我们就称发生了上溢

image-20220515225034617

我们知道一旦发生了上溢现象，那么其元素个数一定等于阶数，即

  • 上溢节点的元素个数必然等于 m

解决：

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

  2. 将 k 位置的元素向上与父节点合并

  3. 将 [0, k-1] 和 [k + 1, m - 1] 位置的元素分裂成 2 个子节点

    这 2 个子节点的元素个数，必然都不会低于最低限制（┌ m/2 ┐ − 1）

    image-20220516092851100

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

最极端的情况，有可能一直分裂到根节点

我们来看一个比较合理的例子：

我们现在要在下面的B树上插入98这个结点

image-20220516093246584

显然结点95需要上溢

image-20220516093428401

我们插入结点52

image-20220516093459509

我们插入结点54，显然这个时候结点52会发生上溢现象且其父结点也会发生上溢

image-20220516093619903

上溢是唯一可能让B树长高的情况

image-20220517100947611

6. 删除元素

6.1 删除 – 叶子节点

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

例如我们要删除结点30，我们直接删除即可

image-20220516094115638

6.2 删除 – 非叶子结点

假如需要删除的元素在非叶子节点中，例如我们要删除结点60

image-20220516094324880

显然我们不能直接删除，因为如果删除了，那么结点40会有三个子结点，这显然是不符合B树性质的（┌ m/2 ┐ − 1 ≤ x ≤ m − 1）

这里我们的做法其实和二叉搜索树一样

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

image-20220516094825058

我们先找到前驱，即先找到左子树，再找左子树中最大的（一直往右找），找到元素55，我们用55覆盖掉我们想要删除的结点60，接着我们再将结点55删除

image-20220516095057002

注意：

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

7. 下溢问题

7.1 旋转解决下溢

假设我们有一棵五阶B树，我们现在需要删除结点22

image-20220516095910327

我们会发现：叶子节点被删掉一个元素后，元素个数可能会低于最低限制（ ≥ ┌ m/2 ┐ − 1 ）

这种现象称为：这种现象称为：下溢（underflow）

这里我们有几个结论：

  • 下溢节点的元素数量必然等于 ┌ m/2 ┐ − 2
  • 如果下溢节点临近的兄弟节点，有至少 ┌ m/2 ┐ 个元素，可以向其借一个元素

所以我们对下溢的解决方法是（父结点下来，挑一个兄弟结点的孩子做父亲）：

  • 将父节点的元素 b 插入到下溢节点的 0 位置（最小位置）
  • 用兄弟节点的元素 a（最大的元素）替代父节点的元素 b
  • 这种操作其实就是：旋转

image-20220517095538748

7.2 合并解决下溢

如果下溢节点临近的兄弟节点，只有 ┌ m/2 ┐ − 1 个元素，显然就不能通过旋转解决下溢问题，这时我们需要通过合并来解决

  • 将父节点的元素 b 挪下来跟左右子节点进行合并
  • 合并后的节点元素个数等于┌ m/2 ┐ + ┌ m/2 ┐ − 2，不超过 m − 1

image-20220517095514955

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

如果一直下溢到根结点，根结点如果元素个数不够，就会和子结点合并，这样B树高度就会减一

8. 练习

请画出四阶B树添加元素从1到20的图

可以在这个网站上看B树生长的过程：https://cdn.fengxianhub.top/eureka-static/Visualization/BTree.html

最后面结果就是这样的：

image-20220517113030211

image-20220629082706891