A branching factor is the number of child nodes produced at each tree level. Increasing it changes the practical cost of traversing persistent data structures without changing logarithmic growth. section 9.2
Two-way versus 32-way branching
For a persistent list of 100,000 elements, binary branching requires about log₂ 100,000, or 16.6, operations to access an element. A branching factor of 32 reduces this to about 3.3 operations because log₃₂ N is five times smaller than log₂ N. section 9.2
The useful trade-off is practical rather than asymptotic:
- Access becomes more efficient as the tree becomes shallower. section 9.2
- Updates also improve, although each level copies more elements; CPU architecture affects the practical result. section 9.2
