B-tree indexes

B-tree is what you get when you write CREATE INDEX foo ON table (col). It is a balanced multi-way tree where each node holds sorted keys and pointers. Lookups are O(log n). Range scans walk leaf pages in order. Postgres's B-tree is technically a B+tree variant (Lehman-Yao).

When to reach for it

• Equality: WHERE id = 5
• Range: WHERE created_at BETWEEN x AND y
• Prefix match: WHERE name LIKE 'yash%' (with text_pattern_ops or default if no collation)
• ORDER BY: index provides sort order for free
• Min/max: jumps to leftmost or rightmost leaf

When B-tree fails you

• Suffix match: LIKE '%yash' cannot use B-tree. Use a trigram GIN index.
• Full-text search: use GIN with tsvector.
• Multi-dimensional range (geo): use GIST.
• Array containment: use GIN.

Composite indexes and column order

An index on (a, b, c) is sorted by a first, then b within each a, then c. Useful for:

• WHERE a = ?
• WHERE a = ? AND b = ?
• WHERE a = ? AND b = ? AND c = ?
• WHERE a = ? AND b > ?
• WHERE a = ? ORDER BY b, c

Useless for:

• WHERE b = ? (cannot skip a)
• WHERE c = ?

Rule of thumb: most selective equality column first, then range column, then sort column.

Index-only scans

If your SELECT columns are all in the index, Postgres can answer without touching the heap. This requires the visibility map to say the page is all-visible (so we know all tuples in the index are live). Use INCLUDE columns to add non-key payload columns to the index leaf without affecting the sort.

CREATE INDEX idx_users_email ON users (email) INCLUDE (name, created_at);

The interview line

"B-tree is the default index in Postgres. It is a balanced tree with sorted keys, O(log n) lookups, range scans via sibling-linked leaves, and supports ORDER BY without a sort step. The cost is write amplification: every INSERT and UPDATE on indexed columns has to update the tree. Composite index column order matters because the index is sorted left-to-right."