有没有一种快速算法可以合并排序后的B+树？

Question

我正在编写一个类似dbm的数据库管理程序，使用不可变的B+树作为存储介质（请参见http://sf.net/projects/aodbm/）。是否有一种快速算法可以合并两个B+树（其中树可能共享节点）？

- dan_waterworth

---

树A的最大键是否小于或等于树B的最小键？如果是，那么速度非常快，否则我认为您将不得不采用更复杂的算法。 - phimuemue

@phimuemue，不幸的是，这只在极端人为的情况下才会发生。 - dan_waterworth

Answer 1

这是一个O(n)问题。
证明：假设它的复杂度更好，为O(d)，其中d < n。你可以将B+树排列成一个数组，然后合并两个树就相当于合并两个数组。如果是这样，你可以在O(d)时间内执行merge(A1,A2)，使用归并排序可以达到O(dlog(n)) - 矛盾。

一个O(n)解决方案（实际上当然是theta(n)）：
1.将T1和T2展平成排序数组A1、A2。
2.使用A <- merge(A1,A2)。
3.用恰好有|T1|+|T2|个“几乎满”的位置构建一个空树T。
4.用A填充T（中序搜索）。
5.结果是T。

复杂度：
步骤1是O(n)（按顺序搜索）。
步骤2是O(n)合并的复杂度（因为A1、A2都是排序的）。
步骤3+4也很容易达到O(n)。

- amit

---

是的，除了树可能共享节点之外。在这种情况下，共享节点的子节点不必迭代，因此可能存在一种算法，其时间复杂度为O(n)，其中n是未共享且具有具有共享子节点的父节点的子节点数。 - dan_waterworth

@dan 共享节点是否也共享它们的所有子节点？因为如果不是这种情况，即使您设法在O（n）中对未共享节点进行排序，您仍需要以某种方式操作每个共享节点 - 因此它们的子树也将被排序，这将是O（| V | - n），然后您将回到O（n）。或者我错过了什么？关于查找共享节点 - 我想不出比BFS更好的方法（也没有证明没有）。 - amit

@amit，如果您修改您的答案并加入这个内容，我会接受您的答案。 - dan_waterworth

@dan 我提出的建议有问题（在编辑时注意到），问题在于结果树将更深，其高度实际上将为 O(logn + h)，其中 h 是最深公共树的高度（因为我们要将高度为 h 的树添加到 logn 树中...）。在平均情况下，它会很好（因为 n 是非共享节点的数量），但在某些情况下，它可能会增加树的高度。另外：它需要手动向树中添加叶子节点（为了以 O(1) 的时间复杂度完成此操作，您需要指向最小和最大元素的指针，因为您要添加的每个元素都比子树中的元素大或小）。 - amit

@amit，我的想法是首先找到应用于T1后得到T2的变更集。然后从变更集中删除所有删除操作。然后将变更集应用于T1。我认为这可能是朴素的O(c log n)，其中c是更改数量，n是树的大小。 - dan_waterworth