第七章第二节：B树和B+树

教程：

1. B树： https://www.bilibili.com/video/BV1b7411N798/?p=72&share_source=copy_web&vd_source=d228985826b563972268952905224139
2. B+树： https://www.bilibili.com/video/BV1b7411N798/?p=74&share_source=copy_web&vd_source=d228985826b563972268952905224139

1. B树

---

---

---

---

1.1 B树的定义

B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或为满足如下特性的m叉树:

• 树中每个结点至多有m棵子树，即至多含有m-1个关键字。
• 若根结点不是终端结点，则至少有两棵子树。
• 除根结点外的所有非叶结点至少有「m/2]棵子树，即至少含有[m/2]-1个关键字。
• 所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空)。
  所有非叶结点的结构如下:

1.2 B树的高度

---

总结：

1.3 B树的插入和 删除

如果要插入80；溢出



插入90；


插入99；




插入83，87，再插入70；





核心：

1.4 B树的删除

要删除60这个关键字：


要删除80；

---

---

删除77；

对非终端结点关键字的删除,必然可以转化为对终端
结点的删除操作

如果删除38这个元素，低于下限；

---

---

删除90；

---

删除49；

1.5 总结：

2. B+树

---

---

2.1 B+树的查找

2.2 B+树与B树的对比

---

---

2.3 总结