依次构建完整的 B 树

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

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

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

1. 选择分支因子 k。
2. 将排序后的数据写入文件。这是叶子级别。
3. To construct the next highest level, scan the current level and write out every k^th item.
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

Now 4:

        4   6

Now 4 again:

        4 5

Found it. In general, the j^th item corresponds to items jk though (j+1)k-1 at the next level. You can also scan the leaf level linearly.