PostgreSQL B-tree internals analysis explains index bloat and VACUUM behavior

A technical deep dive into PostgreSQL storage internals reveals how B-tree index pages differ from standard heap pages. While heap pages act as unordered collections of row versions, B-tree pages are structured, sorted, and linked to sibling pages, which fundamentally changes how they handle deletions.

The analysis demonstrates that when rows are deleted, the index entries are marked as dead, but the physical pages remain allocated in the file. Even after running a VACUUM operation to remove dead item identifiers, the B-tree pages are not deallocated, resulting in a sparse index structure that consumes significant disk space despite low data density.

B-tree Page Structure and VACUUM Limitations

• Page Architecture: B-tree pages utilize an 8KB skeleton consisting of a 24-byte header, line pointers, and tuples packed from the bottom up, but unlike heap pages, they are sorted and linked to sibling pages.
• Deletion Mechanism: A DELETE operation only updates the xmax on the heap tuple; it does not immediately modify the index, leaving the index entries pointing to dead heap tuples until a vacuum occurs.
• VACUUM Behavior: During the index scan phase of VACUUM, dead entries are removed from the B-tree pages, but the pages themselves are left in place, which prevents the reclamation of disk space for scattered deletions.
• Index Bloat: While deleting a specific key range can cause entire pages to be removed from the tree, scattered row deletions result in leaf pages that remain in the file but are mostly empty, leading to high fragmentation and low leaf density.

Why it matters

This technical insight is critical for database administrators managing large-scale PostgreSQL deployments, as it clarifies why standard VACUUM processes fail to reduce index size. Understanding this behavior is essential for planning index maintenance, such as REINDEX operations, to reclaim storage and maintain performance in high-churn environments.