data-structures - B-Tree和B+-Tree计算顺序的区别？

Question

我得到了这个简单的问题

Calculate the order p of a B+ tree if B=512, V=9B, Pr=7B and P=6B.

我认为答案是

6p + (p - 1) * 9 < 512

忽略Pr

但是如果改变问题是计算具有相同 B、Pr、P 和 B 值的B-Tree的 order p那么，我认为答案应该是

6p + (p - 1) * (9 + 78) < 512

我对此是否正确？

Answer 1

每个 B 树节点最多可以有 p 个树指针，以及 p-1 个数据指针和 p-1 个搜索关键字字段值。如果所需的 B-Tree 节点必须对应于磁盘块，则这些必须适合单个磁盘块。

计算 p：

6p+(p-1)*(9 + 7) <= 512
6p + 9p + 7p -9 – 7 <= 512
22p – 16 <= 512
22p <= 528
p <= 24

虽然 p 可以最大为 24，但我们选择 p = 23，因为 B 树节点可能包含用于操作树的附加信息，例如节点中的条目数q，以及指向父节点的指针，因此在我们之前计算上面的 p，块大小应该首先减少所需的额外空间量。