I read here that an m-way B-Tree can have m only odd.

Is that really true?
I've used 2,4 trees that allow a maximum of 4 child linkages for each node (and a minimum of 2).
Isn't this a 4-way B-Tree?

Edited 4 Years Ago by theguitarist

Is that really true?

The powerpoint says that the number m should always be odd, not that it must be. Hopefully the course that the powerpoint supplements would cover the reasoning for that. I assume it's due to simplified splitting and merging algorithms.

If m is even, during splitting, we can choose to keep an extra key in either of the nodes right?

And the minimum number of keys in a non-root node would be floor((m-1)/2). Correct?

If m is even, during splitting, we can choose to keep an extra key in either of the nodes right?

Of course.

And the minimum number of keys in a non-root node would be floor((m-1)/2). Correct?

That depends entirely on the variant of a B-Tree you're using. There's more than one, and the defining characteristic is often the amount of minimum/maximum fillage.

What are these variants?
I've read only 1 insertion algorithm for a B-Tree that will ensure that the formula for minimum keys I mentioned, holds.

This question has already been answered. Start a new discussion instead.