2

我已经建立了自己的 b+tree 索引,其中包含插入/删除/搜索索引的所有操作。为了加速大型数据集的插入,我还想实现批量加载,以便能够对大型数据集进行试验。

我一直在尝试做的是对数据进行排序并开始在叶级别填充页面。必要时在上层复制或推送密钥。我总是在不同的高度跟踪指数的前沿。例如,如果我的索引高度为 3(根,包含内部节点和叶子层的一级),我只在内存中保留 3 页,一旦它们已满,或者没有更多数据,我将它们写入磁盘。

问题是要向每个页面写入多少数据以维持所有单个节点的页面限制。这些限制可以在这里找到。我找不到任何有用的资源,其中包含有关批量加载实施的详细信息或决定使用什么填充率以保证节点限制的好策略。

有任何想法吗?

4

1 回答 1

1

从问题下的评论中,我可以看出您的担忧是最后一页(或最后一页,如果考虑树中较高的页面)可能未达到最小填充数。

由于此类页面的数量受 log2(n)(树的高度)的限制,我怀疑理论性能保证不受影响。

无论如何,您链接到的保证不是正确性所必需的。它们足以保证运行时间的界限。但是,它们对于保证运行时间并不是必需的(例如:在 b 树的末尾添加一页和一行 - 您仍然可以获得相同的保证运行时间)。

如果你想知道真正的 b 树是如何运行的,你可能想看看你最喜欢的 RDBMS(作为 SQL Server 用户,我知道 SQL Server 很高兴地低于 50% 的页面填充度保证而没有实际影响)。我想你会发现理论上的担忧被认为不是很有意义。

于 2012-08-21T21:58:36.607 回答