What happens to a B+tree index page when its entries are deleted? Describe underflow, merging and redistribution, and explain why real implementations often do not merge pages aggressively.

## The delete path in the textbook B+tree Every B+tree definition specifies a minimum occupancy — classically, each non-root page must remain at least half full. Deleting an entry can violate that, which is called **underflow**. The classical repair has two forms: **Redistribution (borrowing).** If an adjacent sibling has more than the minimum, move entries across so both pages are legal again. Only one separator key in the parent needs updating to reflect the new boundary; the tree's shape is otherwise unchanged. This is the cheaper repair and is preferred when possible. **Merging (coalescing).** If the sibling cannot spare entries — because it is itself at or near the minimum — the two pages are combined into one, and the now-redundant separator key is removed from the parent. At the leaf level, the emptied page is also unlinked from the sibling chain so ordered scans remain correct. Removing a separator from the parent is itself a delete, so the parent may underflow and repeat the same procedure one level up. In the extreme the cascade reaches the root; when the root is left with a single child, that child becomes the new root and the tree's height decreases by one. That is the exact mirror of the root split that grows the tree, and it is the only way a B+tree gets shorter. ## Why production engines behave differently **Reason one: multi-version visibility.** In an MVCC engine, deleting a row does not immediately make its index entry removable. Transactions that started earlier hold snapshots in which the row version is still visible, and they may legitimately reach it through the index. So the delete path marks the entry dead and defers actual removal to background maintenance that runs once no active snapshot can see the version. Aggressive structural repair at delete time is therefore not even possible — at the moment of the delete, the entries are still needed. **Reason two: concurrency cost.** A split touches a page, a new page, and the parent, and widely used protocols make it cheap for concurrent readers: each page carries a link to its right sibling and a high key, so a reader that lands on a page which has since split simply follows the link. Merging does not enjoy the same trick. It removes a page that concurrent readers and scans may be positioned on or about to follow, and it requires holding several pages consistently at once — two siblings plus the parent — which introduces lock-ordering and deadlock concerns. Many implementations therefore restrict merging severely, perform it only through a separate maintenance path, or handle only the simple case of a page that has become completely empty. **Reason three: it often is not worth doing.** Deletes frequently come in patterns that will be refilled. A queue table deletes low keys and inserts high ones; a table with a status index moves entries between ranges constantly. Merging pages that will be repopulated shortly is wasted structural work plus wasted logging. ## What actually happens, then The typical production behaviour is: 1. Delete marks index entries dead; the page's live count falls but its size does not. 2. Background maintenance later removes dead entries, reclaiming space **inside** the page. 3. If a leaf page becomes entirely empty, it is unlinked and placed on the index's free list, from which it can be reused anywhere in the index once no scan can still be positioned on it. 4. A page that ends up 20% full simply stays 20% full, and its space is reusable only for keys in its own range. The visible consequence is that indexes shrink far less readily than they grow, and that a large range delete leaves a long stretch of sparse pages that will never refill if the key is monotonically increasing — a date, an id — because no future key will ever fall into that range. ## What this means in practice - **Do not expect deletes to shrink an index.** Reclaiming that space requires a rebuild or a compacting reorganize, or removing the segment structurally. - **Delete patterns matter more than delete volume.** Deleting scattered rows leaves modest gaps that get reused; deleting a contiguous key range on an ever-increasing key leaves permanently dead space. - **Partitioning converts the problem into a non-problem.** Dropping a partition removes its index segment outright: no dead entries, no underfull pages, no maintenance. - **Long-running transactions block step 2.** If an old snapshot is held open, dead entries cannot be reclaimed at all, so even the in-page space recovery stops happening. ## Answering the question well A strong answer separates the two layers explicitly: the classical algorithm (underflow, redistribute, merge, cascade, root collapse) as the textbook contract, and the engineering reality (deferred reclamation under MVCC, merges avoided because they are concurrency-hostile, only empty pages recycled) as what engines actually do — and then connects that gap to the operational consequence: index space is not returned by deleting rows.