B-tree indexes

For DBAs and operators

Structure

Block 0 is the metapage; it records the root block and the tree level. Every non-rightmost page has a high key (upper bound) and a right-link to its sibling. Internal pages hold separator keys and downlinks; leaf pages hold index tuples with heap TIDs (block, line pointer). This is the Lehman & Yao design: a reader that arrives at a page that was just split simply follows the right-link, so searches never need to lock the whole path.

CREATE EXTENSION pageinspect;
SELECT root, level, allequalimage FROM bt_metap('my_idx');
SELECT itemoffset, ctid, itemlen, htid, cardinality(tids) AS n_tids
  FROM bt_page_items('my_idx', 1) LIMIT 5;

Page splits and fillfactor

When a leaf has no room, it first tries to free space: delete entries already marked LP_DEAD by earlier index scans (simple deletion), then bottom-up deletion (only for inserts flagged "index unchanged", see below, or unique-index inserts that met a duplicate), then deduplication. Only then does it split. A normal split moves about half the data to a new page; a split of the rightmost leaf (ever-increasing keys like sequences or timestamps) leaves the left page fillfactor full (90 by default for B-trees) so sequential inserts produce dense pages. CREATE INDEX and REINDEX also fill leaves to fillfactor. Lower it (WITH (fillfactor = 70)) only for indexes with many random inserts into existing ranges.

Deduplication (PostgreSQL 13+)

Equal keys are merged into one posting list tuple: the key stored once, followed by a sorted array of TIDs. On inserts it happens lazily, only when a leaf would otherwise split; CREATE INDEX and REINDEX deduplicate while building. It is controlled by the deduplicate_items storage parameter (on by default). It is not used for numeric, jsonb, float4/float8, container types (arrays, composites, ranges), nondeterministic collations or indexes with INCLUDE columns; bt_metap().allequalimage tells whether it is possible. Indexes created before 13 need a REINDEX after pg_upgrade to use it.

Bottom-up deletion (PostgreSQL 14+)

An UPDATE that cannot be HOT (see HOT updates) inserts a new entry into every index, even ones whose key did not change. The executor passes an "index unchanged" hint for those. When such an insert hits a full leaf, nbtree visits the heap pages behind the duplicate entries and deletes the entries for versions that are dead to everyone, before considering a split. This stops "version churn" bloat between VACUUM runs.

Watching bloat and usage

SELECT indexrelname, idx_scan, idx_tup_read, idx_tup_fetch,
       pg_size_pretty(pg_relation_size(indexrelid))
  FROM pg_stat_user_indexes ORDER BY pg_relation_size(indexrelid) DESC;

CREATE EXTENSION pgstattuple;
SELECT avg_leaf_density, leaf_fragmentation FROM pgstatindex('my_idx');

Index pages are only reused after VACUUM marks them deleted and they become safe to recycle, so an index rarely shrinks by itself. REINDEX INDEX CONCURRENTLY rebuilds a bloated index without blocking writes.