Postgres Indexing Internals

Problem How is indexing done in Postgres?

Be ready to discuss

• The default index type is B-tree: keys stay sorted, giving O(log n) lookups plus range queries (<, <=, =, >=, >), ORDER BY support, and prefix matching.
• Heap storage: Postgres tables are unordered heaps, so an index maps a key to a tuple's physical location (ctid).
• No automatic clustering: unlike InnoDB, a Postgres primary key is not a clustered index - CLUSTER reorders physically but is a one-off, not maintained.
• Hash indices: equality only, no range scans; WAL-logged and crash-safe only since Postgres 10.
• GIN: an inverted index for arrays, JSONB, and full-text search - built for many-values-per-row columns.
• GiST: geometric and range types plus nearest-neighbour searches; SP-GiST for non-balanced partitioned structures.
• BRIN: block range indices storing min/max per block range - tiny and extremely effective on naturally-ordered huge tables like time-series, useless on randomly-ordered data.
• MVCC implications: multiple row versions mean indices can point at dead tuples until VACUUM reclaims them, which is why bloat and autovacuum tuning matter.
• Index-only scans and the visibility map: why they only work when the pages are marked all-visible, tying performance back to vacuum.
• Composite indices and the leftmost-prefix rule, plus partial indices (WHERE clause) and expression indices for computed lookups.