B-Tree
B-Tree 不是 Binary Tree（二叉树，每个节点最多有两个子树），B 的意思是 Balance, 一棵 M 阶的 B-Tree 满足以下条件：
B-Tree的节点包含两部分：
- 关键字，k 个关键字构成了 k+1 个开区间，指向 k+1 个孩子节点
- 数据
B-Tree的特点：
- 树的 根节点 拥有的子节点数量子在 2- M 之间；
- 除根外，每个 非叶子节点 拥有的子节点数量在 M/2 - M 之间；
- 一个 非叶子节点 如果包含 k 个关键字，那么它有 k+1 个子节点；
- 所有叶子节点都在相同的深度，且叶子节点不包含关键字信息；
一个 4 阶 B-Tree：
插入过程
针对 m 阶高度 h 的 B-Tree，插入一个元素时，首先在 B-Tree中是否存在，如果不存在，即在叶子结点处结束，然后在叶子结点中插入该新的元素。
- 若该节点元素个数小于m-1，直接插入；
- 若该节点元素个数等于m-1，引起节点分裂；以该节点中间元素为分界，取中间元素（偶数个数，中间两个随机选取）插入到父节点中；
- 重复上面动作，直到所有节点符合B-Tree的规则；最坏的情况一直分裂到根节点，生成新的根节点，高度增加1；
插入的例子（为了直观而先插入元素，然后判断是否要分裂）：
（1）5 阶 B-Tree，插入前：
（2）插入 19，引起 14、16、17、18 的节点分裂，把中间元素【17】上移到父节点中，但是情况来了，父节点中空间已经满了，所以也要进行分裂，将父节点中的中间元素【13】上移到新形成的根结点中，这样具体插入操作的完成。
删除过程
首先，查找 B-Tree中需删除的元素，如果该元素在 B-Tree中存在，则将该元素在其节点中进行删除；删除该元素后，首先判断该元素是否有左右孩子节点， 如果有，则上移孩子节点中的某相近元素（「左孩子最右边的节点」或「右孩子最左边的节点」）到父节点中，然后是移动之后的情况；如果没有，直接删除。
- 某节点中元素数目小于 m/2-1、m/2 向上取整，则需要看其相邻兄弟节点是否丰满。
- 如果其相邻兄弟都不丰满，即其节点数目刚好等于 m/2-1，则该节点与其相邻的某一兄弟节点进行「合并」成一个节点。
- 如果其相邻兄弟丰满（节点中元素个数大于 m/2-1），则向父节点借一个元素来满足条件。
接下来用一个 5 阶 B-Tree为例，详细讲解删除的操作。
如图所示，接下来要依次删除 8，20，18，5。 首先要删除元素 8。先查找到元素 8 在叶子节点中，删除 8 后叶子节点的元素个数为 2，符合 B-Tree的规则。然后需要把元素 11 和 12 都向前移动一位。完成后如图所示。
下一步，删除 20，因为 20 没有在叶子节点中，而是在中间节点中找到，可以发现 20 的继承者是 23（字母升序的下个元素），然后需要将 23 上移到 20 的位置，之后将孩子节点中的 23 进行删除。 删除后检查一下，该孩子节点中元素个数大于 2，无需进行合并操作。
所以这一步之后，B-Tree如下图所示。
下一步删除 18，18 在叶子节点中，但是该节点中元素数目为 2，删除导致只有 1 个元素，已经小于最小元素数目 2。而由前面已经知道：如果其某个相邻兄弟节点中比较丰满（元素个数大于 5/2），则可以向父节点借一个元素，然后将最丰满的相邻兄弟节点中上移最后或最前一个元素到父节点中。在这个实例中，右相邻兄弟节点中比较丰满（3 个元素大于 2），所以先向父节点借一个元素 23 下移到该叶子节点中，代替原来 19 的位置。19 前移。然后 24 在相邻右兄弟节点中，需要上移到父节点中。最后在相邻右兄弟节点中删除 24，后面的元素前移。
这一步之后，B-Tree如下图所示。
最后一步需要删除元素 5，但是删除后会导致很多问题。因为 5 所在的节点数目刚好达标也就是刚好满足最小元素个数 2。 而相邻的兄弟节点也是同样的情况，删除一个元素都不能满足条件，所以需要该节点与某相邻兄弟节点进行合并操作；首先移动父节点中的元素（该元素在两个需要合并的两个节点元素之间）下移到其子节点中。 然后将这两个节点进行合并成一个节点。所以在该实例中，首先将父节点中的元素 4 下移到已经删除 5 而只有 6 的节点中，然后将含有 4 和 6 的节点和含有 1，3 的相邻兄弟节点进行合并成一个节点。
这一步之后，B-Tree如下图所示。
但是这里观察到父节点只包含了一个元素 7，这就没有达标（因为非根节点包括叶子节点的元素数量 
必须满足于[2, 4] ）。如果这个问题节点的相邻兄弟比较丰满，则可以向父节点借一个元素。而此时兄弟节点元素刚好为 2，刚刚满足，只能进行合并，而根节点中的唯一元素 13 下移到子节点。这样，树的高度减少一层。
所以最终的效果如下图。
B-Tree 的复杂度分析
B-Tree高度的证明过程：
结论 对于一颗数阶=M, 高度=h, 索引了 N 个元素的 B-Tree:
树高 h 的上限: $\log_M ((N+1)/2)$
查找一个元素的时间复杂度为: $O\log_M N$
插入复杂度:
- 先查找 $O\log_M N$
- 插入会发生结点的分裂操作, 分裂操作可以认为是常数级别, 最坏情况引起 root 以下所有节点分裂
- 所以插入时间复杂度一般情况下等于 $O\log_M N$
删除复杂度:
- 先查找 $O\log_M N$
- 删除会引起合并操作, 分析同插入情形
- 所以插入时间复杂度一般情况下等于 $O\log_M N$
上面的分析都是基于所有节点都在内存中, 没有访问硬盘. 但实际上基于外部存储的 B-Tree 最耗时的是磁盘的 IO 次数. 如果从磁盘 IO 的角度分析插入和删除的耗时：
- 删除操作的磁盘 IO 次数: 如果删除引起了节点合并, 最坏情况下磁盘访问次数是 3h ＝（找到包含被删除元素需要 h 次读访问）+（获取第 2 至 h 层的最相邻兄弟需要 h-1 次读访问）+（在第 3 至 h 层的合并需要 h-2 次写访问）+（对修改过的根节点和第 2 层的两个节点进行3次写访问）
- 插入操作引起的磁盘 IO: 当插入操作引起了 s 个节点的分裂时，磁盘访问的次数为
h(读取搜索路径上的节点)＋2s(更新两个分裂出的新节点)＋1（回写新的根节点或插入后没有导致分裂的节点）。因此，所需要的磁盘访问次数是 h+2s+1，最多可达到 3h+1。因此插入的代价是很大的。
一般实际应用中，M 是非常大的数字，通常超过 100，因此 h 非常小（通常不超过 3），业界公认 MySQL 单表容量在 1KW 以下是最佳状态，因为这时它的 BTREE 索引树高 h = 3~5之间。
B+Tree
与B-Tree相比，B+Tree有以下不同点：
- 有 k 个子树的中间节点包含有 k 个关键字（B-Tree中是 k-1个）@doubt
- 非叶子节点没有 data, 只存储关键字和关键字对应的指针（非叶子节点仅存索引）;
- 叶子节点存储了所有的关键字和关键字对应的 data（叶子节点包含所有的关键字和数据）；
- 相邻的叶子节点按顺序形成单链表（叶子节点在一条链表中）; // @duobt: 单向链表 还是 双向链表？
各种资料上 B+树的定义各有不同，上面的定义方式是关键字个数和孩子结点个数相同，这里我们采取维基百科上所定义的方式，即关键字个数比孩子结点个数小1，这种方式是和B-Tree基本等价的（B+ tree - Wikipedia）：
➤ 为什么说 B+树比 B-Tree更适合数据库索引？
1）B+树的磁盘读写代价更低
B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B-Tree更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了；
2）B+树查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当；
3）B+树便于范围查询（最重要的原因，范围查找是数据库的常态）
B-Tree在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题，正是为了解决这个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。
补充：B-Tree的范围查找用的是中序遍历，而B+树用的是在链表上遍历
MySQL如何使用索引
MySQL 使用 B+Tree 作为索引，数据库表中每个索引都可以认为是一个 B+Tree 结构
聚集索引，B+Tree 的叶子节点存储的内容是每一行的数据，所以表在磁盘上的存储顺序与索引的顺序一致
非聚集索引，叶子节点存储的内容不是真实行数据，而是主键的值表，所以数据存储顺序与索引顺序无关。通过非聚簇索引查询要再回主键的 B-Tree查询才能得到数据（回表）, 所以也叫二级索引
查询非聚集索引也有不需回表的情况：
覆盖索引（covering index ）：即查询使用的索引，恰好覆盖了查询需求，这种情况下不必再回表
例如：
- select 查询的列是主键
- select 查询的列 = where 条件的列，且这个列上有索引
- 使用联合索引的情况：例如 A，B 两个列组成联合索引，查询的需求恰好被这个联合索引覆盖（如
select A, B），这种情况下不需要回表，但是如果select A,B,C的情况，联合索引就无法覆盖了
MyISAM和InnoDB索引区别
InnoDB: 主键的索引 B+Tree, 叶子节点存储的数据即一行完整数据(聚集索引), InnoDB 的辅助索引的叶子节点存储的是 主键的值 (非聚集索引)
MyISAM 的主键和非主键索引, 叶子节点存储的都是数据行的地址
@ref: