B-tree minimum internal children count 解释

Question

为什么 B 树必须有 ceil(m/2) - 1 的内部子节点数。我已经搜索过了，但没有任何解释。

Answer 1

这不完全正确，正确的是定义的一部分。
Wikipedia

According to Knuth's definition, a B-tree of order m is a tree which satisfies the following properties:

1. Every node has at most m children.
2. Every non-leaf node (except root) has at least ⌈m/2⌉ child nodes.
3. The root has at least two children if it is not a leaf node.
4. A non-leaf node with k children contains k − 1 keys.
5. All leaves appear in the same level and carry no information.

所以不是ceil(m/2)，而是ceil(m/2)...m，而且是不是授予而是实现，这是一个目标。

---

目的是保持最小的存储密度。 “太空”的节点浪费空间。所以从技术上讲，当删除时你可以下降到一个 child ，那将是一个工作树结构(即使链表毕竟仍然是一个有效的图)，只是会浪费很多。

m/2 本身来自节点 split 。当一个完整的节点被分成两部分时，你将有一个 floor(m/2) 和一个 ceil(m/2) 节点(如果 m为偶数，两者相同)，新条目添加到较小的条目。然后两者都变得大于或等于 ceil(m/2)。

• 偶数情况:m=4，m/2=2=ceil(m/2)=floor(m/2)，添加新条目后的结果为2 和 3，都 >=2
• 奇数情况:m=5，ceil(m/2)=3，floor(m/2)=2，后者获得新条目，它们变为 3 和 3，均 >=3。