c++ - B-Tree中是否有批量加载的算法？

Question

我知道 b+tree 中有批量加载。我只是想知道在 B-Tree 中是否有任何用于批量加载的算法。例如，给定一个数据数组，创建 B-Tree 的最佳方法是什么？

Answer 1

其实答案是肯定的。

B+-trees 和普通 B-trees 的主要区别在于前者的值实际上存储在叶子中，而在后者中，您将在每个节点中找到值。因此，B+-树让您以几乎连续的方式存储数据，每个叶子包含整个排序数据的连续切片。这对于 B 树来说是不可能的：一个内部节点将包含几个元素，但它们不会是连续的。整个排序的数据集。

此属性对于批量加载至关重要：该过程通过将已排序的数据集切割成将形成 B+-tree 叶子的数组来处理已排序的数据集。因此，对于 B 树来说，它似乎无法工作。

如果我们能够以将内部节点元素组合在一起的方式对数据进行排序，那么问题就解决了。为了做到这一点，必须事先知道元素将如何分组。事实证明这是可能的。

让我们调用o（排序）节点中的最小子节点数（这与 B 树顺序的原始定义一致）。我们认为根节点处于树的最高阶段，叶子处于最低阶段（阶段 0）。对于一棵平衡良好的树，所有的叶子确实会处于同一阶段。

树的第 k 级对至少由o第 k-1 级中的元素隔开的元素进行分组。在初始排序之后，我们必须从构成阶段 0 的已排序数组中提取元素，并将它们分组到不同的数组中以构建阶段 1，然后再次使用该数组到阶段 2 的新数组中，并重复该过程直到最新数组中的元素少于o，这将是根阶段。从那时起，可以直接从舞台集构建树：

• 将每个阶段拆分为 o元素数组，
• 构建索引数组以将节点链接到子节点
• 将每个节点构建为一对对应的索引数组 * 值数组

生成的树不一定会很好地平衡。它取决于数据集中的条目数，以及o. 不过，应该可以调整用于构建阶段的间隔以拥有更好的分布式树。

总而言之，批量加载 B-tree 所需的工作比 B+-tree 更乏味，但这是可能的。