B+树插入顺序
B+ tree insertion order
有没有办法找到B+树的原始插入顺序？
我有这棵树：
{ [ (1 2) 3 (5 6 7) ] 8 [ (9 10) 11 (12 13) 14 (14 16 17) 18 ( 19 20) ] }
Example tree
没有
例如，在您的情况下，最后两个插入内容可能是 7, 17 或 17, 7，并且绝对无法分辨哪个是哪个。确实5, 6, 7三个中的一个插入在另外两个之后，没有记录哪个是哪个。
这一点从鸽巢原理也能马上看出来。首先让我们设置一个上限，其中包含 n 个东西可以有多少 k-way B-trees。
任何 b-tree 和 n 事物的结构都可以编码为节点大小的流。从顶级节点的大小，您可以知道有多少个第二层节点，第二层的第三层节点也是如此。一个节点可以包含 1..k 中的任何地方。节点不能多于元素。因此，我们可以通过首先指定有多少个节点，然后指定节点的大小来指定 B-tree。 （并非所有数字组都是 B-tree。）对于 B-tree 的每个大小 s，都有 k^s <= k^n 个。因此 n k^n 是可以有多少 k-way B-trees 的上限。这是指数级增长。
但是可以插入元素的顺序数是 n!。此函数的增长速度严格快于指数增长，因此您无法从 B-tree.
中恢复顺序
有没有办法找到B+树的原始插入顺序？
我有这棵树：
{ [ (1 2) 3 (5 6 7) ] 8 [ (9 10) 11 (12 13) 14 (14 16 17) 18 ( 19 20) ] }
Example tree
没有
例如，在您的情况下，最后两个插入内容可能是 7, 17 或 17, 7，并且绝对无法分辨哪个是哪个。确实5, 6, 7三个中的一个插入在另外两个之后，没有记录哪个是哪个。
这一点从鸽巢原理也能马上看出来。首先让我们设置一个上限，其中包含 n 个东西可以有多少 k-way B-trees。
任何 b-tree 和 n 事物的结构都可以编码为节点大小的流。从顶级节点的大小，您可以知道有多少个第二层节点，第二层的第三层节点也是如此。一个节点可以包含 1..k 中的任何地方。节点不能多于元素。因此，我们可以通过首先指定有多少个节点，然后指定节点的大小来指定 B-tree。 （并非所有数字组都是 B-tree。）对于 B-tree 的每个大小 s，都有 k^s <= k^n 个。因此 n k^n 是可以有多少 k-way B-trees 的上限。这是指数级增长。
但是可以插入元素的顺序数是 n!。此函数的增长速度严格快于指数增长，因此您无法从 B-tree.