algorithm - 有没有办法评估 B+ 树所需的叶子数量？

Question

如果我有 t = #tuples(或#records)并且我唯一可以利用的其他信息是我的 B+ 树的扇出 F，有没有办法获得多少叶子(叶子的#blocks)树将需要？假设树必须是平衡的，因此尽可能在最少的空间中保留最多的信息。

示例:t = 40K, F = 40 ==> depth = log_40(40K) = 3 , #leaves = ???

Answer 1

在 B+ tree 中实际记录是从树叶中引用的。另一方面，内部节点不直接引用记录，而是定义键值的范围，以便遍历树到达最终具有感兴趣记录的键值的叶( block )。

B+ 树的另一个特性是内部节点的子节点数不仅有上限(即扇出 F)，还有下限:F/2。 (我忽略了根不受此下限规则的约束)。这个1/2系数就是填充因子(0.5)。

叶 block 的数量 (L) 受记录数量 (t) 和扇出 (F) 的约束，但顺便说一下，树是(不)平衡的。在最好的、最小的情况下，我们有:

min(L) = ⌈ t/F⌉

在最坏的情况下，我们有:

max(L) = ⌈ 2t/F⌉

如果你有不同的填充因子(c>= 0.5)，那么最坏的情况是:

max(L) = ⌈ t/cF⌉

请注意，增加填充因子会减少已用空间，但会增加插入记录时的时间开销。当填充因子接近 1 时，空间使用率保持在最低限度，但更新速度会很慢。