1
$\begingroup$

https://en.wikipedia.org/wiki/B-tree#Initial_construction

Currently I know of 2 ways for building a B-Tree : bulkloading and just inserting key after key.

In the wiki example the keys are sorted, which I guess is a condition for this bulkloading concept.

What is the advantage of bulkloading if the keys are unsorted ? because I have to sort them myself still resulting in O(nlogn) , same as inserting key after key in the B-Tree.

Thanks.

$\endgroup$
  • 2
    $\begingroup$ Hint: asymptotic runtime is not the only interesting characteristic of an algorithm. $\endgroup$ – adrianN Jul 27 '17 at 12:27
  • $\begingroup$ @adrianN the wiki article didn't mention why it's really done , my first thought was that this building technique is used to reduce the asymptotic runtime $\endgroup$ – Oleg Jul 27 '17 at 13:08
  • 1
    $\begingroup$ Because you sort "flat data", so with bulk loaded data you save (mean) time of the tree traversal and (possibly) some splits that could be avoided knowing data in advance. $\endgroup$ – Evil Jul 27 '17 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.