B+ Trees

Question

Going with the definition, that order of a B+ tree is the maximum number of children a node can have.

What is exactly meant by the order of a leaf node? As per my understanding order of a leaf node is the number of <key,pr> pairs it can hold.

But in general when order of a B+ tree is defined in a question like, order is 5. Example:https://www.tutorialcup.com/dbms/b-tree.htm . Then we assume the leaf nodes to have keys in [n/2] to n-1(3 to 4).

If we assume the leaf can contain 5 pairs then. Then the upper limit on keys should be 5 and not 4. Could someone explain why its taken to be n-1 in every B+ tree insertion tutorial.

Comments

Could you please answer with respect to B+ Trees.

Assume a leaf node has an order of 5.

Then the leaf node can have at-most 5 children pointers, which will be originating from the <key,pointer> pairs. Then the number of keys should also be 5. Assuming we are not counting the pointer to the next leaf.

If we count the next leaf pointer, then the number of keys will be 4 and that means, number of pairs are 4 and the order of a leaf node is defined as number of key, pointer pairs. This contradicts to our original assumption of order as 5.

---

@Shiwam

in B+ trees order of leaf node is number od <key,value> pairs!

order of internal node is number of child pointers.

---

Yes, I am also assuming the same.

But referring to any insertion tutorial for B+ Tree, like the one mentioned:  https://www.tutorialcup.com/dbms/b-tree.htm

The maximum number of keys should be same as order of the leaf node, but the number of keys is taken to be "n -1 " where n is the order of B+ Tree.

Also refer to this wiki: https://en.wikipedia.org/wiki/B%2B_tree

Answer 1

I am glad to answer this because I too faced this doubt at a point of time and then I simply worked on simple maths on this. Below proof will definitely clear your doubt. 

There is an assumption involved:

Size of block pointer = Size of record pointer.