Search code examples
databasetreeb-tree

What is the minimum number of a valid B+tree?

I'm trying to appeal on a question I had on my exam the other day, about a B+tree.

The question was:

Consider a B+tree with l as factor (assuming l is positive and even), h>=0 as height (the root is considerto be 0) and n>=1 as the number of records.

There were 5 answers. 3 of them I eliminated immediately, and had to choose between these two:

  1. h>1 ==> n >= 0.5*l*(l+1). The second direction is not guaranteed: it depends on the arrival order of the keys.
  2. None of the above.

I chose (2) and the lecturer says its option (1). I have the following example that I think contradicts it:

                      7
               /              \
              3                9
           /     \           /   \
        1 2      3 4 5     7 8    9 10

With l=4, and h=2:

  • Does this b+tree represent a valid B+tree?
  • Is my lecturer actually wrong?

I would really appreciate some help here. Is this example a good one to base my appeal on?

In general, what is the minimum number of records n in a B+tree with height h and factor l?

Solution

  • Well, apparently I was right... The tree I showed is legal and is contrasting the lecturer's answer.

    By inserting the following keys in that order: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 and then taking 6 out of the tree will create a valid B+tree of height > 1 and n<10.

    This contradicts the h>1 ==> n >= 0.5*l*(l+1) rule in the answer...

    After many tries and lots of bureaucracy the lecturer accepted my answer and I got the points :)

    Thanks for the try @Jonathan Leffler...