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 「树的深度」整体性的增加是不常见的，这会导致树中所有的「叶子节点」离「树根」更远了一个节点。