文章来源：s默心的编程开发笔记
B树
B 树又叫平衡多路查找树，如果每个节点最多有 m个孩子，那么这样的树就是 m阶 B 树。
上图是一个3阶 B 树的，当然现实中，索引每个节点的孩子数上限，肯定是远大于3的。每个存储块中主要包含了关键字和指向孩子的指针，最多能有几个孩子取决于每个存储块的容量以及数据库的相关配置。通常情况下，这个 m是很大的
B 树的特征
根节点至少包括两个孩子
树中每个节点最多含有 m个孩子（m>=2）
这个就是咱们说的 m阶树的含义了，m取决于节点的容量以及相关配置。
除根节点和叶节点外，其他每个节点至少有ceil(m/2)个孩子，每个非根非叶子节点至少具备两个孩子
其中这个 ceil 这个函数表示取上限。比如 m为3，m/2=1.5，那我们取它的上限，就是2，它并不是四舍五入，比如说等于1.2，它取上限也是2。
所有叶子节点，都位于同一层，叶子节点的高度都是一样的
假设每个非终端节点中包含有n个关键字信息，其中
a)，Ki(i=1...n)为关键字，且关键字按顺序升序排序，K(i-1)<Ki
b)，关键字的个数n必须满足：[ceil(m/2)-1] <= n <=m-1
c)，非叶子节点的指针：P[1],P[2],...,P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1],K[i])的子树。
可以看一下上图所示的3阶B树，通过这个树来检查和理解一下上述这几个特征
可以看到 B 树的前4条规则，主要是用来限定 B 树的孩子数的，每个节点的孩子数和 B 树的深度的。而它的最后一条规定，则是用来限定 B 树节点关键字数量以及大小的。当我们要查找数据的时候，这个 B 树，它跟二叉查找树的查询效率是一样高效的。它的这个查找效率，同样是O(logn)。
当数据发生变动的时候，必然会存在现有结构被打乱的情况。二叉查找树，它就会有可能被打乱成线性的。由于 B 树有这5个规定存在，所以，b 树就会有相应的策略，通过这个合并分裂上移下移节点，来保持它的这个特征，使B树的高度远比我们的二叉树矮得多。并且不会经过数据不断变动后变成线性的这种情况。由于我们重点关注索引，所以具体的这些策略，以及它的实现，大家有时间可以去了解一下，面试的时候，这类数据结构的实现有时候也会作为面试官的利器来考大家。
B+树
B+树是B树的变体，其定义基本与B树相同，除了以下几个特点：
非叶子节点的子树指针与关键字个数相同
此特点表明B+树相对于B树能存储更多的关键字
非叶子节点的子树指针P[i]，指向关键字值[K[i],K[i+1])的子树
非叶子节点仅用来做索引，数据都保存在叶子节点中
B +树所有的检索都是从根部开始检索到叶子节点才能结束。同时非叶子节点仅用来存储索引，非叶子节点不存储数据，又能存储更多的关键字。也就使得我们的 B+ 树相对于 B 树来说更矮。B 树的搜索，可以在任意一个非叶子节点就终结掉，也就是它可能把数据文件存储到非叶子节点上
所有的叶子节点均有一个链指针指向下一个叶子节点，并按大小顺序链接
大家可以看到 B+ 树的叶子节点，都是按照大小顺序来做排列的，大家可以看到5，8，9，然后再到10，15，18都是按照这个大小顺序来排列的，叶子节点链接起来，能够方便我们直接在叶子节点做范围统计，就比如说我们要搜索大于或者等于10的这些数据，我们定位到存储10的这一个叶子节点之后，它就会直接从这里往后统计，也就是说它支持范围统计，例如这里的大于等于10。也就是说一旦定位到某个叶子节点呢，便可以从该叶子节点开始横向的去跨子树去做统计。
通过对比二叉查找树、平衡二叉树、B树和B+树，很明显，B+树更适合用来做存储索引，理由如下：
B+树的磁盘读写代价更低
B+ 树的内部结构并没有指向关键字具体信息的指针，也就是不存放我们的数据，只存放索引信息，因此其内部节点相对 B 树更小。如果把所有同一内部节点的关键字存放在同一盘块中，这个盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说，io 读写次数也就降低了。
B+树的查询效率更加稳定
由于内部节点并不是最终指向文件内容的节点，而只是叶子节点中关键字的索引。所以，任何关键字的查找必须走一条从根节点到叶子节点的路。所有关键字查询的长度相同，导致每一个数据的查询效率也几乎是相同的，稳定的O(logn)。
B+树更有利于对数据库的扫描
B 树在提高了磁盘 io 性能的同时，并没有解决元素遍历的效率低下的问题，而 B+ 树只需要遍历叶子节点，就可以解决对全部关键字信息的扫描。所以对于数据库中频繁使用的范围查询，以上图B+树为例，要查询大于或者等于10的数据。由于它的每个叶子都是用指针来连接起来的，我们就可以从这个10开始顺着它的指针直接在叶子里面去做范围查询，这样是非常方便的，也就表明了 B 加树在做范围查询时有着更高的性能，这也是为什么我们在数据库选择 B+ 树作为主流索引数据结构的原因。
