Существует ли быстрый алгоритм объединения отсортированных деревьев B +?

Question

Я пишу менеджер баз данных в стиле dbm с неизменными деревьями B + в качестве носителя данных (см. http://sf.net/projects/aodbm/). Существует ли быстрый алгоритм объединения двух деревьев B + (где деревья потенциально совместно используют узлы)?

Answer 1

это проблема омега (н).
доказательство: предположим, что оно имеет лучшую сложность O (d) и d
O (n) решение (на самом деле это будет, конечно, тета (n)):
1.плоские T1 и T2 в отсортированные массивы A1, A2.
2.используйте A
3. построить пустое «почти полное» дерево T с точно | T1 | + | T2 | «место».
4. заполнить T с A (поиск по порядку)
5. Результатом является Т.

Сложность:
шаг 1 - O (n) (в поиске заказа)
шаг 2 - сложность слияния O (n) (поскольку A1, A2 оба отсортированы)
шаги 3 + 4 также тривиально O (n)