Index Rebuilding

Imagine a library with a card catalog. Every book has a card, filed alphabetically. When new books arrive, the librarian slots cards into the right place. When books are removed, the cards are pulled out.

Over months and years, the catalog gets messy. There are gaps where cards were removed. Some drawers are half-empty while others are overflowing. Finding a card now means flipping through empty space, jumping between drawers that used to be adjacent.

That's exactly what happens to database indexes. When you INSERT, UPDATE, and DELETE rows, the index structure, typically a B-tree, develops fragmentation. Pages that were once full now have gaps. Pages that were sequential on disk are scattered across different locations. The index still works, but it's slower than it should be.

Index rebuilding is the process of creating a fresh, compact, perfectly ordered copy of the index. It's like reorganizing the entire card catalog from scratch.

B-tree indexes, the default in PostgreSQL, MySQL, SQL Server, and Oracle, degrade over three mechanisms:

Page splits: When you insert a row and the target B-tree page is full, the database splits it into two half-full pages. Over time, heavy inserts create many half-full pages. Your index uses twice the storage it actually needs.

Dead space from deletes: When you delete a row, the index entry isn't physically removed, it's marked as dead (similar to tombstoning). That dead space isn't reclaimed until the page is reorganized.

Logical vs. Physical order divergence: Indexes start with data physically ordered on disk to match the logical sort order. After thousands of inserts and deletes, the physical order becomes random. A range scan that should read 10 sequential pages now reads 10 pages scattered across the disk.

The combined effect: your index might be using 3x more disk space than necessary, and range scans might perform 5x more I/O than they should.

How to detect it:

In PostgreSQL:

SELECT schemaname, tablename, indexname,
 pg_size_pretty(pg_relation_size(indexrelid)) as index_size
FROM pg_stat_user_indexes
ORDER BY pg_relation_size(indexrelid) DESC;

In SQL Server:

SELECT avg_fragmentation_in_percent, page_count
FROM sys.dm_db_index_physical_stats(DB_ID(), NULL, NULL, NULL, 'DETAILED')
WHERE avg_fragmentation_in_percent > 30;

If fragmentation exceeds 30%, it's time to rebuild.