algorithm - 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 树可以与 n里面的东西。

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

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