Handling a branching factor of 2

[sharwell]

When a branching factor of 2 is used in a B+-tree data structure, it is possible for pathological tree shapes to be created where entire unnecessary index levels exist. A tree falls into this category if the following are all true:

• The tree contains N data elements
• The tree contains N leaf nodes (where each leaf node holds one data element)
• The index level above the leaf nodes contains N index nodes (where each index node references one leaf node)

This situation can occur multiple times, resulting in substantial indirection between the leaf nodes and the root.

The easiest way to address this is requiring the branching factor to be at least 3. Trees with a branching factor require each node (except the last at each level) to contain at least 2 elements, resulting in a worst-case structure with binary fan-out. Other ways to address this also exist.

[sharwell]

Another option for addressing this is modifying the algorithm to ensure two adjacent nodes cannot be merged into a single node.