本文最后更新于 2022年07月18日 已经是 433天前了 ,文章可能具有时效性,若有错误或已失效,请在下方留言。
B树
一颗m阶的B树定义如下:
- 每个结点最多有m-1个关键字。
- 根结点最少可以只有1个关键字。
- 非根结点至少有Math.ceil(m/2)-1个关键字。
- 每个结点中的关键字都按照从小到大的顺序排列,每个关键字的左子树中的所有关键字都小于它,而右子树中的所有关键字都大于它。
- 所有叶子结点都位于同一层,或者说根结点到每个叶子结点的长度都相同。
B树插入
此处以4阶B树为例:
空树插入38
插入21,40后
继续插入 96,因为超过了最大允许的关键字个数 3,所以以关键字值为40为中心进行分裂
继续插入20,39
当达到下面情况时
我们需要分裂父节点
B树删除