（面试）B Tree和B+Tree的性质和区别

B Tree 指的是 Balance Tree，也就是平衡树。平衡树是一颗查找树，并且所有叶子节点位于同一层。 B+ Tree 是基于 B Tree 和叶子节点顺序访问指针进行实现，它具有 B Tree 的平衡性，并且通过顺序访问指针来提高 区间查询的性能。
B Tree的性质：
一棵m阶的B Tree有如下特性：
1.每个节点最多有m个孩子
2.除了根节点和叶子节点外，其余节点至少有ceil（m/2）个孩子。
3.若根节点不是叶子节点则至少有两个孩子。
4.所有叶子节点都在同一层，且不包含其他关键字。
5.每个非叶子节点都包含n个关键字信息（P0,P1,…Pn, k1,…kn）
5.1. 关键字的个数n满足：ceil(m/2)-1 <= n <= m-1
5.2. ki(i=1,…n)为关键字，且关键字升序排序。
5.3. Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)

B+Tree相对于B-Tree有几点不同：
1.B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构（链指针）关键字的大小自小而大顺序链接。对于范围查找来说，b+树只需遍历叶子节点链表即可，b树却需要重复地中序遍历。 优势。
2.数据记录都存放在叶子节点中，非叶子节点只存储键值信息，也就是B+树中，内部节点仅仅起到索引的作用。优势（能存更多的键值，因为没有数据）。
3.内部节点中，关键字的个数与其子树的个数相同，不像 B树中，子树的个数总比关键字个数多1个

4。b+树查询必须查找到叶子节点，b树只要匹配到即可不用管元素位置，因此b+树查找更稳定。优势。