Why is it that Btrees most of the times have a degree that is odd? What happens if they are even?

Question

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.

Answer 1

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.

Answer 2

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.