B Tree
B树呢，又叫平衡多路查找树。如果每个节点最多有m个孩子，那么这样的树就是m阶B树。咱们可以看到，该图就是一个三阶B树的样子
特征：
- 根节点至少包括两个孩子.
- 树中的每个节点最多含有m个孩子(m>=2)
- 除了根节点和叶节点外，其他每个节点至少有Math.ceil(m/2)个孩子，即对m/2向上取整，例如m为3的话就取2。 除了满足第3点外，还要非根非叶节点至少有两个孩子.
- 所有叶子节点都位于同一层，叶子节点的高度都是一样的.
- 假设每个非叶子节点中包含了n个关键字信息(就是上面的图的蓝色部分)，其中:
- Ki(i=1…n)为关键字，且关键字按顺序升序排序，即K(i-1) <Ki.
- 关键字的个数n必须满足: [ceil(m/2)-1]<=n<=m-1，即关键字的个数永远比阶数少至少一个
- 非叶子节点的指针:P[1]，P[2]，…P[M];其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[I]指向关键字属于(K[I-1]，K[i])的子树，即对比上面的图来说，指向的左子树永远小于等于左边的关键字，指向的右子树永远大于等于右边的关键字，中间的子树位于左右两个关键字之间
B树相比二叉搜索树的优势：
- B树的特征限定了其不会变成线性的情况
- 比二叉搜索树更矮，IO次数更少，搜索速度更快
B树的前四条规则呢，主要是用于用来限定B树的孩子数，每个节点的孩子数，还有B树的深度。 而它的第五条规则呢，则是用来限定B树节点关键字数量，以及大小的。
当我们要查询数据的时候呢，B树的查找效率，和二叉查找树是一样高效的，也是O(logN) 当数据发生变动的时候，必然会存在现有结构被打乱的情况。我们的这个二叉查找树就有可能被打乱成线性的。
而由于我们的B树有这五个规定存在。B树就会有相应的策略，通过合并，分裂，上移下移节点，来保持它的特征。使B树远比二叉树矮的多。并且不会有 经过数据不断变动后，变成线性的情况。
用B树去做索引，是一个不错的选择。但是，还有没有更好的替代品？那便是我们的B+ Tree
B+ Tree
特征：
B+树呢是B树的变体，其定义呢基本与B树相同，除了：
- 其非叶子节点的子树指针与关键字个数相同.（表明了B+树能存储更多的关键字）
- 其非叶子节点的子树指针P[i]，指向关键字值范围为[K[i]，K[i+1]）这个左闭右开区间的子树.
- 非叶子节点仅用来做关键字的索引，数据都保存在叶子节点中.所以B+Tree的检索都是从根节点开始，叶子节点结束. （叶子节点才存储我们需要用到的数据，有的可能是指向数据文件的指针。有的有可能是主键的值，或者有的就干脆就把相关的关键数据存储到这个节点上面了）
- 所有叶子节点均有一个类似于链表指针的结构指向下一个叶子节点并按照大小顺序连接， 例如P1叶子节点中的5->8->9，P2叶子节点中的10->15->18.
总之数据都是存储在叶子节点当中的，这也就表明了B+树所有的检索都是从根部检索，到叶子节点才结束，同时非叶子节点只用来存储索引。非叶子节点不存储数据的话，就又能存储更多的关键字了，那也就使得我们的B+树相比B树更矮。
之所以B+树的非叶子节点只存储索引，叶子节点存储数据的原因是：在数据库中页的大小是固定的，InnoDB 中页的默认大小是 16KB。如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点数）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的 IO 次数又会再次减少，数据查询的效率也会更快。另外，B+ 树的阶数是等于键值的数量的，如果我们的 B+ 树一个节点可以存储 1000 个键值，那么 3 层 B+ 树可以存储 1000×1000×1000=10 亿个数据。一般根节点是常驻内存的，所以一般我们查找 10 亿数据，只需要 2 次磁盘 IO。
B+树相比B树的优势：
经过上面的分析，咱们得出了一个结论，B+树相比B树还有其它树来说，在文件系统及数据库系统当中，更有优势，原因如下：
B+Tree的磁盘读写代价更低，因为B+Tree的非叶子节点只存放索引的信息，而不存放数据（因此其内部节点相比B树会更小），所以可以指向更多的数据，（即同一盘块中所能容纳的关键字就更多）可以一次性读取更多的要查找的关键字到内存中，因此相对来说IO的次数，也就降低了
B+Tree的查询效率更加稳定.因为其非叶子节点不是指向文件内容的节点，只是叶子节点中才有关键字的索引，所以任何数据的查找都是从根节点到叶子节点，所有数据的查询长度都是一样的，自然效率也一样，这就稳定了嘛，基本保持在O(logN).
B+Tree更利于对数据库的扫描，可以直接只在叶子节点里根据链表指针做扫描，不用每次都遍历整棵树。(B树在提高了磁盘IO性能的同时呢，并没有解决元素遍历的效率低下的问题，而B+树，只需要遍历叶子节点就可以解决对全部关键字信息的扫描。所以，对于数据库中频繁使用的范围查询，比如说查找大于等于10的部分，我们就可以先从上到下定位到10，然后再顺着叶子节点的连接指针去做范围查询）也就表明了B+树在做范围查询时，有着更高的性能。这些也是为什么我们选择B+树来作为主流索引数据结构的原因
