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?

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?

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 …

## All 6 Replies

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.

What are these variants?

They're intuitively named, like B+Tree or B*Tree. ;)

Okay. Thank you :)
I always considered them as different from B-trees.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.