B-Tree Index Fragmentation
degradedSummary
When frequent update and delete operations leave B-tree index pages partially filled, index scans must traverse more pages than the data density justifies, producing read amplification. Storage utilization inflates, index cache hit rates fall, and query latency for index-range scans increases progressively as the table accumulates write churn. The degradation is gradual and often unnoticed until query plans change or periodic REINDEX maintenance is missed.
Description
B-tree indexes store key-pointer pairs in sorted leaf pages with a target fill factor (typically 70–90% for write-heavy tables). When rows are deleted, their index entries are marked as dead but the pages remain allocated. When rows are updated, the old index entries are marked dead and new entries are inserted (potentially into different pages). Over time, pages fill with dead entries and the live-entry density drops. A page that once held 200 live entries may contain only 40, with 160 dead entries consuming space but contributing no useful data.
PostgreSQL VACUUM reclaims dead heap tuples but does not restructure index pages. The dead index entries are marked as reusable for future inserts, but the page itself is not compacted or merged with adjacent low-density pages. An index that was 80% full after initial build can degrade to 30–40% effective density after a year of update-heavy workload. A range scan that should read 10 index pages now reads 25 because 60% of each page is dead or empty.
The performance impact is most visible on range queries (WHERE created_at BETWEEN ... AND ..., ORDER BY id LIMIT 100) that must traverse many contiguous index pages. Random point lookups are less affected because they read only one leaf page. For a table with 10 million rows and 40% index density, a range query covering 100,000 rows reads 250,000 index entries across 2500 pages instead of the 1000 pages it would need with a fresh index. This extra 1500 pages of I/O adds 15–150ms to the query depending on storage subsystem and buffer cache state.
Fragmentation also inflates index storage size, reducing effective shared_buffers cache efficiency. An index that should consume 2 GB occupies 5 GB on disk; only 40% of cached pages contain useful entries. Write-heavy workloads on tables with multiple indexes amplify this problem: each index fragments independently, and the cumulative effect on buffer pool efficiency is additive.
Characteristics
Triggers
- ·High-frequency deletes on an indexed column (soft-delete patterns updating status fields)
- ·Update-heavy workload on indexed columns where updated values span many different index pages
- ·Bulk delete operations removing large fractions of a table without subsequent REINDEX
- ·Time-series tables with rolling retention deletes that continuously remove old rows from the beginning of the index
- ·Missing or infrequent REINDEX CONCURRENTLY maintenance on high-churn tables
Detection Signals
Mitigation Strategies
Run REINDEX CONCURRENTLY index_name to rebuild the index to full density without blocking reads or writes. The concurrent form builds a new index alongside the existing one and swaps them atomically. Duration depends on table size (estimate 1 hour per 50 GB of table data). Schedule during low-traffic windows and monitor index build progress via pg_stat_progress_create_index. Requires PostgreSQL 12+ for CONCURRENTLY support on REINDEX.
Create indexes on frequently-updated columns with a lower fill_factor (60–70 instead of default 90). This leaves reserved space on each page for future insertions from HOT (Heap Only Tuple) updates, reducing page splits and dead-entry accumulation. Apply when creating the index: CREATE INDEX idx_name ON table (col) WITH (fillfactor = 70). Rebuilding existing indexes with a new fill_factor requires REINDEX.
For status-column indexes where most queries filter on a small subset of values (WHERE status = active, which is 5% of rows), create a partial index: CREATE INDEX idx_active ON table (id) WHERE status = 'active'. The partial index is smaller, fragments more slowly, and is more cache-efficient. Rows with status != active are excluded entirely, reducing the write amplification from status updates.
Recovery Steps
- 1.Query pg_stat_user_indexes and pg_class to identify bloated indexes (ratio of pg_relation_size to expected size > 2x)
- 2.Run REINDEX CONCURRENTLY on the most bloated indexes during off-peak hours
- 3.Monitor query p99 latency during and after rebuild to confirm improvement
- 4.Add pg_bloat_check or pgstattuple-based monitoring to catch future fragmentation before it becomes severe
- 5.Schedule REINDEX CONCURRENTLY as a quarterly maintenance job for all high-churn table indexes
Estimated recovery time: 1–6 hours for REINDEX CONCURRENTLY to complete on large tables (1–50 GB index size). Query latency improvement is immediate after the new index replaces the old one.
Affected Systems
Patterns
Technologies
Basis
B-tree fragmentation mechanics are well-documented in PostgreSQL and MySQL internals documentation; fill factor and REINDEX CONCURRENTLY behavior is empirically verified; latency impact estimates are conservative ranges based on common production system observations