B+ Tree order of 1 & 2

I am confused regarding the maximum and minimum number of keys to be inserted in a B+ Tree having an order of 1 and order of 2.

In the videos I watch, it is said that the maximum number of keys to be inserted in a node (except the root) is at least m and at most 2m (assuming m is the order).

According to these 2 statements, what is the minimum & maximum number of keys to be inserted in a B+ Tree, having an order of 1 and order of 2? I am not sure if the 2 statements above conflict, or I misunderstood something. Any idea?

Without having the reference to the video, it looks like they use a non-standard definition of the term order, which is the cause of the confusion.

The standard definition of order for a tree would be the maximum branching factor, i.e. the maximum number of children that a node may have. So, in that definition it is not the minimum, but the maximum, and it is not about the number of keys, but about the number of children.

The video's definition would mean that the maximum number of keys would always be an even number, while in reality there is no such requirement. B+ trees may well have a maximum branching factor that is even, making the maximum number of keys odd.

Using standard definition of the term order, we specifically have for B+ trees these constraints:

• Its internal nodes have at the most m children. This means that they have at the most m - 1 keys.
• Its internal nodes have at least m/2 (rounded upwards) children, except for the root:
• If its root is not a leaf, it may have as few as 2 children.
• Its leaves contain the actual data values.

Here is an example B+ tree with order 4 (standard definition), which corresponds to a B+ tree where the number of keys must be between 1 and 3 -- something that does not fit with the video's definition:

As you can see, a node can here at most have 4 children, and at most 3 keys. In your definition where 2m represents the maximum number of keys, the order is actually 2m+1. So you are asking for examples of B+ trees of order 3 and 5, using the standard definition of order.

Here is an example of order 3 -- the lowest possible order for B+ trees -- which means the number of keys must be either 1 or 2 in each node: