Btrees don't need to be rebalanced. They only split. The cost of splitting to the root is counteracted by the cache locality of always accessing the same set of

Btrees don't need to be rebalanced. They only split. The cost of splitting to the root is counteracted by the cache locality of always accessing the same set of pages. Inserting into the last page only needs O(logn) page accesses and O(logn) page writes worst case.