A table's live row count has been flat for months, yet queries served by one of its B+tree indexes keep getting slower. What can happen inside an index over time that explains this, even with no growth in live data?
answer
- Cost tracks pages, not live entries
- Dead entry lives until no snapshot needs it
- Empty page recycled, half-empty page stays
- Density down → effective cache smaller
- Bloat = space; fragmentation = order
basics
~20 sDeletes and updates leave dead entries and half-empty pages behind. The same live keys end up spread over more pages, so scans read more pages and each cached page carries less useful data. That is index bloat.
solid answer
~50 sAn index's cost is driven by **pages**, not by live entries. Every delete, and every update of an indexed column, kills an index entry; in an MVCC engine that dead entry must survive until no running snapshot can still see the row version it points at. Space is reclaimed later by background maintenance, and reclaiming frees room *inside* a page — the page itself normally stays in the index and is only reusable for keys in its own range. Over months of churn the index converges on the same number of live keys spread across far more, far emptier pages. A range scan reads pages, so halving page density roughly doubles its I/O. The buffer cache degrades the same way: each cached page holds fewer useful entries, so the effective cache shrinks and more reads go to disk. Enough extra leaf pages can even add a tree level. Fragmentation compounds it: the leaf chain is no longer in physical order, so ordered scans become random I/O.
code
text · 7 linesentries per leaf page (dense, 90% fill): ~360
entries per leaf page (bloated, 30% fill): ~120
scan returning 12,000 index entries
dense : 12,000 / 360 = 34 leaf pages read
bloated : 12,000 / 120 = 100 leaf pages read
same rows returned, ~3x the I/O and ~3x the cache footprintgo deeper
Say that deletes and updates leave dead entries, that pages therefore hold fewer live entries than they could, and that reading more pages for the same rows is slower.
Add the MVCC reason entries can't be removed immediately, the distinction between bloat (density) and fragmentation (physical order), and that scan cost is per page.
Tie it to observable symptoms — scans degrade while point lookups don't, cache hit ratio drifts down — and name the operational causes such as long-running transactions blocking reclamation.
Frame it as a lifecycle question: which workloads inevitably bloat, when to solve it structurally (partition drop instead of bulk delete, killing unused indexes) rather than with recurring rebuild jobs.
## Pages, not rows A B+tree index is stored as fixed-size pages (blocks), typically 4–16 KB. Leaf pages hold index entries in sorted key order: the key value plus a pointer to the row. Internal pages hold separator keys that route a search down to the right leaf. The storage engine reads and writes whole pages, and caches whole pages. That single fact drives everything about bloat: the price of using an index is the number of *pages* it must touch and keep resident, not the number of live entries it contains. ## Where dead entries come from - **DELETE** removes the row; its index entry becomes dead. - **UPDATE of an indexed column** is logically a delete plus an insert: the old entry dies and a new entry appears elsewhere in key order, because the key moved. - **UPDATE of any column** in engines that write a whole new row version can also require new index entries pointing at the new version, unless an optimization lets the new version be reached through the old one. - **Rolled-back transactions** leave entries behind too — they were written before the abort. In a multi-version (MVCC) engine, a dead entry cannot be removed the instant the row dies: an older transaction may still be running with a snapshot in which that row version is visible. Removal is therefore deferred to background maintenance that runs after the version becomes invisible to everyone. ## Why space is not handed back automatically When maintenance does reclaim a dead entry, it frees slots *within* a page. That page stays allocated to the index. A page that ends up completely empty can usually be recycled onto a free list and reused anywhere; a page left 25% full stays 25% full unless new keys happen to land in that page's key range. The index file's high-water mark rarely shrinks — files typically only give space back to the filesystem when a rebuild rewrites them, or when free pages sit at the very end. So the steady state after heavy churn is: correct index, correct results, same live key count, but many more pages, each thinly populated. ## Bloat versus fragmentation Two related but distinct defects: - **Bloat (low page density)** — pages hold far fewer live entries than they could. Costs page count and cache efficiency. - **Fragmentation (logical/physical order divergence)** — the leaf pages, chained in key order, no longer sit in ascending physical order on disk. Costs sequential-read efficiency: what should be a readahead-friendly sequential scan turns into scattered random reads. A freshly built index has both properties good: dense pages laid out in key order. Churn erodes both, though different workloads erode them at different rates. ## Why performance degrades 1. **Range scans read more pages.** A scan returning 10,000 entries at 90% density might touch 60 pages; at 30% density it touches 180. The rows returned are identical; the I/O tripled. 2. **Cache efficiency collapses.** The buffer pool caches pages. If a page holds a third as many live entries, the same cache memory covers a third as much of the index, so a workload that used to be memory-resident starts hitting storage. 3. **Tree height can grow.** More leaf pages need more internal pages; crossing a threshold adds a level, and every single-row lookup pays one more page read. 4. **Maintenance cost grows.** Background reclamation, statistics sampling and backups all scan the physical structure, so they get slower too, which delays the very process that would clean it up. 5. **Ordered scans lose locality.** Fragmentation converts sequential I/O into random I/O — a large multiplier on spinning disks and still meaningful on network-attached storage. ## What bloat does not explain A unique point lookup costs roughly the tree height in page reads, and height grows logarithmically. If a single-row lookup went from 1 ms to 50 ms, bloat is a poor explanation; look at lock waits, a changed plan, stale statistics, or a cold cache instead. Bloat's signature is that scan-shaped and cache-sensitive work degrades gradually while point lookups barely move. ## Workloads that bloat fastest Queue and job tables (insert, process, delete, forever), tables where a status or timestamp column is indexed and updated repeatedly, bulk deletes of old data by date, and indexes on randomly distributed keys where inserts land all over the structure. ## Keeping it in check Ensure background reclamation actually keeps up (long-running transactions and idle-in-transaction sessions block it, because they hold old snapshots alive). Delete large ranges by dropping a partition rather than by row-by-row DELETE. Drop indexes nobody uses — an unused index still bloats and still costs on every write. And rebuild when measurement, not superstition, says density has genuinely collapsed.
- Does bloat hurt a single-row primary-key lookup as much as it hurts a range scan?No. A point lookup costs about one page read per tree level, and height grows only logarithmically with leaf count, so bloat usually adds at most one level. A range scan, by contrast, pays per page touched, so its cost scales almost linearly with the loss of density. That asymmetry is a useful diagnostic: if point lookups are fine but scans have doubled, bloat is a plausible cause.
- Why can't the engine remove an index entry the moment the row is deleted?In an MVCC engine the delete only marks a row version as dead for transactions that start after it commits. Older transactions still holding a snapshot may legitimately need to see that version, and they may reach it through the index. The entry can only be removed once no active snapshot can see the version, which is why reclamation is a deferred background job — and why a single long-running transaction can stall cleanup database-wide.
- If deletes leave the file the same size, how does the space ever get reused?Reclaimed space inside a page is reused by later entries whose keys fall in that page's key range, and pages that become completely empty are put on a free list and can be reused anywhere in the index. The file shrinks only when free pages happen to be at the end, or when a rebuild rewrites the whole structure.
A filing cabinet after years of folder removals: the same documents remain, but they are scattered thinly across twice as many drawers, so every search walks further.
saying these in an interview costs you the question
- "Deleting rows shrinks the index file" — the pages stay allocated; only a rebuild reliably returns space
- "Bloat affects the table but not the indexes" — indexes usually bloat faster, because updating an indexed column kills an entry even when the table is barely touched
- "Once I rebuild, it stays compact" — the same churn rebuilds the bloat; rebuilding is maintenance, not a fix
- "It's only wasted disk, disk is cheap" — the real cost is buffer-cache dilution and extra I/O per query
- "An unused index is harmless" — it still bloats, still costs on every write, and still has to be maintained