B-树
定义：B-树是一类树，包括 B-树、B+树、B* 树等，是一棵自平衡的搜索树，它类似普通的平衡二叉树，不同的一点是 B-树允许每个节点有更多的子节点。B-树是专门为外部存储器设计的，如磁盘，它对于读取和写入大块数据有良好的性能，所以一般被用在文件系统及数据库中。
为什么会出现 B-树这类数据结构？
传统用来搜索的平衡二叉树有很多，如 AVL 树，红黑树等。这些树在一般情况下查询性能非常好，但当数据非常大的时候它们就无能为力了。
原因是当数据量非常大时，内存不够用，大部分数据只能存放在磁盘上，只有需要的数据才加载到内存中。一般而言内存访问的时间约为 50ns，而磁盘在 10ms 左右，相差了近 5 个数量级。这说明程序大部分时间会阻塞在磁盘 IO 上。
那么我们如何提高程序性能？减少磁盘 IO 次数。像 AVL 树，红黑树这类平衡二叉树从设计上无法“迎合”磁盘。
平衡二叉树是通过旋转来保持平衡的，而旋转是对整棵树的操作，若部分加载到内存中则无法完成旋转操作。其次平衡二叉树的高度相对较大为 log2n，这样逻辑上很近的节点实际可能非常远，无法很好的利用磁盘预读（局部性原理），所以这类平衡二叉树在数据库和文件系统上的选择就被 pass 了。
空间局部性原理：如果一个存储器的某个位置被访问，那么将它附近的位置也会被访问。
从“迎合”磁盘的角度来看看 B-树的设计。
索引的原理其实是不断的缩小查找范围，就如我们平时用字典查单词一样，先找首字母缩小范围，再第二个字母等等。平衡二叉树是每次将范围分割为两个区间。为了更快，B-树每次将范围分割为多个区间，区间越多，定位数据越快越精确。
那么如果节点为区间范围，每个节点就较大了。所以新建节点时，直接申请页大小的空间（磁盘是按 block 分的，一般为 512 Byte。磁盘 IO 一次读取若干个 block，我们称为一页，具体大小和操作系统有关，一般为 4k，8k或 16k），计算机内存分配是按页对齐的，这样就实现了一个节点只需要一次 IO。
上图是一棵简化的 B-树，多叉的好处非常明显，有效的降低了 B-树的高度，为底数很大的 logn。一般一棵 B-树的高度在 3 层左右。
B-树的每个节点是 n 个有序的序列（a1, a2, a3, … , an），并将该节点的子节点分割成 n+1 个区间来进行索引（X1< a1 < X2 < a2 < … < an < Xn+1）。
一个 m 阶的 B-树满足以下条件：
- 有 k 棵子树的分支结点存在 k-1 个关键码，关键码按照递增次序进行排列；
- 根结点至少拥有两颗子树（存在子树的情况下），至多拥有 m 棵子树；
- 除了根结点以外，每个结点至多拥有 m 棵子树，其余每个分支结点至少拥有 m/2 棵子树（即关键字数量 n 需要满足 ⌈m/2⌉-1 ≤ n ≤ m-1）；
- 所有的叶结点都在同一层；
B-树的查找
我们来看看 B-树的查找，假设每个节点有 n 个 关键字，被分割为 n+1 个区间，注意，每个 关键字紧跟着 data 域，这说明 B-树的关键字和 data 是聚合在一起的。一般而言，根节点在内存中，B-树以每个节点为一次磁盘 IO，比如上图中，若搜索关键字为 25 节点的 data，首先在根节点进行二分查找（因为 keys 有序，二分最快），判断关键字 25 小于关键字 50，所以定位到最左侧的节点，此时进行一次磁盘 IO，将该节点从磁盘读入内存，接着继续进行上述过程，直到找到该关键字为止。
一个酷炫的网页，可以自己插入删除节点，观察 B-树的变化情况：
https://www.cs.usfca.edu/~galles/visualization/BTree.html
B-树的插入规则
新结点一般插入在最底层，通过搜索找到对应的结点进行插入，根据即将插入的结点的关键字数量又分为下面几种情况：
- 如果该结点的关键字个数没有到达 m-1 个，那么直接插入即可；
- 如果该结点的关键字个数已到达了 m-1 个，无法满足 B-树的性质，需要将其进行分裂。分裂的规则是该结点分成两半，将中间的关键字提升到父亲结点中，这又可能导致父节点的分裂，那就继续向上回溯（甚至是要对根结点进行分裂，那么整棵树都加了一层）。
过程如下：
B-树的删除规则
先通过搜索找到相应的值，存在则进行删除：
- 如果该结点拥有关键字数量仍然大于或等于 ⌈m/2⌉-1，则不做任何处理；
- 如果该结点在删除关键字以后，关键字数量小于 ⌈m/2⌉-1，则需要向兄弟结点借关键字，这又分为兄弟结点的关键字数量是否足够的情况：
- 如果兄弟结点借出一个关键字仍满足 B-树性质，则将该节点与兄弟节点之间夹的父亲结点关键字下移，兄弟结点的关键字上移；
- 如果兄弟结点的关键字在借出以后无法满足情况，那么我们可以将该结点合并到兄弟结点中，合并之后的子结点数量少了一个，则需要将父亲结点的关键字下放，如果父亲结点不满足性质，继续向上回溯；
过程如下：
B+树
B+树是 B-树的变种，它与 B-树的不同之处在于：
- 在 B+树中，关键字的副本存储在内部节点，真正的关键字和 data 存储在叶子节点上（所有的 data 都在最后一层）。
- n 个关键字的节点指针域为 n 而不是 n+1。
每个节点关键字的数量范围依然是 ⌈m/2⌉-1 ~ m-1，顺序递增。
因为内节点并不存储 data，所以一般 B+树的叶节点和内节点大小不同。为了增加区间访问性，一般会对 B+树做一些优化。如下图带顺序访问的 B+树：
B+树的插入删除类似于 B-树。
B-树和 B+树的区别
1、B+树内节点不存储数据，所有 data 存储在叶节点导致查询时间复杂度固定为 logn。而 B-树查询时间复杂度不固定，与关键字在树中的位置有关，最好为 O(1)。
如下所示 B-树/B+树查询关键字为 50 的 data。
B-树
关键字为 50 的节点就在第一层，B-树只需要一次磁盘 IO 即可完成查找。
B+树
由于 B+树所有的 data 域都在根节点，所以查询关键字为 50 的节点必须从根节点索引到叶节点，时间复杂度固定为 O(logn)。
2、B+树叶节点两两相连可大大增加区间访问性，可使用在范围查询等，而 B-树每个节点关键字和 data 在一起，则无法区间查找。
根据空间局部性原理：如果一个存储器的某个位置被访问，那么将它附近的位置也会被访问。
B+树可以很好的利用局部性原理，若我们访问节点关键字为 50，则关键字为 55、60、62 的节点将来也可能被访问，我们可以利用磁盘预读原理提前将这些数据读入内存，减少了磁盘 IO 的次数。
当然 B+树也能够很好的完成范围查询。比如查询关键字在 50~70 之间的节点。
3、B+树更适合外部存储。由于内节点无 data 域，每个节点能索引的范围更大更精确。
由于 B-树节点内部每个关键字都带着 data 域，而 B+树节点只存储 key 的副本，真实的关键字和 data 域都在叶子节点存储。前面说过磁盘是分 block 的，一次磁盘 IO 会读取若干个 block，具体和操作系统有关，那么由于磁盘 IO 数据大小是固定的，这就意味着B+树单次磁盘 IO 的信息量大于 B-树，从这点来看 B+树相对 B-树磁盘 IO 次数少。
为什么 MongoDB 索引选择 B-树，而 Mysql（InnoDB 引擎）索引选择 B+树
MongoDB 是文档型的数据库，是一种 NoSQL，一般使用 XML 或 Json 格式来保存数据，归属于聚合型数据库。被设计用在数据模型简单，性能要求高的场合。MongoDB 是聚合型数据库（通常就是键值对），而 B-树恰好关键字和 data 域聚合在一起。
Mysql 是一种关系型数据库，区间访问是常见的一种情况，而 B-树并不支持区间访问，B+树由于数据全部存储在叶子节点，并且通过指针串在一起，这样就很容易的进行区间遍历甚至全部遍历，且每个节点能索引的范围更大更精确。
