B 树上的最小/最大记录数？

Question

我正在寻找最好的& B+Tree 的最坏情况 (http://en.wikipedia.org/wiki/ B-tree#Best_case_and_worst_case_heights），但我不知道如何根据我所掌握的信息使用这个公式。 假设我有一个包含 1,000 条记录的树 B，B 可以拥有的最大（和最大）级别数是多少？ 我可以在每一页上有尽可能多/小的按键。我也可以有尽可能多/少量的页面。 有什么想法吗？ （如果你想知道，这不是一个家庭作业问题，但它肯定会帮助我理解硬件的一些东西。）

Answer 1

我没有方便的数学知识，但是......

基本上，树深度的主要因素是树中每个节点的“扇出”。

通常，在简单的 B 树中，扇出为 2，树中每个节点有 2 个节点作为子节点。

但对于 B+Tree，它们的扇形通常要大得多。

起作用的因素之一是磁盘上节点的大小。

例如，如果您有 4K 页面大小，并且有 4000 字节的可用空间（不包括与该节点相关的任何其他指针或其他元数据），并且假设指向树中任何其他节点的指针是4 字节整数。如果您的 B+Tree 实际上存储 4 字节整数，则组合大小（4 字节指针信息 + 4 字节键信息）= 8 字节。 4000 个可用字节 / 8 个字节 == 500 个可能的子级。

对于这个人为的案例，你的粉丝满分是 500 分。

因此，使用一页索引（即根节点）或高度为 1 的树，可以引用 500 条记录。添加另一个级别，您的分辨率为 500*500，因此对于 501 个 4K 页面，您可以引用 250,000 行。

显然，密钥大小越大，或者节点的页面大小越小，树的扇出能力就越低。如果每个节点中允许可变长度密钥，那么扇出很容易发生变化。

但希望您能明白这一切是如何运作的要点。

Answer 2

这取决于树的数量。您必须定义该值。如果你说每个节点可以有 4 个子节点，并且有 1000 条记录，那么高度为

最佳情况 log_4(1000) = 5

最坏情况 log_{4/2}(1000) = 10

数量为 m，记录是n。

Answer 3

最好和最坏的情况取决于否。每个节点可以拥有的子节点数。对于最好的情况，我们考虑这样的情况：每个节点具有最大数量的子节点（即 m 表示 m 叉树），每个节点具有 m-1 个键。所以，

第一层（或根）有 m-1 个条目
第二层有 m*(m-1) 个条目（因为根有 m 个子项，每个子项有 m-1 个键）
第三级有 m^2*(m-1) 个条目
....
第 H 层有 m^(h-1)*(m-1)

因此，如果 H 是树的高度，则条目总数等于 n=m^H-1
相当于 H=log_m(n+1)

因此，在您的情况下，如果您有 n=1000 条记录，每个节点有 m 个子节点（m 应该是奇数），那么最佳情况高度将等于 log_m(1000 +1)

同样，对于最坏的情况：

1 级（根）至少有 1 个条目（且至少有 2 个子条目）
第二级至少有 2*(d-1) 个条目（其中 d=ceil(m/2) 是每个内部节点（根除外）可以拥有的最小子节点数）
第三级有 2d*(d-1) 个条目
...
第 H 层有 2*d^(h-2)*(d-1) 个条目

因此，如果 H 是树的高度，则条目总数等于 n=2*d^H-1 ，相当于H=log_d((n+1)/2+1)

因此，在您的情况下，如果您有 n=1000 条记录，每个节点有 m 个子节点（m 应该是奇数），那么最坏情况的高度将等于log_d((1000+1)/2+1)