概念
B-树可以理解为平衡二叉树的拓展, 它也是平衡的, 但是每个节点可以有多个关键字. ‘B’ 后面的 ‘-‘ 不是减号.
下面是一棵 B-树的例子:
B-树的存储结构
其中, n 为当前结点关键字个数, text{p}_i 是指向孩子结点的指针.
性质
对于 m 阶 B-树:
注意: 严格来讲, B-树的阶数不是指含有最多关键字结点的度数.
有争议的问题: B-树的高度是否应该包含失败结点? 此处认为是不包括的.
常用操作
查找
当关键字数不是很多的时候, 可以使用顺序查找, 否则可使用二分查找.
插入(以 5 阶 B-树为例)
删除(以 5 阶 B-树为例)
- 直接删除, 位于终端, 且删除后该结点的关键字数仍然大于等于 lceil m/2 rceil
- 非终端结点:用左子树最大关键字或者右子树最小关键字取代. 选择关键字数大于 lceil m/2 rceil 的子结点进行取代.
- 当删除后关键字数小于 lceil m/2 rceil , 父结点关键码下移, 兄弟结点关键码上移, 上移关键码位置的子树指针移动到被删关键码位置
- 若该结点和左右兄弟关键字数都达到下限, 此时合并. 原则上选择较少关键字数目的结点进行合并.
