algorithm - 顺序构建完整的 B 树

Question

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

问题是可以从一组排序的数据构建完整的 B 树而不进行任何页面拆分吗？以便将排序后的数据按顺序写入磁盘。

Answer 1

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

1. 选择分支因子 k。
2. 将排序后的数据写入文件。这是叶子级别。
3. 要构建下一个最高级别，请扫描当前级别并写出每第 k 项。
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 项对应于下一级的项 jk 至 (j+1)k-1。您还可以线性扫描叶子水平。