是否有快速算法来合并已排序的B +树？

Question

我正在编写一个dbm样式的数据库管理器,其中包含不可变的B + Trees作为存储介质(请参阅http://sf.net/projects/aodbm/).是否存在用于合并两个B +树的快速算法(树可能共享节点)？

Answer 1

这是omega(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)