Index Types

B-tree for ordered range queries, hash for equality, GIN/GIST for full-text and arrays, BRIN for huge sorted tables — pick by query shape.

What it is

An index is an auxiliary data structure that speeds up lookups at the cost of write overhead and storage. B-trees are the default in every relational engine — they support equality and range queries on sorted keys. Hash indexes are O(1) for equality but useless for ranges. Postgres-specific GIN (Generalized Inverted Index) supports full-text and JSONB array containment; GIST supports geometric and full-text with custom operators; BRIN (Block Range Index) is tiny and great for large naturally-sorted tables. Partial indexes index only rows matching a WHERE clause; covering (INCLUDE) indexes let queries be answered from the index alone without hitting the heap.

Why senior interviewers ask

Most engineers create indexes by guessing. Senior interviewers ask how you'd index a specific query plan to see if you can read EXPLAIN output and match the index to the query.

Key points

B-tree: O(log N) lookup, O(log N) range start + sequential scan; works for equality, range, ORDER BY, LIKE 'prefix%'.
Hash index: O(1) equality only; rarely worth using over B-tree in Postgres (B-tree is nearly as fast).
GIN: inverted index — great for full-text search (tsvector), JSONB containment (@>), arrays.
GIST: generalized search tree — geometric data (PostGIS), trigram search (pg_trgm), range types.
BRIN: stores min/max per block range; tiny on disk; only useful when data is naturally sorted (time-series).
Partial index: WHERE clause limits the index to a subset — smaller, faster, often the right call for sparse predicates.
Covering index (INCLUDE): non-key columns stored in the index for index-only scans.
Every index slows writes by O(log N) and consumes disk — don't over-index.

Real systems

PostgreSQL B-tree — Default index; supports equality, range, ORDER BY, prefix LIKE; multi-column with leftmost-prefix rule.

PostgreSQL GIN on JSONB — Index JSONB columns for containment queries: WHERE data @> '{"status": "active"}'.

PostgreSQL BRIN on time-series — Tiny index (kilobytes for billion-row tables) on timestamp columns where data is append-ordered.

MySQL InnoDB clustered index — Primary key IS the table — rows stored in PK order; secondary indexes point to PK, not row pointer.

Elasticsearch inverted index — Full-text search via term-to-document inverted index with TF-IDF/BM25 scoring.

Interview probe

'EXPLAIN says Seq Scan instead of Index Scan on a query that has an index. Why?' Answer: planner thinks seq scan is cheaper (small table, low selectivity, or stale statistics). Run ANALYZE; check selectivity; consider partial or covering index.

Dive deeper

Multi-column B-tree indexes follow the leftmost-prefix rule: an index on (a, b, c) can serve queries filtering on a, on a+b, or on a+b+c — but NOT queries filtering on b or c alone. This is the single most common source of 'why isn't my index being used' confusion. The fix is either reordering the index columns to match query patterns or adding a separate index. Also know that index-only scans (covering indexes) bypass the heap entirely and are the fastest read path Postgres can offer.

All database concepts