Search code examples
algorithmtreeb-tree

Creating a B-tree

I am reviewing for my exam tomorrow and was stuck on a question. I have to draw a valid B-tree where M = 4 and L = 3 containing the values 1-25. The problem is that I can't get my tree to look like the answer. The answer tree looks like this:

             9            14             22
            /       |             |        \
         4 7       12           17 20        24
        / | \     /  \         /  |  \      /  \
       1  4  7   9   12      14  17  20   22   24
       2  5  8   10  13      15  18  21   23   25
       3  6      11          16  19  21

Sorry if this is difficult to read. Perhaps I copied the answer wrong but can anyone confirm if this the correct answer? If so how was this answer reached?

Solution

  • Looks like you're talking about a B+ Tree rather than a BTree, and there is a small typo: you have key 21 duplicated in the leaf [20,21,21]. As you say, the Order is 4.

    The answer is a valid B+ Tree, but not the one you'd get by adding values 1-25 in sequence. Did the question give a specific order in which the keys were to be added, or was the question to try and determine that for yourself? Other than a lengthy trial and error process I'm not sure how you'd determine the sequence, but you can try it out by using the demo page here:

    http://goneill.co.nz/btree-demo.php

    If you want to try various sequences of insert you'd do better to download the offline version and edit the Hardcoded() function:

    http://goneill.co.nz/btree.php

    It's all in JavaScript which might not be useful to you though.