B树
B 树就是 B-树，B即balance，原为B-tree，翻译而来，其中间的-起连接作用，而非减
定义
B树为多路搜索树（并非二叉树）
一个 m 阶B树
- 每个节点最多有 m-1 个关键字
- 根节点最少可以只有 1 个关键字
- 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它
- 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同
- 每个节点都存有索引和数据，也就是对应的key和value
即根节点关键字数量为[1,m)，非根节点关键字数量为[m / 2 - 1, m)，其中 m / 2 向上取整
插入
B树的插入需要满足以下分裂规则：
判断当前结点key的个数是否小于等于m-1，如果满足，直接插入即可，如果不满足，用节点的中间的key将这个节点分为左右两部分，中间的节点放到父节点中即可
如下图，一个五阶 B 树，节点最多有4个key，最少为2个
- 插入 16，40，55，70
- 插入 22
在插入 22 后，这个节点关键词数量已经大于4了，所以需要分裂，分裂规则如上，分裂后如下图
- 接着插入30，35，39
- 分裂得到如下
删除
B树的删除相对于插入相对复杂，但也有规律可循
- 如下图的五阶B树
- 删除 12 ，删除之后 该节点数还是大于 m / 2 - 1，直接删除即可
- 完成后接着删除 22 ，因为 22 是非叶子节点，对于非叶子节点的删除，我们需要用后继key（元素）覆盖要删除的key，然后在后继key所在的子支中删除该后继key，对于删除 22，需要将后继元素 23 移到被删除的 22 所在的节点
- 但是删除后发现 25 节点只有一个元素，小于 2 （m / 2 - 1）个，则该节点不符合要求，则此时：如果删除叶子节点，如果删除元素后元素个数少于（[m/2]-1），并且它的兄弟节点的元素大于（[m/2]-1），也就是说兄弟节点的元素比最少值[m/2]-1还多，将先将父节点的元素移到该节点，然后将兄弟节点的元素再移动到父节点
- 操作如下
- 接着删除 26，删除叶子节点，删除后不满足要求，所以，我们需要考虑向兄弟节点借元素，但是，兄弟节点也没有多的节点（2个），借不了，怎么办呢？如果遇到这种情况，首先，还是将先将父节点的元素移到该节点，然后，将当前节点及它的兄弟节点中的key合并，形成一个新的节点
- 移动之后再将将其与兄弟节点合并
B+树
B+树其实和B树是非常相似的
相同点
- 根节点至少一个元素
- 非根节点元素范围：[m / 2 - 1,m)
不同点
- B+树有两种类型的节点：内部结点（也称索引结点）和叶子结点。内部节点就是非叶子节点，内部节点不存储数据，只存储索引，数据都存储在叶子节点
- 内部结点中的 key 都按照从小到大的顺序排列，对于内部结点中的一个 key，左树中的所有 key 都小于它，右子树中的 key 都大于等于它。叶子结点中的记录也按照 key 的大小排列
- 每个叶子结点都存有相邻叶子结点的指针，叶子结点内部按关键字的大小自小而大顺序连接
- 父节点存有右孩子的第一个元素的索引
插入
以下用5阶B+树示例
- 插入 17，19，23，25
- 插入 30，此时数量大于4，分裂
- 接着插入 40，66
- 继续分裂
删除
B+树的删除相比与B树简单
因为叶子节点有指针的存在，向兄弟节点借元素时，不需要通过父节点了，而是可以直接通过兄弟节移动即可（前提是兄弟节点的元素大于[m/2]-1），然后更新父节点的索引；如果兄弟节点的元素不大于[m/2]-1（兄弟节点也没有多余的元素），则将当前节点和兄弟节点合并，并且删除父节点中的key
就不图示了
小结
B+树相比B树有一些优点：
- 单一节点存储的元素更多，使得查询的IO次数更少，所以也就使得它更适合做为数据库MySQL的底层数据结构
- 所有的查询都要查找到叶子节点，查询性能是稳定的，而B树，每个节点都可以查找到数据，所以不稳定
- 所有的叶子节点形成了一个有序链表，更加便于查找
