共计 936 个字符，预计需要花费 3 分钟才能阅读完成。
B-Tree
B 树中所有结点中孩子结点个数的最大值成为 B 树的阶，通常用 m 表示，从查找效率考虑，一般要求 m >=3。一棵 m 阶 B 树或者是一棵空树，或者是满足以下条件的 m 叉树。
1）每个结点最多有 m 个分支（子树）；而最少分支数要看是否为根结点，如果是根结点且不是叶子结点，则至少要有两个分支，非根非叶结点至少有 ceil(m/2)个分支，这里 ceil 代表向上取整。
2）如果一个结点有 n - 1 个关键字，那么该结点有 n 个分支。这 n - 1 个关键字按照递增顺序排列。
3）每个结点的结构为：
n
k1
k2
…
kn
p0
p1
p2
…
pn
其中，n 为该结点中关键字的个数；ki 为该结点的关键字且满足 ki<ki+1；pi 为该结点的孩子结点指针且满足 pi 所指结点上的关键字大于 ki 且小于 ki+1，p0 所指结点上的关键字小于 k1，pn 所指结点上的关键字大于 kn。
4）结点内各关键字互不相等且按从小到大排列。
5）叶子结点处于同一层；可以用空指针表示，是查找失败到达的位置。
B+ Tree
B+ 树是 B 树的变体，也是一种多路搜索树，定义基本与 B 树同，除了：
1. 非叶子结点的子树指针与关键字个数相同；
2. 非叶子结点的子树指针 P[i]，指向关键字值属于 [K[i], K[i+1]) 的子树（B 树是开区间）；
3. 为所有叶子结点增加一个链指针；
4. 所有关键字都在叶子结点出现；
为什么说 B + 树比 B 树更适合数据库索引
1、B+ 树的磁盘读写代价更低：B+ 树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对 B 树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对 IO 读写次数就降低了。
2、B+ 树的查询效率更加稳定：由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
3、由于 B + 树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是 B 树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以 B + 树更加适合在区间查询的情况，所以通常 B + 树用于数据库索引。
