B-Tree 简述

度的定义

B-Tree 预定义了一个「树的度(degree )」的范围。当在节点中插入或删除数据时,「节点的度」就会变化,但仅限制在 B-Tree 预定义的范围之内变化。

为了维持预定义的「树的度」的范围,B-Tree 的内部节点可能被合并或分离。因为「节点的度」可以在一定范围内盖改变,所以 B-Tree 可以不像其它「自平衡搜索树」一样,需要经常重新平衡树的内部节点。不过 B-Tree 可能会浪费一些存储空间,因为它的内部节点可能是不满的。

B-Tree 「树的度」的上限和下限,对某一特定的实现来说通常是固定的。例如 2-3 B-Tree 的每一个内部节点的度仅可能只有 2 或 3 个子节点。

节点内部

每个 B-Tree 的内部节点可以包含多个 key,key 用作为分离内部节点的「子树」的分离值。例如,如果一个 B-Tree 的内部节点拥有 3 个子节点(即子树),那么它就有拥有 2 个 key :a1 和 a2。左侧子树中的 key 小于 a1,中部子树中的 key 大于 a1 并小于 a2,右侧子树中的 key 大于 a2。

通常来说,key 的个数会介于 d ~ 2d 之间,d+1 是「树的度」。在实际应用中,key 往往占用了节点的大部分空间。系数 2 可以保证节点被正常分离或组合。当向一个拥有 2d 个 key 的内部节点添加一个 key 时,B-Tree 将会这 2d+1 个 key 分离成 2 节点,并且将处于中间位置的 key 移动至父节点中。至此,每个被分离的节点都拥有最小数量的 key。类似的,当向两个相邻且都拥有 d 个 key 的内部节点删除一个 key 时,B-Tree 则会组合这两个相邻的节点。删除一个 key 会导致内部节点仅有 d-1 个 key。组合两个相邻的节点时,会从其父节点中取出一个 key 与它们组成一个拥有 2d 个 key 的节点。

节点的「子树」个数会比节点的 key 个数多一个。在 2-3 B-Tree 中,内部节点将会存储 1 个或 2 个 key,同时会存储 2 个子树或 3 个子树。一棵 B-Tree 树的上限和下限,有时候会被参数化成 (d + 1) - (2d + 1) ,或者更简单地仅以 (2d + 1) 来描述。

维持平衡

B-Tree 通过要求所有的「叶子节点」都保持相同的深度,来维持树的平衡。「树的深度」会随着元素的添加而缓慢增加,然而 B-Tree 「树的深度」整体性的增加是不常见的,这会导致树中所有的「叶子节点」离「树根」更远了一个节点。

参考资料

最后更新于