algorithm - 如何从给定的列表中有效地构建 B+ 树？

Question

我想根据给定的大小为 N 的无序元素列表构建 B+ 树。

我知道这样做的最佳界限是 Θ(N/B * logM/B(N/B)) block 传输，这也是排序的最佳界限；所以我不能简单地选择一个项目并单独在树中插入，因为它会给我 O(N logB(N)) block 传输。

所以我认为构建树的最佳方法是首先对元素进行排序，因为叶子无论如何都是有序的。由此，我不知所措。

我想过这样的事情:

1. 从列表中取出B个元素
2. 写下它们在某处的位置(这是三者中的一片叶子)
3. 取 block 的最后一个元素(最大的)；它将是叶子父节点的路由键
4. 对下一个元素重复步骤 1，直到父级中有 B-1 个路由键
5. 当父级中有B-1 路由键时，表示它已满。所以新的路由键将改为“祖父”(因此树生长一层)，所有新叶子将有一个新的父
6. 继续这样直到N/B block 被读取

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

我到处寻找，但找不到实际上解释如何在Θ(N/B * logM/B(N/B))。我找到的所有算法都是将列表中的每个项目简单地插入到树中，而没有利用 B 因子。

你能帮帮我吗，也许能给我指明正确的方向？

Answer 1

与其同时构建所有级别，这可能会使用超过固定数量的 RAM block ，我认为我会构建从最叶到最根的级别(即广度优先而不是深度优先).给定列表，将其贪婪地切成大小为 B 的 block 。如果只有一个 block ，那么这就是根。否则，如果最后一个 block 的元素太少，则尽可能均匀地重新平衡其元素与倒数第二个 block 的元素；两者现在都有足够的元素。下一个列表由该级别每个 block 中的最后一个元素组成。