The Balance of B-Trees

Because B-trees grow (and shrink), they always maintain a kind of balance. To be specific, all leaf nodes of a B-tree are always on the same level of the tree. It’s not like one path of the tree can end on the second level while another path stretches down to the fourth level. Because new values are only inserted into leaf nodes, and the tree only grows upwards, leaf nodes cannot possibly end up on different levels of the tree.

Another way to look at this is that if I try to make one branch of the tree fatter than the others, at some point, I’ll end up failing. This is because if I make one node too fat, it ends up splitting! And once it splits, all parts of the tree grow at the same rate, and not only that branch.

Ultimately, the fact that all leaf nodes live on the same level means that all paths from the root to any leaf node are all the same length. And so, in this sense, we can say that a B-tree always remains balanced.

That being said, we cannot say that a B-tree is always perfectly efficient. As with BSTs, inserting values in, say, perfectly ascending order will reduce the tree’s efficiency to some extent. For example, look at the following B-tree:

This tree houses all integers from 1 through 8 on two levels efficiently, as all the nodes are full. Now, when building this tree, I happened to insert the integers in the sequence of 1-5-3-6-8-4-2-7, and it worked out great.

However, if I build the B-tree by inserting the same integers in perfectly ascending order, we get this tree:

You can see that this tree uses three levels while the previous tree used only two. Accordingly, we’re not filling the nodes to capacity.

The reason this happens is that when we insert values in ascending order, we always insert each new value into the right-most leaf node. And so, while there are other leaf nodes to the left that have potential room to hold new values, we nonetheless ignore those leaf nodes and don’t make use of their full capacity. Instead, we keep inserting into the right-most leaf node, which keeps causing it to split and grow the tree.

In other words, when inserting ascending values into a B-tree, we unnecessarily cause the B-tree to grow instead of first filling each node to capacity.

Ultimately, as with plain old BSTs, a B-tree could also benefit from randomizing the order in which we insert values.