如何从给定列表有效地构造B +树？

Question

我想从给定大小的无序元素列表中构建B +树N.

我知道这样做的最佳界限是?(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因子.

你能帮助我吗,也许能指出我正确的方向？

Answer 1

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