6.2 B树 & B+树

1. B树基本性质（又称为多路平衡查找树）（包括 B树的高度计算方法）

• B树中所有结点的孩子结点数最大值称为B树的阶，通常用m表示，一颗m阶B树或为空树，或满足以下条件
• 每个结点最多有m棵子树
• 若结点不是终端结点，至少有两棵子树
• 出根结点外的非叶结点至少有 ⌈m/2⌉ 棵子树
• 非叶子结点结构

结点结构

n为该结点孩子数量，p是指针，k是关键字。
p0指向的结点的数均小于k1，p1指向的结点的数均大于k1，小于k2，如此类推

2. B树查找

1. 找到结点，在结点内找指向下一个结点的指针
2. 在最终的结点找关键字。
   由于B树常存储在磁盘上，则前一个查找操作是在磁盘上进行的，而后一个查找操作是在内存中进行的，即在找到目标结点后，先将结点中的信息读入内存，然后再采用顺序查找法或折半查找法查找等于K的关键字。

根据B树查找规律可知，每在磁盘中查找到一个结点，需把结点读取到内存里通过对比寻找关键字 / 找到指向下一个结点的指针。
计算机中，磁盘读取尤为耗费时间，所以，B树查找的时间复杂度主要计算关键字在第几层即可（每一层需要从磁盘读取一个结点到内存中）。

• 假设一颗包含 n 个关键字、高度为 h 、阶数为 m 的B树
  此时影响B树高度的是每个结点所包含的子树数，如果尽可能使结点子树数都等于 ⌈m/2⌉ ，则层数最多，最坏情况；如果尽可能使结点子树数都等于 m ，则层数最少，最好情况。
  1. 最好情况：h >= log_m(n + 1)
  2. 最坏情况：h <= log_⌈m/2⌉((n + 1) / 2) + 1

3. B树插入

插入本是直接加入相应叶子结点的相应位置就没问题了。
但是存在特殊情况，那就是插入后，结点的关键字个数大于m。
因此，B树的关键字插入分为两个步骤：

1. 定位：通过查找，找到最底层的结点，便是该插入的位置了。
2. 插入：如果给结点的关键字个数小于等于m - 1，直接插入，否则进行分裂插入
3. 分裂插入：插入后，对结点进行分裂，分裂后的新结点插入到其父结点中。如果造成父结点的关键字也超过上限，继续分裂。

4. B树删除

分为三种情况：

1. 直接删除关键字
2. 删除关键字后，结点的关键字小于 ⌈m/2⌉ 。与相邻兄弟，合并，然后分裂。（从相邻兄弟中取部分关键字，并在双亲结点中，两兄弟指针之间的关键字调整）
3. 删除关键字之后，结点的关键字小于 ⌈m/2⌉，而相邻的兄弟关键字结点等于 ⌈m/2⌉不能借。两个结点合并。（此时需从双亲结点中删除关键字，双亲结点也要进行删除关键字操作。）

5. B+树

与B树不同之处：

1. 每个结点都少了大于k_n的子树，即没有了指针p_n，所以每个结点的子树最多只有m - 1
2. 非叶子结点不存储关键字，里面的key只是区分其子树的分界数，所有关键字存储于叶子结点
3. 所有叶子结点内的数字按顺序排列，且叶子节点之间按顺序相互链接