How Database Indexes Rot and How to Fix Them
Your database indexes rot over time, making queries slower. Frequent writes cause fragmentation (disordered pages) and low page density (half-empty pages), forcing more disk I/O.
Why it exists
Databases must handle data modifications (inserts, updates, deletes) efficiently. To do this, B-tree indexes dynamically adjust their structure. This constant adjustment, while necessary for write performance, inevitably leads to a gradual disorganization of the index over time, which hurts read performance.
The mental model
Think of a library where books are initially shelved in perfect alphabetical order. As new books arrive (inserts), librarians find space where they can, sometimes on a different shelf or floor. Over time, finding a series of books by one author requires running all over the library (random I/O) instead of walking down one aisle (sequential I/O). This is index fragmentation.
How it works
Index degradation has two primary components. First, fragmentation. In a B-tree index, logical ordering (by key value) should match the physical ordering of pages on disk. Modifications break this link, forcing the database to perform many small, slow random I/O operations instead of a few large, fast sequential ones for range scans. Second, low page density. When a data page is full and a new row must be added, the database performs a "page split," creating two new pages that are each about 50% full. This means more pages are needed to store the same data, increasing I/O and memory pressure.
When to use it
Index maintenance (reorganizing or rebuilding) is crucial for tables with frequent INSERT, UPDATE, and DELETE operations. It's most effective when queries that perform index scans are running slower than expected. If the query optimizer starts choosing different, less efficient plans for the same queries, it's a strong signal to check index health.
When not to use it
Don't perform maintenance on indexes for read-only or rarely modified tables, as they won't be fragmented. Maintenance operations can be resource-intensive, locking tables and consuming significant I/O and CPU, so they should be scheduled during off-peak hours. Over-maintaining indexes with very low fragmentation is a waste of resources.
One canonical example
A page in your index is 100% full. An INSERT statement needs to add a new row that belongs on this page. The database performs a page split: it creates two new pages and moves half the rows from the old page to one and the other half to the other. The new row is then inserted. The result is two pages that are now only about 50% full. The database now needs to read two pages instead of one to get the same amount of data, doubling the I/O for that range.
Interview question
What is the primary consequence of a database index page split?
- a.The database must perform a full table scan instead of using the index.
- b.Duplicate index entries are created, consuming excessive storage space.
- c.Two new pages are created, each approximately 50% full, increasing I/O for the same data.Correct
- d.The index's logical order no longer matches its physical storage order.
Why? this is the answer
A page split occurs when a full page needs a new row, resulting in two new pages that are only about 50% full, which directly increases the number of I/O operations required to retrieve the same amount of data. Option D describes fragmentation, which page splits contribute to, but is a broader issue than the direct consequence of the split itself.
Just read this? Test yourself on what you have been reading.
Read the original → learn.microsoft.com
- #databases
- #indexes
- #performance-tuning
- #sql
You just looked this up. Could you explain it out loud?
That is the part interviews actually test. Tezvyn takes questions like this one and gives you what the interviewer is really checking, the answer that lands, and the mistake that ends the conversation, in the four minutes before your next meeting.
The iPhone app is on the way
We are building it. Until it lands, nothing here is held back from you: every interview card, your saved cards, streaks and the job board all work in Safari, plus hundreds of free practice quizzes of thirty questions each. Sign in and it all carries over to the app the day it arrives.
Want it as an icon? Tap Share at the bottom of Safari, then Add to Home Screen. It opens full screen and the cards you have read stay available offline.
We are hiring for this. Open roles that interview on databases — each one lists the topics its interview covers.
See open roles