algorithm - 顺序构建完整的 B 树

Question

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

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

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 在下一级。您还可以线性扫描叶级别。

Answer 2

我们可以一次完成 B 树，但它可能不是最优的存储方法。根据您进行顺序查询与随机访问查询的频率，最好按顺序存储它并使用二进制搜索来服务随机访问查询。

也就是说：假设您的 b-tree 中的每条记录都包含(m - 1) 个键（m > 2，二进制情况有点不同）。我们希望同一级别的所有叶子和所有内部节点至少具有(m - 1) / 2 个键。我们知道高度为k的完整 b-tree具有(m^k - 1) 个键。假设我们总共有n 个键要存储。令k为满足m^k - 1 > n的最小整数。现在如果2 m^(k - 1) - 1 < n我们可以完全填满内部节点，并将其余的键均匀地分配给叶节点，每个叶节点获得(n + 1 ) 的下限或上限- m^(k - 1))/m^(k - 1)键。如果我们不能这样做，那么我们知道我们有足够的空间来填充深度k - 1处的所有节点至少一半，并在每个叶子中存储一个密钥。

一旦我们确定了树的形状，我们只需要对树进行中序遍历，然后将键依次放置到位。

Answer 3

最优意味着数据的中序遍历将始终通过文件（或映射区域）向前搜索，并且以最少的搜索次数完成随机查找。