B+树插入顺序

Question

有没有可能找到B+树的原始插入顺序？

我有一棵树：

{ (1 2) 3 (5 6 7) 8 (9 10) 11 (12 13) 14 (14 16 17) 18 ( 19 20) }

Example tree

Answer 1

不是的。

例如，在您的示例中，最后两个插入可能是7, 17或17, 7，并且绝对无法区分哪个是哪个。事实上，在5, 6, 7中，三个中的一个插入在其他两个之后，没有记录哪一个是哪一个。

这也可以立即从鸽子洞原理中看出。首先，让我们设置一个上限，说明可以有多少个k-way B-tree中包含n内容。

任何具有n内容的b-tree的结构都可以编码为节点大小的流。从顶层节点的大小，您可以知道有多少第二层节点，第二层中的第三层也是如此。一个节点中可以有来自1..k的任何东西。节点不能多于元素。因此，我们可以通过首先指定有多少个节点，然后指定节点的大小来指定B树。(并不是所有的数字集都是B树。)对于B- s的每一种大小，都有它们的k^s <= k^n。因此，n k^n是可以有多少个k-way B树的上限。这是指数级的增长。

但是插入元素的顺序数是n!。此函数的增长速度严格快于指数增长，因此您无法从B树恢复顺序。