B-Tree

Database 16 Sep 2026 5 min read

PostgreSQL B-Tree Deduplication Compresses Duplicate Keys

A PostgreSQL B-tree leaf page can hold many index tuples with identical key values. When deduplication is applicable, PostgreSQL can represent a group of those tuples as one posting-list tuple: the indexed key appears once, followed by a sorted array of heap tuple identifiers. This representation changes physical index density without changing the logical set of index entries. Each heap tuple remains individually addressable through its TID, while repeated key material occupies less leaf-page space.

PostgreSQL Database

Database 15 Sep 2026 5 min read

PostgreSQL B-Tree Skip Scan Repositions Index Searches

A multicolumn B-tree does not always require an equality condition on its first column to avoid reading the entire index. PostgreSQL can use skip scan to perform repeated targeted searches when a predicate constrains a later column and the planner estimates that repositioning will bypass enough index entries. Consider an index whose key order is (region, created_at): CREATE INDEX orders_region_created_at_idx ON orders (region, created_at); A query that filters only created_at has no explicit condition on region:

PostgreSQL Database

Database 15 Sep 2026 6 min read

PostgreSQL B-Tree Fillfactor Reserves Space Before Page Splits

A PostgreSQL B-tree leaf page has finite space for index tuples. When an incoming tuple belongs on a page that no longer has room, the access method must make space, and a page split can add another leaf page plus a new parent downlink. The fillfactor storage parameter controls how tightly leaf pages are packed at selected points in the index lifecycle, leaving capacity that later writes can consume. For B-tree indexes, PostgreSQL uses a default fillfactor of 90. A value below 100 deliberately exchanges denser initial storage for free space on leaf pages. That space is not a permanent reservation for a particular row or key. It is simply unused page capacity available to later index activity.

PostgreSQL Database

Database 14 Sep 2026 5 min read

PostgreSQL B-Tree Deduplication Packs Duplicate Keys

A PostgreSQL B-tree can represent several equal index keys with one physical key value followed by multiple heap tuple identifiers. This representation, called a posting-list tuple, reduces repeated key storage on leaf pages without changing the logical contents of the index. The mechanism matters most when an indexed value occurs many times. An index on a low-cardinality status column, for example, may contain thousands of entries whose key is pending. Logically those entries still identify separate table tuples. Physically, B-tree deduplication can pack groups of equal keys so the key datum is stored once for a group of TIDs.

PostgreSQL Database