1
$\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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\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).

Improve this answer
$\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.

Improve this answer
$\endgroup$
3
  • $\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$ Commented Dec 20, 2017 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$ Commented Dec 20, 2017 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$ Commented Dec 21, 2017 at 9:19

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.