Core idea
A database without indexes on large tables is a book without a table of contents. Every query scans every row. Indexes make reads fast at the cost of slower writes and more storage.
Mental model
A phone book (sorted by name) is an index. If you want ‘Sarah Smith’, you go to S, then Sm, then find Sarah. Without it, you read every name. A B-tree index in a database does the same thing hierarchically. A hash index is a lookup table: key → pointer. O(1) but only for exact matches.
Why it matters
- The difference between 100ms and 10s queries is often one missing index
- Over-indexing slows writes — every write must update every index
- Understanding indexes lets you design schemas that are actually fast
What to know
- B-tree index: default, supports range queries (>, <, BETWEEN), sorted scans
- Hash index: exact match only, O(1), no ranges — useful for equality lookups (most databases still use B-trees for primary keys)
- Composite index: (user_id, created_at) — order matters! Left-prefix rule
- Covering index: index contains all columns a query needs — no table lookup
- Inverted index: used in full-text search — maps words to documents
Common traps
- Indexing every column ‘just in case’ — doubles write overhead
- Wrong column order in composite index — query can’t use it
- Not indexing foreign keys — joins become table scans
Recognise it
Recognition trigger: Whenever you define a table, immediately think — what queries will run? What columns are in WHERE, JOIN, ORDER BY? Those are your index candidates. Then prune: which are not worth the write cost?
Practice question
You have a users table with 100M rows. Queries by email are slow. What do you do? What’s the tradeoff?
Go deeper
- Indexes (opens in a new tab) · PostgreSQL documentation
- Chapter 3: Storage and Retrieval · Designing Data-Intensive Applications (Kleppmann), book