如图所示这是一棵5阶B树。B树的根节点数量要>2
image.png

生成一颗B树

用以下数字生成一颗b树
image.png

image.png

  • 超过了最大的阶数，以阶数/2向上取整来拆分b树

image.png

  • 继续插入新节点

image.png

  • 超过了最大的阶数，以阶数/2向上取整来拆分b树

image.png

  • 继续插入

image.png

  • 超过了最大的阶数，以阶数/2向上取整来拆分b树

image.png

  • 继续插入

image.png

  • 超过了最大的阶数，以阶数/2向上取整来拆分b树

image.png

  • 继续插入

image.png

  • 超过了最大的阶数，以阶数/2向上取整来拆分b树

image.png

  • 超过了最大的阶数，以阶数/2向上取整来拆分b树

image.png

  • b树构建完成

删除B树的节点

  1. 如果是叶子节点且节点数＞2，直接删除。
  2. 如果不是则用右子树的最小节点或者左子树的最大节点来代替，举个例子，例如要删除上面b数16节点，可以把16换成左子树最大节点15或者右子树最小节点17。但是用15来替换会导致15这颗子树的节点数＜2，所以只能用17来替换。

B+树

下图就是一个B+树，所有的数全部在叶子节点中。
image.png