Indexing Strategies

Problem statement (interviewer prompt)

A 100M-row table needs lookups by primary key, range queries by timestamp, fuzzy search on a text column, and spatial nearest-neighbour on lat/lng. Pick the right index type for each access pattern and explain the trade-offs.

A database index is a secondary data structure that trades write cost (and disk) for read speed. Different shapes solve different problems.

Source: Wikimedia Commons. CC BY-SA 3.0.

flowchart LR
  subgraph PointLookup[Point lookup]
    BT[B-tree] --- HSH[Hash]
  end
  subgraph Range[Range queries]
    BT2[B-tree] --- BRIN[BRIN]
  end
  subgraph Text[Text]
    FT[Full-text]
    GIN[GIN inverted]
  end
  subgraph Geo[Spatial]
    GiST
    RTree[R-tree]
  end
  subgraph Vector[Embedding]
    HNSW
    IVF
  end

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class BT,HSH,BT2,BRIN,FT,GIN,GiST,RTree,HNSW,IVF datastore;

Pick by access pattern; one table often needs several indexes.

An index is a secondary data structure that the database maintains so reads can find rows without scanning the whole table. Each index type targets a specific access pattern.

B-tree (the default)

flowchart TB
  Root[Root<br/>50, 100] --> M1[1..49]
  Root --> M2[50..99]
  Root --> M3[100..]
  M1 --> L1[leaf 1..15]
  M1 --> L2[leaf 16..49]
  M2 --> L3[leaf 50..75]
  M2 --> L4[leaf 76..99]

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class Root,M1,M2,M3,L1,L2,L3,L4 datastore;

Strengths: point lookups, range scans, equality, inequality, sort order. Almost every DB's default. O(log N) lookup. See storage-engines-lsm-btree.

Hash

Bucketed by hash(key). O(1) equality lookup; no range support.

• Postgres: USING hash (was unlogged historically; safe since 10).
• MySQL InnoDB: adaptive hash index for hot pages.
• Use when range scan never needed and equality is the hot path.

Inverted / GIN

Maps a token to the list of rows containing it.

token:apple  -> rows [3, 17, 92]
token:banana -> rows [3, 88]

• Powers full-text search and JSON containment (@>).
• Postgres GIN indexes tsvector, jsonb, arrays.

GiST and SP-GiST

Generalised search tree: a B-tree-like skeleton with user-defined splitting predicates. Used for ranges, geometry, text similarity (pg_trgm), nearest-neighbour. R-tree for spatial is a GiST instance.

BRIN (block-range)

Stores min/max per page range, not per row. Skips pages whose range doesn't overlap the query. Tiny index, massive table:

• Append-only data correlated with insertion order (timestamps, sequence ids).
• 1 GB index covers 1 TB table.
• Returns false positives; not for selective queries.

Vector / ANN

HNSW, IVF, ScaNN. See vector-databases.

Composite (multi-column)

CREATE INDEX ix_orders_user_created ON orders(user_id, created_at);

Query patterns this serves:

Query	Uses index?
WHERE user_id = ?	yes
WHERE user_id = ? AND created_at > ?	yes
WHERE created_at > ? (alone)	NO (leftmost column missing)

Order matters: put the equality column first, then the range column.

Covering / index-only scans

CREATE INDEX ix_orders_covering ON orders(user_id) INCLUDE (total, status);

If the index contains all columns the query needs, the DB never touches the heap. Massive speedup for hot read paths.

Partial / filtered indexes

CREATE INDEX ix_active_orders ON orders(created_at)
  WHERE status = 'OPEN';

Only rows matching the predicate are indexed. Smaller, faster, only for the relevant slice of data.

Functional / expression indexes

CREATE INDEX ix_lower_email ON users(lower(email));
SELECT ... WHERE lower(email) = 'a@b.com';

Index expressions so queries that match the expression hit the index.

Cost model

Every index pays:

• Write cost: every INSERT/UPDATE/DELETE updates the index.
• Storage: typically 10-30% of the table size; vector indexes much more.
• Maintenance: vacuum, reindex, bloat management.

Rule of thumb: an index on a column used in ≤1 query type is usually a loss. Track usage with pg_stat_user_indexes or sys.dm_db_index_usage_stats.

Choosing per workload

Access pattern	Index
Primary key lookup	B-tree (clustered if available)
Equality on column	B-tree or hash
Range scan / sort	B-tree
Substring search	GIN with pg_trgm
Full-text	GIN on tsvector (Postgres), inverted index (Elasticsearch)
Geospatial	GiST / R-tree / S2 / Geohash
Time-series append-only	BRIN
JSON containment	GIN on jsonb
Embedding similarity	HNSW or IVF

How indexing connects

flowchart TB
  IDX((Indexing<br/>strategies))
  SE[Storage engines LSM / B-Tree<br/>disk-layer impl]
  SRCH[Search internals<br/>inverted indexes]
  VEC[Vector databases<br/>ANN family]
  QO[Query optimizer<br/>consumes index stats]
  SE --> IDX
  SRCH --> IDX
  VEC --> IDX
  IDX --> QO

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class IDX service;
    class SE,SRCH,VEC,QO datastore;

Glossary & fundamentals

Tag	Concept	What it is	Page
HLD	Storage engines LSM B-Tree	the disk-layer index implementation	storage-engines-lsm-btree
HLD	Search internals	inverted index used in search	search-internals
HLD	Vector databases	ANN index family	vector-databases
HLD	Query optimizer	the consumer of index statistics	query-optimizer

Quick reference

Index → workload

Workload	Index
PK lookup	B-tree (clustered)
Equality	B-tree / hash
Range / sort	B-tree
Substring	GIN + trigram
Full-text	GIN on tsvector (PG), inverted (ES)
JSON containment	GIN on jsonb
Geo nearest	GiST / R-tree / S2 / geohash
Append-only time series	BRIN
Vector similarity	HNSW / IVF

Composite rule

Leftmost column must appear in WHERE. Order: equality first, range second.

Covering / INCLUDE

Include all SELECTed columns in the index → index-only scan.

Partial

WHERE status='OPEN' → smaller, faster, only relevant slice.

Functional

CREATE INDEX ix ON users(lower(email)) → match WHERE lower(email)=?.

Cost

• Write: each insert/update/delete updates every applicable index
• Storage: 10-30% of table typical; vector indexes much higher
• Maintenance: vacuum, reindex, bloat

Watch-outs

• Unused indexes (audit pg_stat_user_indexes)
• Too many indexes (> 5-7) → write tax
• Wrong leading column on composite
• Bloat after heavy updates → reindex

Refs

• Winand - Use The Index, Luke!
• PostgreSQL index types docs
• Petrov - Database Internals

FAQ

What is a database index?

An index is a secondary structure that lets the query planner find rows without scanning the whole table. It trades extra writes and disk for much faster reads.

B-tree vs hash index, when use which?

B-tree handles range and ordered scans. Hash supports point lookups only. Most general indexes are B-tree because equality is just a special case of range.

When should I use a BRIN index?

BRIN works for very large, naturally ordered columns like timestamps, where storing min and max per block is enough to skip most of the table.

What is a GIN index used for?

GIN stores an inverted list per token, ideal for full-text search, JSON containment, and array membership queries. It is heavier to write than B-tree.

What is a covering index?

A covering index includes all columns the query reads, so the planner can answer the query from the index alone without touching the table heap.

Related Topics

• Storage Engines LSM B-Tree: the engine-level structures indexes are built on
• Search Internals: inverted indexes for text search
• Vector Databases: ANN indexes for embeddings

Further reading

• Book - Markus Winand - Use The Index, Luke!
• Doc - PostgreSQL - Index types
• Blog - Cloudflare - Postgres BRIN indexes for time series
• Book - Database Internals - Alex Petrov