B 树（B- 树）

概念

关于 B 树 和 B+ 树

B 树是一棵 多路平衡查找树。其定义为（一般用 m 表示 B 树 的阶数）：

  • 每个节点最多有 m-1 个关键字
  • 根节点最少可以只有 1 个关键字
  • 非根节点至少有 m/2 个关键字
  • 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的关键字都小于它，每个关键字的右子树中的关键字都大于它
  • 所有叶子节点都位于同一层

B 树的插入

判断当前节点 key 的个数是否小于等于 m-1，如果满足，直接插入到当前节点，如果不满足，根据节点中间的 key 将这个节点一分为二，中间的节点放到父节点中。若父节点 key 的数量也超出范围，向上继续分割，直至满足要求。

B 树的删除

  • 若删除的 key 位于叶子节点且删除后当前节点 key 的个数仍满足要求，直接删除即可。
  • 对于非叶子节点的删除，需要使用后继 key 覆盖要删除的 key，然后删除后继 key，并按照如下规则进行调整使得 节点 key 数量符合范围：
    • 后继 key 所在的节点为叶子节点，若删除后节点 key 数量小于 m/2，且其兄弟节点 key 数量大于 m/2。将父节点 key 移动到该节点，然后将兄弟节点的 key 移动到父节点。