0
$\begingroup$

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 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 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.

$\endgroup$
0
$\begingroup$

As you state, the order is the maximal number of children. That is one more than the number of items the node can store.

$\endgroup$
  • $\begingroup$ for leaf node order is the maximum number of <key,pr> pairs it can hold. Then the number of keys should be same as the order of B+ Tree. But according to en.wikipedia.org/wiki/B%2B_tree the max number of keys is n-1 $\endgroup$ – Shiwam Singh Dec 20 '17 at 10:45
  • $\begingroup$ Why would the maximal number of items/pairs be different for leaf nodes? In both cases it is $n-1$ where $n$ is the order. $\endgroup$ – Hendrik Jan Dec 20 '17 at 14:46
  • $\begingroup$ @HendrikJan the maximal number of items/pairs can be different for leaf nodes. In leaf we use a record pointer (all bits for an address must be used) whereas in an intermediate node we use block pointers. So less bits required. $\endgroup$ – Kishan Kumar Dec 21 '17 at 9:19
0
$\begingroup$

For a B+ tree the order of a node is the maximum number of keys that it can contain. This satisfies the definition of maximum number of children because for a leaf node number of record pointers(children) is same as number of keys. The last pointer present in a leaf node is not considered a children since it links one leaf to another(is not a record pointer).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.