（十五）B-Tree树(B-树)与B+树

B-树

B-树是一种平衡的多路查找树。一棵m阶的B-树或者为空树，或者为满足下列特征的m叉树：
（1）树中的每个结点至多有m棵子树；
（2）若根结点不是叶子结点，则至少有两棵子树；
（3）除根结点之外的所有非终端结点至少有不少于m/2棵子树

1. B 树的阶：节点的最多子节点个数。比如 2-3 树的阶是 3，2-3-4 树的阶是 4
2. B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点
3. 关键字集合分布在整颗树中, 即叶子节点和非叶子节点都存放数据.
4. 搜索有可能在非叶子结点结束
5. 其搜索性能等价于在关键字全集内做一次二分查找

B-树的删除

图1

图2

图3

图4

图5

这里以2-3树为例（最少有2个分支，最多有3个分支，相对应的就是一个结点中有1个或者2个元素）
图1到图2删除元素12。当被删除的结点中有2个元素，删除一个元素并不会影响2-3树的结构，直接删除即可。

图2到图3删除元素60。当要删除的结点中只有一个元素值而兄弟结点中有两个元素值的时候，向兄弟结点借。将兄弟结点上移，兄弟对应的双亲结点下移至被删除结点处。

图3到图4删除元素53。当要删除的结点和兄弟结点中都只有一个元素的时候。将该元素删除，将其兄弟与它共同的双亲结点一起合并到兄弟结点中。
如果因此导致不再是2-3树，继续调整。（如图4到图5删除元素37–向上调整。必须保证为此的调整之后仍然是一棵2-3树）。

B-树的插入

每次向叶子结点插入。如果插入之后仍然是2-3树，则保持不动。如果不再是2-3树，向上提拉即可。

#B+树
B+树是 B 树的变体，也是一种多路搜索树

1. B+树的搜索与 B 树也基本相同，区别是 B+树只有达到叶子结点才命中（B 树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找
2. 所有关键字都出现在叶子结点的链表中（即数据只能在叶子节点【也叫稠密索引】），且链表中的关键字(数据)恰好是有序的。
3. 不可能在非叶子结点命中。
4. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层5) 更适合文件索引系统
5. B 树和 B+树各有自己的应用场景，不能说 B+树完全比 B 树好，反之亦然.