一. B-树特征和基本概念：
B-树中所有结点孩子结点个数的最大值是B-树的阶。
对于一个 m 阶的B-树（为了查找效率考虑，要求m >= 3）：
结构要求：
1. 根节点至少有2个分支，1个关键字
2. 非根结点至少有 m/2（向上取整）个分支，（m/2） - 1 个关键字。
3. 所有结点最多有 m 个分支，m - 1 个关键字。（与B+树的区别）
特点：
1. 有 n 个分支的结点有 n - 1 个关键字 ，他们按递增顺序排列。
2. 结点内个关键字互不相等且按从小到大排列。
3. 各个底层结点是叶结点，他们处于同一层；叶结点下面是失败结点（可以用空指针表示），是查找失败到达的位置。
结构：
| n | k1 | k2 | …… | kn |
| p0 | p1 | p2 | …… | pn |
（注：B-树是平衡m 叉查找树，但限制更强，要求所有叶节点在同一层。）
二. B-树查找操作：
特点：是二叉排序树的扩展，二叉排序树是二路查找，B-树是多路查找。
节点内进行查找的时候除了顺序查找之外，还可以用折半查找来提高效率。
三. B-树插入操作：
首先：插入位置一定在叶结点上！
注意：m阶B-树关键字个数范围是(m/2)-1（向上取整）~ m-1
过程：
1. 按照B-树的查找方法找到插入位置（一定在叶节点上），然后直接插入。
2. 插入后检查被插入结点内关键字的个数：
1）如果关键字个数大于m-1，则需要进行拆分。进行拆分时，结点内的关键字若已经有m个，此时取出第 m/2 (向上取整) 个关键字
2）并将第 1~(m/2) -1个关键字和第(m/2)+1~m个关键字（即第m/2关键字的左右不分）做成两个结点连接在第 m/2 个关键字左右的指针上
3）并将第m/2个关键字插入其父节点相应的位置中
4）如果在其父结点内又出现了关键字个数超出规定范围的情况，则继续进行拆分操作。（这就是插入结点所引起的连锁反应）
特点：插入操作只会是的B-树逐渐变高而不会改变叶子结点在同一层的特性。
四. B-树删除操作：
分两种情况：
（一）删除结点在叶子结点上
1. 结点内的关键字个数大于m/2(上取整)-1，可以直接删除（大于关键字个数下限，删除不影响B-树特性）
2. 结点内的关键字个数等于m/2(上取整)-1（等于关键字个数下限，删除后将破坏B-shu特性），此时需观察该节点左右兄弟结点的关键字个数：
1）如果其左右兄弟结点中存在关键字个数大于m/2-1的结点，则从关键字个数大于m/2-1的兄弟结点中借关键字：
采用覆盖操作：用需删除结点的父节点关键字覆盖需删除结点，再用关键字个数大于m/2-1的兄弟结点借关键字覆盖父节点，在删除原兄弟结点的借关键字。
2） 如果其左右兄弟结点中不存在关键字个数大于m/2-1的结点，这是需要进行结点合并：
将其父结点中的关键字拿到下一层，与该节点的左右兄弟结点的所有关键字合并
3）如果出现2所述的情况，会使得其父节点中关键字个数少于规定个数，出现这种情况时需要对其父结点继续进行合并操作。（这就是由于删除结点引起的连锁反应）
（二）删除结点在非叶子结点上
1. 首先要将其转化成在叶子节点上，再按上述（一）进行删除操作
2. 转化过程：
1）找到相邻关键字：即需删除关键字的左子树中的最大关键字或右子树中的最小关键字（可以先到左子树，再一直按右指针往下找；或在右子树中，按左指针往下找）
2）用相邻关键字来覆盖需删除的非叶子节点关键字，在删除原相邻关键字。