How Postgres Indexing Works Internally

Q: How is indexing done in Postgres?

A: Key points to cover:

• Postgres's default index type is the B-tree, which keeps keys sorted and supports equality and range queries (<, <=, =, >=, >) with O(log n) lookups.
• Postgres tables use heap storage (unordered by default), so a B-tree index maps a key value to a tuple's physical location (ctid); unlike some other databases, Postgres's primary key is not automatically a "clustered" index unless CLUSTER is explicitly run.
• Other index types: Hash (equality-only), GIN (good for arrays, JSONB, full-text search - inverted index), GiST (geometric/range types, nearest-neighbor), BRIN (block range index, very compact, good for naturally-ordered huge tables like time-series).
• MVCC implication: Postgres keeps multiple row versions (tuples) for concurrency; indexes can point to dead tuples until VACUUM cleans them up, which is why bloated indexes/tables need regular vacuuming.
• Composite indexes: column order matters - a multi-column B-tree index is only useful for queries that filter on a left-prefix of the indexed columns.