Menu
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 nodes)?
359
The leaf nodes in a B+ tree are linked to each other to provide sequential access. Searching in a B tree is inefficient because records are stored in either leaf or internal nodes. Because all records are stored in the leaf nodes of the B+ tree, searching is very efficient or faster.
In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.
Merge sort is not in place because it requires additional memory space to store the auxiliary arrays. The quick sort is in place as it doesn't require any additional storage.
Two-way merge is the process of merging two sorted arrays of size m and n into a single sorted array of size (m + n). Merge sort compares two arrays, each of size one, using a two-way merge. The sorted sequence is saved in a new two-dimensional array.
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
139
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
