B-Tree Insertions and Splits
How wide, balanced trees reduce page reads.
A B-tree stores several keys in each node. Database indexes often size nodes to fit a storage page, so one page read brings in many keys. A wider tree needs fewer levels to hold the same number of entries.
To insert a key, find the leaf where it belongs. If a node exceeds its capacity, split it and promote the middle key to its parent. Splits can continue upward; splitting the root adds a level while keeping every leaf at the same depth.
A useful exercise is to insert the numbers 1 through 20 into an order-5 B-tree, using the convention that a node has at most five children. Draw the tree after each split and check that its keys stay sorted and its leaves stay at the same depth.