如何高效地从给定列表构建B+树？

Question

我想从一个大小为N的无序元素列表构建一个B+树。

我知道最优的方法是使用Θ(N / B * logM / B(N / B))个块传输，这也是排序的最优方法。因此，我不能简单地选择一个项目并逐个插入到树中，因为它会给我带来O(N logB(N))个块传输。

所以我想先对元素进行排序，因为叶子节点已经有序了。但是之后我就不知道该怎么做了。

我考虑了以下步骤：

1. 从列表中取出B个元素 2. 将它们按原样写在某个地方（这是树的叶子） 3. 取出块的最后一个元素（最大值）；它将成为父节点的路由键 4. 重复步骤1，直到父节点中有B-1个路由键 5. 当父节点中有B-1个路由键时，它就满了。所以新的路由键将去“祖父”处（所以树增加了一层），所有新的叶子将有一个新的父节点 6. 继续这样做，直到读取了N/B个块

基本上，这种方法的问题在于我没有考虑一个内部节点可以拥有的最小子节点数。因此，可能会发生一个节点最终只有一个子节点的情况，这显然是错误的。

我到处寻找算法，但我找不到一个真正解释如何在Θ(N / B * logM / B(N / B))中构建树的算法。我发现所有的算法都是针对列表中每个项目进行简单插入到树中，而没有利用B因子。

你能帮我吗，也许指点一下方向？

- Beriol

---

关于第5步，“新的路由键将进入祖父”，实际上不是新键进入祖父，而是旧父亲的中间键。新键将进入新父亲。 - mangusta

你说得对，是我的错误！如果我在内部节点达到B-1个元素时拆分它们，我可以保证树建立时遵守每个节点的最小子节点数。谢谢！ - Beriol

Answer 1

与其同时构建所有级别，这可能会使用超过常量数量的RAM块，我认为最好是从叶子节点到根节点依次构建级别（即广度优先而非深度优先）。给定列表，将其贪心地划分为大小为B的块。如果只有一个块，则这就是根。否则，如果最后一个块的元素太少，则尽可能平衡地重新分配其元素和倒数第二个块的元素；现在两者都有足够的元素。下一个列表由此级别中每个块的最后一个元素组成。

- David Eisenstat

---

第一个块集和下一个块集之间的关系怎么样构建？我猜第一个块集仍然需要在内存中才能完成这个任务。 - mangusta

根据mangusta的建议，我认为可以只使用大小为B的h + 1个块在主内存中完成（其中h是树的高度）；一个块用于从列表中加载B个元素（基本上是叶子），其他h个块（每个级别一个块）用于存储路由键。当h个块之一满时，它会被分裂：前floor((B+1)/2)个元素可以进入外部存储器，因为它们不会再次使用，位置为ceil((B+1)/2)的元素进入与前一级别相关的主内存块中，剩余的元素留在块中。 - Beriol

@Beriol，你的方法需要大量的输入/输出操作，所以我们需要进行一些权衡。 - mangusta

为什么会这样呢？我的意思是，有些 N/B I/O 操作是不可避免的，加上每个节点在树中都需要一个 I/O 操作，也是不可避免的...还是说可以避免？ - Beriol

@Beriol，按照David Eisenstat的建议，一个层级=一次写入，同一层级中的所有块都驻留在同一个列表中，因此同一层级中的所有块都会一次性写入。在您的情况下，您需要为每个块执行写操作。 - mangusta

我对外部存储算法之类的东西还比较陌生，请帮我理解一下。如果每个叶子大小为B，每个内部节点也是B（实际上是B-1），难道我们不需要“付出”B来写入树中的一个节点吗？我的意思是，无论如何我们都必须单独写入每个块（我们不能使用一次写操作写入2个块，只支付B），那么为什么重要的是按顺序一个接一个地写入它们，而不是先写一个，然后过一段时间再写另一个，依此类推？这不像我们一次只写入一个元素，我们仍然一次写入B个元素，这是最大值，不是吗？ - Beriol