1.B树
定义：B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一颗m阶B树或为空树，或为满足如下特性的m叉树。
- 1.树中每个结点至多有m颗子树，即至多含有m-1个关键字。
- 2.若根结点不是终端结点，则至少有俩颗子树。
- 3.除根节点外的所有非叶子结点至少有┌(m/2)┐颗子树，即至少含有┌(m/2)┐-1个关键字。
- 4.所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。
m阶B树的核心特性：
- 1.根节点的子树∈[2, m]，关键字树属于[1, m-1]。其它节点的子树数∈[┌(m/2)┐， m]，关键字数∈[┌(m/2)┐-1，m-1]。
- 2.对任一结点，其所有子树高度都相同。
- 3.关键字的值：子树0 < 关键字1 < 子树1 < 关键字2 < ...（类比二叉查找树左 < 中 < 右）
B树的高度:
问题:含n个关键字的m阶B树，最小高度，最大高度是多少?
- 1.最小高度——让每个结点尽可能的满，有m-1个关键字，m个分叉，则有n ≤ (m-1)(1 + m + m2 + m3 + ... + mh-1) = mh - 1，因此h ≥ logm(n+1)
- 2.最大高度——让各层的分叉尽可能的少，即根节点只有2个分叉，其他结点只有┌(m/2)┐个分叉，各层结点至少有：第一层1，第二层2，第三层2┌(m/2)┐ ... 第h层2(┌(m/2)┐)h-2。
第h+1层共有叶子结点（失败结点）2(┌(m/2)┐)h-1个。
n个关键字的B树必有n+1个叶子结点，则n+1 ≥ 2(┌(m/2)┐)h-2，即h ≤ log┌(m/2)┐(n+1)/2 + 1
2.B树的插入
5阶B树——结点关键字个数┌(m/2)┐ - 1 ≤ n ≤ m-1，即：2 ≤ n ≤ 4（此处省略失败结点）
- 1.在插入key后，若导致原结点关键字树超过上限，则从中间位置（┌(m/2)┐）将其中的关键字分为俩部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置（┌(m/2)┐）的结点插入原结点的父结点。
- 2.若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致B树高度增1。
注：新元素一定是插入到底层“终端结点”,用查找来确定插入位置
核心要求：
- 1.对m阶B树——除根结点外，结点关键字个数┌(m/2)┐-1 ≤ n ≤ m-1
- 2.子树0 ＜ 关键字1 < 子树1 < 关键字2 < 子树2 < ...
3.B树的删除
- 1.若被删除关键字在终端节点，则直接删除该关键字（要注意结点关键字个数是否低于下限┌(m/2)┐-1
- 2.若被删除关键字在非终端节点，则用直接前驱或直接后继来代替被删除的关键字
- 直接前驱：当前关键字左侧指针所指子树中“最右下”的元素
- 直接后继：当前关键字右侧指针所指子树中“最左下”的元素
- 3.若删除的关键字低于其下限
- 当其右兄弟结点很宽裕时，使用当前结点的后继，后继的后继来填补空缺
- 当其左兄弟结点很宽裕时，使用当前结点的前驱，前驱的前驱来填补空缺
- 当其左右兄弟结点都刚好是下限时，则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并
4.B+树
一颗m阶的B+树需满足下列条件：
- 1.每个分支结点最多有m颗子树（孩子结点）。
- 2.非叶根结点至少有俩颗子树，其他每个分支结点至少有┌m/2┐颗子树。
- 3.结点的子树个数与关键字个数相等。
- 4.所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大学顺序排列，并且相邻叶结点按大小顺序相互连接起来。
- 5.所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针。
- 6.B+树中，无论查找成功与否，最终一定都要走到最下面一层结点。
5.B+树与B树对比
1.m阶B+树
- 1.结点中的n个关键字对应n颗子树。
- 2.根结点的关键字树n∈[1，m]；其他结点的关键字树n∈[┌m/2┐，m]。
- 3.在B+树中，叶结点包含全部关键字，非叶结点中出现过的关键字也会出现在叶结点中。
- 4.在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
2.m阶B树
- 1.结点中的n个关键字对应n+1颗子树。
- 2.根结点的关键字树n∈[1，m-1]；其他结点的关键字树n∈[┌m/2┐-1，m-1]。
- 3.在B树中，各结点中包含的关键字是不重复的。
- 4.B树的结点中都包含了关键字对应的记录的存储地址。
