按顺序构建完整B-树 [英] Sequentially Constructing Full B-Trees

问题描述

如果我有一个排序的数据集，这是我希望在磁盘上存储的方式是最优的顺序读取和做随机查找上，似乎变种B树（或一个是不错的选择... presuming此数据集不全部装入RAM）。

If I have a sorted set of data, which I want to store on disk in a way that is optimal for both reading sequentially and doing random lookups on, it seems that a B-Tree (or one of the variants is a good choice ... presuming this data-set does not all fit in RAM).

现在的问题是可以完整的B树从一个排序的数据集的构建，而不做任何页面拆分？使得排序的数据可以被写入到磁盘顺序

The question is can a full B-Tree be constructed from a sorted set of data without doing any page splits? So that the sorted data can be written to disk sequentially.

推荐答案

构建B +树，以这些规范很简单。

Constructing a "B+ tree" to those specifications is simple.

1. 选择您的分支系数k。
2. 写排序的数据到一个文件中。这是叶级。
3. 要构建一个最高级别，扫描当前水平，并写出每k ^日项目。
4. 停止在当前水平有k个项目或更少。

1. Choose your branching factor k.
2. Write the sorted data to a file. This is the leaf level.
3. To construct the next highest level, scan the current level and write out every k^th item.
4. Stop when the current level has k items or fewer.

例，其中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 ：

Now let's look for 5. Use binary search to find the last number less than or equal to 5 in the top level, or 0. Look at the interval in the next lowest level corresponding to 0:

0       4

现在 4 ：

        4   6

现在 4 又说：

        4 5

发现了它。在一般情况下，第j ^个项对应于物品jk的虽然第（j + 1）k-1个在新的水平。您也可以扫描叶级线性。

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.

这篇关于按顺序构建完整B-树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！