What is the fastest way to merge two B trees?

Given two B-trees of some order $$m$$ - $$T_1,T_2$$, such that $$y > x$$ for every pair $$x \in T_1$$ and $$y \in T_2$$. What is the fastest way to create a new tree that is the union of both $$T_1,T_2$$?

My current solution is naive in a sense that I create an array and insert all $$T_1$$ elements, than all $$T_2$$ elements. As a result I have a sorted array which I can create a new tree off of with a cost of $$n \log n$$

I'm thinking that there must be a better solution, something like the AVL merging question but I can't figure it out.

• This isn't an answer, but for B+-trees, by far the easiest solution is to do a merge of the leaf nodes, and then build the branch nodes. – Pseudonym May 5 at 2:04

It is great that you have obtained a sorted array, which runs in $$O(n)$$ time.

Once we have $$n$$ elements in a sorted array, every kind of "nice" tree, that I know, can be built in $$O(n)$$. In particular, we can build a $$B$$-tree in $$O(n)$$ time.

Here is an example. Suppose the sorted array is $$[1, 2, 3, 4, 5, 6, 7,8,9,10,11,12,13,14,15,16,17]$$ and we want to build a $$2$$-$$4$$ $$B$$-tree. Split the array into groups of $$2$$ numbers, except that last group that could be $$2$$ or $$3$$ numbers. $$\{1, 2\}, \{3, 4\}, \{5, 6\}, \{7,8\},\{9,10\}, \{11,12\}, \{13,14\}, \{15,16, 17\}.$$

Had the number of groups been an odd number, great. Otherwise, distribute the elements in the last group so that the number of groups becomes odd.

$$\{1, 2\}, \{3, 4\}, \{5, 6\}, \{7,8\},\{9,10\}, \{11,12, 13\}, \{14,15,16, 17\}.$$

Label the groups successively as $$g_1, g_2, \cdots, g_7$$. Let $$g_1$$ be the root of the tree. Let the left child of $$g_i$$ be $$g_{2i}$$ if $$2i\le n$$ and the right child of $$g_i$$ be $$g_{2i+1}$$ if $$2i+1\le n$$. Now we have a complete binary tree where

• each node contains at least 2 number, and
• each internal node has 2 children.

That means, it is a $$2$$-$$4$$ $$B$$-tree.

The example above should provide enough idea so that a full algorithm for general situations should not be too difficult to figure out.

• While it is correct that every kind of "nice" tree, including $B$-tree can be built in $O(n)$ given a sorted array, my $B$-tree is not fully correct. (I would like to spend more time to explore whether there is a $O(\log n)$ way in the case of $y>x$ for every pair $x\in T_1$ and $y\in T_2$ as well.) – John L. May 5 at 13:51
• Yes, $O(\log n)$ can be done, easily ...updating ... Drawing graphs is time-consuming ... – John L. May 7 at 15:07