Here’s something counterintuitive about B+ trees - inserting keys in sorted order is fast, but it comes with an interesting hidden cost…
When you insert keys sequentially (1, 2, 3, 4…), the B+ tree doesn’t need to split nodes or reorganize. Every new key goes straight to the rightmost leaf, making insertions incredibly efficient. Minimal rebalancing and minimal disk blocks touched.
But here’s the trade-off: this creates severe internal fragmentation.
Since all insertions happen at the right edge, the left nodes never get filled to capacity. You end up with mostly empty nodes sitting in storage, wasting space. A node that could hold 100 keys might only have 50-60, and that inefficiency compounds across the entire tree.
Random insertions, on the other hand, distribute keys more evenly across nodes. They’re slower because of the splits and rebalancing, but they achieve much better space utilization.
So if you’re bulk-loading data into a B+ tree, sorted insertion gives you speed. But if you care about memory efficiency in the long run, you might want to shuffle your keys first or use specialized bulk-loading algorithms that pack nodes more densely.
So, like always, there is no one best way to do anything :)