B-Tree
# 什么是B-Tree
B-Tree,即B树,与平衡二叉树不同的地方是B树为多路查找树。
# 性质(M阶)
- 每个节点最多有M个子节点。
- 每个非叶子节点(根节点除外)至少包含M/2个子节点。
- 如果根节点不是叶子节点,那么根节点至少有两个子节点。
- 每个节点上,所有的关键字都是有序的,从左到右,依次从小到大排序。
- 每个关键字的左子树的均值小于当前关键字,右子树均值大于当前关键字。
- 每个节点都存有索引和数据。
- 对于一个非叶子节点而言,它最多存储M-1个关键字。
- 所有叶子子节点位于同一层。
B-树的搜索,从根节点开始,对节点内的关键字序列进行二分查找,如果命中则结束,否则进入查找关键字所属范围的子节点;重复上述步骤,直到所对应的子节点为空或者已经是叶子节点。
# 新增
在新增之前,要确定每个节点中关键字个数的范围,如果B-树的为M阶,则节点关键字个数的范围是Ceil(M/2)-1 ~ M-1 个。
对于关键字的新增,首先要进行位置查找,在B-树的查找过程中遇到空指针时,则证明查找不成功,同时也意味着找到了插入位置,即根据空指针可以确定在最底层非叶节点中的插入位置(终端结点);在插入过程中如果节点的关键字范围个数超出规定的个数,这是我们就需要对节点进行拆分。
# 过程:
以{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}关键字序列为例
- 确定节点中关键字的个数范围。
- 根据关键字个数规定以及从左到右依次从小到大的排序性质将关键字插入到节点内。
- 当插入的关键字个数超出规定个数时,从节点中去除中间位置的关键字,作为独立节点,将独立节点左右的关键字分辨作为独立节点的子节点。
- 继续插入关键字,此时关键字总是插入到叶子节点上。
- 继续插入过程中,子节点会的关键字个数会超出规定范围,继续拆分叶子节点,将此时叶子节点的中间关键字纳入到父节点中,并将中间关键字两侧的关键字作为作为两个新的叶子节点连接到父节点上。
- 继续以上操作,直到父节点的关键字个数超出规定个数或叶子节点的个数超出规定个数,对父节点进行重新拆分。
# 删除
B-树中关键字的的删除过程也会对B-树的特性进行破坏,如关键字删除时,可能节点中的关键字个数少于规定个数,这种情况下需要向兄弟节点或子节点借关键字,也有可能需要进行节点合并。 以上面的B-树为例,删除8、16、15、4这些关键字
- 8关键字在叶子节点上,删除后叶子节点数满足B-树的特性,可以直接删除。
- 16关键字删除后,破坏了B-树的特性,需要借关键字来维持原有的树的结构,此时向左节点借关键字会破坏原有结构、只能向右子节点借17来维持原有的结构。
- 15关键字删除,会破坏原有结构,这时需要向兄弟节点借关键字,由于15位于右叶子节点,只能向右借,18关键字大于17关键字,不能直接将18关键字移动到左叶子节点,只能将17关键字移动至该节点,将18关键字替换原17关键字的位置,此时,满足B-树的性质。
- 4关键字删除,由于节点的关键字已到下限,需要向兄弟节点借关键字,但此时兄弟节点的关键字也处于下限,这种情况下需要合并节点来满足B-树的性质。 此时会出现: 即出现了非根节点的双分支节点,需要继续合并,合并后如下:
上次更新: 2023/05/09, 17:54:37