一、B树

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

一棵 MB 树的定义为:

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

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