algorithm - 顺序构建完整的 B 树

Question

如果我有一组排序的数据，我想以一种最适合顺序读取和随机查找的方式存储在磁盘上，似乎 B 树(或其中一个变体是不错的选择……假设这个数据集不能全部放入 RAM)。

问题是，是否可以在不进行任何页面拆分的情况下从一组已排序的数据构建完整的 B 树？以便排序后的数据可以顺序写入磁盘。

Answer 1

根据这些规范构建“B+ 树”很简单。

1. 选择分支因子 k。
2. 将排序后的数据写入文件。这是叶级别。
3. 要构造下一个最高级别，扫描当前级别并写出每个第 k^th 项。
4. 当当前级别有 k 个项目或更少时停止。

k = 2 的例子:

0 1|2 3|4 5|6 7|8 9
0   2  |4   6  |8
0       4      |8
0               8

现在让我们寻找5。使用二进制搜索在顶层查找小于或等于 5 或 0 的最后一个数字。查看0对应的下一个最低级别的区间:

0       4

现在 4:

        4   6

现在又是4:

        4 5

找到了。一般来说，第 j^th 项对应于下一级的第 jk 到 (j+1)k-1 项。您还可以线性扫描叶级别。