B树及B+树

一、B树

B 树是一种多路查找平衡树，其命名来自英语称谓 Balance Tree，也就是平衡树的意思。

一棵 M 阶 B 树的定义为：

1. 树中每个结点最多含有 M 棵子树，M-1 个值。
2. 若根结点不是叶子结点，则至少有2棵子树。
3. 除根结点之外的所有非叶子结点至少有 [m/2]（向下取整） 棵子树。
4. 每个结点包含的值，值是从小到大排序，子树的大小们也都是介于这些值之间。

可以参考 2-3 树或 2-3-4 树，红黑树章节介绍的 2-3 树和 2-3-4 树都是 B 树，一个是3阶，一个是4阶。