1
$\begingroup$

I was watching a lecture video and the Professor states that it would be very rare to see the order of a Btree to be even. I was hoping for an explanation but he cut it off there and moved on with the lecture.

$\endgroup$
2
$\begingroup$

I don't think there's a right answer to this but you could argue for a preference either way.

Let's define B-tree order m like this

  • max children/values m
  • min children/values m/2
  • max keys m-1
  • min keys Math.ceil(m/2)-1
    • Math.ceil is only needed if m is odd

If m is even, the you have an odd number of keys. For example [a b c], we could split this either [a b] [c] (left bias) or [a] [b c] (right bias). If m is odd you have an even number of keys. [a b c d] would always split into [a b] [c d].

The opposite is true for values. i.e. when you have an even number of keys you have an odd number of values. In which case you need to pick either a left or right bias.

If you declare upfront that you won't deal with odd or even you get a little bit less to think about.

Other than that, it's an arbitrary decision. There's no benefit to either choice.

$\endgroup$
3
$\begingroup$

One thing that distinguishes real-world B-trees from "lecture B-trees" is that real B-trees tend to have nodes and leaves where the size in bytes is fixed. So the "degree" of a B-tree is determined by the number of keys that will fit on a page.

So if the keys vary in size (e.g. strings), the "degree" of different nodes may be different. Roughly 50% of them will have even degree.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.