B+树的顺序

Question

查看不同的来源，在我看来，B+树顺序有两种定义。第一个是谈论每个节点的条目数，第二个是谈论子节点（指针）的数量。他们指的是同一个定义吗？或者也许我看不出它们有什么关系。

1. （https://cs186berkeley.net/notes/note4/）

“数字 d 是 B+ 树的阶数。假设没有发生删除，每个节点（根节点除外）必须有 d ≤ x ≤ 2d 个条目（叶节点有可能以 < d entries if you delete data). The entries within each node must be sorted."

结束）

2. （https://www.cs.cornell.edu/courses/cs3110/2012sp/reitations/rec25-B-trees/rec25.html）

“m阶B树是一棵搜索树，其中每个非叶节点最多有m个子节点。集合的实际元素存储在树的叶子中，非叶节点仅包含键。每个叶子存储一定数量的元素；最大数量可能大于或（通常）小于 m。”

Answer 1

首先，请注意，此主题对于 B+ 树和 B 树是相同的。事实上，第二个引用涉及 B 树。但这与术语“顺序”的定义无关。

他们指的是同一个定义吗？或者也许我看不出它们有什么关系。

不，他们使用不同的定义。

维基百科关于

B-tree

的文章有一个段落涵盖了术语上的这种差异：

有关 B 树的文献在术语方面并不统一。

Bayer 和 McCreight (1972)、Comer (1979) 等人将 B 树的阶定义为非根节点中键的最小数量。 Folk 和 Zoellick 指出，术语含糊不清，因为最大键数尚不清楚。 3 阶 B 树最多可容纳 6 个键或最多 7 个键。 Knuth (1998) 通过将顺序定义为子级的最大数量（比最大键数多 1）来避免这个问题。

因此，您提出的第一个引用使用了 Bayer 和 McCreight 的定义（并且意味着最大键数始终为

even

），而第二个引用则使用了 Knuth 的定义。 与你的问题无关，但第一句话中的评论“叶子节点有可能以

结束”假设是“惰性”变体。在该变体中，当从中删除大量内容时，树可能会变得相对低效。通常的过程是在删除后重新平衡树（

从叶节点删除），这可能涉及合并节点。这样在整个树中保持对最小键数的约束。< d entries if you delete data"