Can an m-way B-Tree have m odd?

I read on book CLRS that we have m-way B-tree where m is even. But is there is B-Tree where m is odd, if there is then how can we make changes in the code given in this book.

Solution

By an m-way B-tree I assume you mean a B-tree where each internal node is allowed to have at most m children. According to CLRS's definition of a B-tree:

Nodes have lower and upper bounds on the number of keys they can contain. We express these bounds in terms of a fixed integer t 􏰄≥ 2 called the minimum degree of the B-tree: ... an internal node may have at most 2t children.

So the maximum number of children will always be even – by this definition it can not be odd.

However, this is not the only definition of B-tree. There are many definitions with slight differences that ultimately, make little difference to the overall performance. This can cause confusion. There are some B-tree definitions that allow for odd upper bounds and those which don't. CLRS's definition does not odd upper bounds for the children count of internal nodes.

However, another formal definition of a B-tree is by Knuth [1998] (The Art of Computer Programming, Volume 3 (Second ed.), Addison-Wesley, ISBN 0-201-89685-0). Knuth's definition does allow odd upper bounds. While CLRS enumerates all min-max tree bounds of the form (t, 2t) for t ≥ 2, Knuth enumerates all tree bounds of the form (ceil(k/2), k) for k ≥ 2.

Knuth Order, k |  (min,max)  | CLRS Degree, t
---------------|-------------|---------------
     0         |      -      |        –
     1         |      –      |        –
     2         |      –      |        –
     3         |    (2,3)    |        –
     4         |    (2,4)    |      t = 2
     5         |    (3,5)    |        –
     6         |    (3,6)    |      t = 3
     7         |    (4,7)    |        –
     8         |    (4,8)    |      t = 4
     9         |    (5,9)    |        –
     10        |    (5,10)   |      t = 5

So for example, a 2-3 tree, (2,3), is a B-tree with Knuth order 3. But it is not a valid CLRS tree because it has an odd upper bound.

Changing code will not be easy as B-trees have a lot of code depending on variable t. One of the biggest changes would be inside: B-TREE-SPLIT-CHILD(x,i), you'd need find a way to split a child with an odd number of children (an even number of keys) into nodes y and z. One of these two resulting nodes will have one more key than the other. If you're looking for code, I'd recommend looking on the Internet for an implementation of a B-tree that uses a definition similar to Knuth's (e.g. search for "Knuth Order B-tree").