B树中的大容量装载

Question

施工

目前我知道两种构建B树的方法:大容量加载和在键后插入键。

在wiki示例中，对键进行排序，这是大容量加载的先决条件。

如果密钥没有排序，大容量装载的好处是什么？因此，我必须自己对它们进行排序，结果仍然是O(nlogn)，就像在B-树中插入后面的键一样。

谢谢。

Answer 1

考虑以下情况：

• 如果数据已经被排序，那么您不需要自己对数据进行排序。这可能导致O(n)加载(我不是散装装载方面的专家)。
• 如果树非常大，并存储在磁盘或多台机器上，那么内存局部性可能会发挥作用。大容量加载避免在添加某些内容之前将树的部分“加载”到内存中。

Answer 2

红黑树和四树的区别是滞后的，B树为将来的使用留出了空间。只有当节点有太多的键时，它才会分裂成两半。当一个人按顺序提交键时，就会出现低效率；也就是说，一半填充的节点永远不会满，因为一个节点总是添加到一边。

这是一个三棵树的例子 (使用Knuth的定义)，我按升序插入了数字1-8。这棵树大多处于低端入住率.访问数据的节点数的期望值为2.5。

​

​

散装是一个过程，通过这个过程，我们忽略了分裂的规则，并尽可能地把它包装在一起，因为我们知道我们可能有更多来自右边的东西。它还有助于避免不必要的复制，而代价是可能不得不修复树以恢复右边的B树不变量。在这个过程中，我大量加载了相同的数据。

​

​

虽然渐近空间和运行时是相同的，但它使用几乎所有的空间，而不是占用空间的一半以上。因此，此时的平均查找成本较低，期望值为1.75。当加载保持相对静态的大量数据时，这会更有用。