Overview
The order, or branching factor, b of a B+ tree measures the capacity of nodes (i.e., the number of children nodes) for internal nodes in the tree. The actual number of children for a node, referred to here as m, is constrained for internal nodes so that . The root is an exception: it is allowed to have as few as two children. For example, if the order of a B+ tree is 7, each internal node (except for the root) may have between 4 and 7 children; the root may have between 2 and 7. Leaf nodes have no children, but are constrained so that the number of keys must be at least and at most . In the situation where a B+ tree is nearly empty, it only contains one node, which is a leaf node. (The root is also the single leaf, in this case.) This node is permitted to have as little as one key if necessary, and at most b.
| Node Type | Children Type | Min Children | Max Children | Example b = 7 | Example b = 100 |
|---|---|---|---|---|---|
| Root Node (when it is the only node in the tree) | Records | 1 | b | 1 - 7 | 1 - 100 |
| Root Node | Internal Nodes or Leaf Nodes | 2 | b | 2 - 7 | 2 - 100 |
| Internal Node | Internal Nodes or Leaf Nodes | b | 4 - 7 | 50 - 100 | |
| Leaf Node | Records | b - 1 | 3 - 6 | 50 - 99 |
Read more about this topic: B+ Tree