B树的定义
B树也是一种平衡树，是一个多叉树（AVL是二叉平衡树）。B树的每个节点内可以存多个数据，可以有多个子节点，且所有叶子节点都在同一层。单个节点最大的分支数称为阶（Order），阶数为m的B树有以下性质：
-
平衡：B树通过调整节点的分裂和合并来保持树的平衡，确保所有叶子节点在同一层，从而保证了查找、插入和删除操作的时间复杂度为 O(log n)。
-
有序：B树的节点内关键字是有序排列的，且任意一个节点的关键字都大于其左子树中的所有关键字，小于其右子树中的所有关键字。
-
多路：对于m阶B树：
-
每个节点最多有m个子节点，至少有⌈m/2⌉个子节点（根节点除外）。
-
每个节点内可以存储最多m-1个关键字，至少存储⌈m/2⌉-1个关键字（根节点除外）。
-
k个分支的节点有k-1个关键字。
-
B树的构建
对于1，4，5,7,13,26，11，3，45这样的数构建一个4阶B树：
4阶B树每个节点最多有4个子节点，最多存3个关键字，至少存2个关键字。
从空树开始插入：
- 插入1：根节点[1]
- 插入4：根节点[1,4]
- 插入5：根节点[1,4,5]
- 插入7：根节点满，分裂为两个节点，[4]溢出（上移）变成根节点，左子节点[1],右子节点[5,7]
- 插入13：右子节点[5,7,13]
- 插入26：右子节点满，分裂为两个节点，[7]溢出（上移）到根节点，变成[4,7]，左子节点[1],中间子节点[5],右子节点[13,26]
- 插入11：右子节点[11,13,26]
- 插入3：左子节点[1,3]
- 插入45：右子节点满，分裂为两个节点，[13]溢出（上移）到根节点，变成[4,7,13]，左子节点[1,3],中间左子节点[5],中间右子节点[11],右子节点[26,45]
B树的搜索
和二叉搜索树类似，B树的搜索过程也是从根节点开始，因为其有序性，关键字小则走左子树，大则走右子树，直到找到目标关键字或到失败节点。
B树的插入
插入操作从根节点开始，遵循小左大右的顺序。插入的地方一定是叶子节点。
m阶B树，每个节点最多有m个子节点：
-
如果该节点未满，则直接插入
-
如果该节点已满，则需要进行节点分裂，将中间关键字提升到父节点，并将节点分裂为两个子节点。
这个过程可能会递归地向上进行，直到根节点。
当根节点满时，分裂根节点并创建一个新的根节点，树的高度增加1。
B树的删除
删除需要担心下溢出
先用搜索找到要删除的关键字所在的节点：
-
如果关键字在叶子节点中，直接删除即可。
-
删除非叶节点的元素，需要找到其前驱或后继节点来替代，然后删除前驱或后继节点。前驱是左子树的最大值，后继是右子树的最小值。均在叶节点。
-
删除后，如果节点的关键字数少于⌈m/2⌉-1，则需要进行调整：
- 借位：如果相邻兄弟节点有多余的关键字（拿走一个不发生下溢出），兄弟节点的父节点关键字下移到当前节点，兄弟节点的一个关键字上移到父节点。
- 合并：如果相邻兄弟节点也没有多余的关键字，则将一个兄弟节点的父节点下移，并将当前节点和兄弟节点合并为一个节点。
-
如果向左兄弟合并，则左兄弟的父节点关键字下移到左兄弟节点的末尾，当前节点的所有关键字和子节点也移动到左兄弟节点的末尾。
-
如果向右兄弟合并，则当前节点的父节点关键字下移到当前节点的末尾，右兄弟节点的所有关键字和子节点也移动到当前节点的末尾。
-
合并后，父节点的关键字数减少1，如果父节点下溢出，则递归地进行调整，向该父节点的左右兄弟借，注意需要带着子树一起动
-
如果根节点下溢出且没有关键字了，则树的高度减少1，新的根节点是原根节点的唯一子节点。