Is there a fast algorithm to merge sorted B+Trees?

I'm writing a dbm style database manager with immutable B+Trees as the storage medium (see http://sf.net/projects/aodbm/ ). Is there a fast algorithm for merging two B+Trees (where the trees potentially share开发者_StackOverflow中文版 nodes)?

it is omega(n) problem.
proof: assume it had better complexity O(d) and d < n. you can arrange a B+ tree as an array, and then merging the two trees will be merging two arrays. if so, you could do merge(A1,A2) in O(d), and using mergesort could be O(dlog(n)) - contradiction.

a O(n) solution (actually it will be of course theta(n)):
1.flat T1 and T2 into sorted arrays A1,A2.
2.use A <- merge(A1,A2)
3. build an empty "almost full" tree T with exactly |T1|+|T2| 'places'.
4. fill in T with A (in-order search)
5. result is T.

complexity:
step 1 is O(n) (in order search)
step 2 is O(n) merge`s complexity (since A1,A2 are both sorted)
steps 3+4 are trivially O(n) as well