algorithm - 为什么在 B-tree 和 B+_tree 中在每个非叶节点中从半满存储到全满

Question

我刚刚在 DBMS 中学习了 B-tree 和 B+-tree。我不明白为什么树中的非叶节点具有 [n/2] 和 n 个子节点，当 n 对特定树是固定的时。

这是为什么？和优势？

谢谢 ！

Answer 1

这是使 B+ 和 B-tree 平衡的特性，因此，我们可以轻松计算树上操作的复杂度并将其绑定到 O(logn) [其中 n 是数据集中的元素数]。

• 如果一个节点可以有 B 个以上的儿子，我们可以创建一个深度为 2 的树：一个根，所有其他节点将是来自根的叶子。搜索元素将是 O(n)，而不是所需的 O(logn)。
• 如果一个节点的子节点少于 B/2，我们可以创建一个实际上是链表的树 [n 个节点，每个节点有 1 个子节点]，高度为 n - 并且搜索操作将再次是 O(n) 而不是O（登录）

小修正：每个非叶节点 - 除了根，都有 B/2 到 B 个子节点。仅根允许有少于 B/2 个儿子。

Answer 2

The basic assumption of this structure is to have a fixed block size, this is why each internal block has n slots for indexing its children.

When there is a need to add a child to a block that is full (has exactly n children), the block is split into two blocks, which then replace the original block in its parent's index. The number of children in each of the two blocks is obviously n div 2 (assuming n is even). This is what the lower limit comes from.

If the parent is full, the operation repeats, potentially up to the root itself.

The split operation and allowing for n/2-filled blocks allows for most of the insertions/deletions to only cause local changes instead of re-balancing huge parts of the tree.