Indexing
Why Indexes Exist
An overview of book indexes and why databases need lookup structures.
1. Introduction
An index is a data structure that enables the database to find rows without scanning the entire table. Just like a book's index lets you jump to the right page instead of reading every page, a database index lets the query planner locate data in O(log N) time instead of O(N). Without indexes, every query on a million-row table would require reading all million rows.
2. Why It Matters
- Query speed: A well-placed index can turn a 30-second sequential scan into a 2ms index lookup — a 15,000x improvement.
- Scalability: Without indexes, query time grows linearly with table size. With indexes, it grows logarithmically — a billion-row table is only ~30 lookups deep.
- JOIN performance: Foreign key columns without indexes cause nested loop joins to degrade to O(N×M). Indexes on FK columns enable efficient index-based joins.
- Sorting: B-tree indexes store data in sorted order, enabling the planner to skip expensive sort operations for ORDER BY queries.
3. Real-World Analogy
Imagine a 1,000-page textbook. To find all mentions of "photosynthesis," you could read every page (sequential scan) or use the alphabetical index at the back, which points you to pages 234, 567, and 891 (index scan). The index took space to create and must be updated when pages change — but lookups are nearly instant.
4. How It Works
5. Internal Architecture
6. Visual Explanation
7. Practical Example
8. Common Mistakes
Indexing every column
Each index slows down INSERT/UPDATE/DELETE (must update all indexes). Index only columns used in WHERE, JOIN ON, ORDER BY, and GROUP BY. Avoid indexing boolean columns, low-cardinality columns, or columns you never filter on.
Ignoring index maintenance
Indexes become bloated over time due to dead tuples. Run REINDEX CONCURRENTLY periodically on high-churn indexes to reclaim space and improve performance.
9. Quick Quiz
Q1: What's the time complexity of a B-tree index lookup?
Answer: O(log N). For a B-tree with 1 billion rows and fanout of 300, it takes about 3-4 page reads to find the target leaf node.
10. Scenario-Based Challenge
Challenge: Index Audit for a 500M Row Table
Your orders table has 500M rows and 12 indexes. Write queries to: (1) identify unused indexes (check pg_stat_user_indexes), (2) find duplicate indexes (same columns, different names), (3) calculate total index size vs table size, (4) recommend which indexes to drop.
11. Debugging Exercise
This index exists but isn't being used. Why?
Issue: The query applies LOWER() to the indexed column, which changes the value. The B-tree stores original values, not LOWER(name). Fix: create a functional index: CREATE INDEX idx_users_lower_name ON users(LOWER(name)).
12. Interview Questions
Q1: When does the query planner choose a sequential scan over an index scan?
A: When the query returns a large percentage of the table (>10-15%), when the table is very small (fits in a few pages), or when the index is too bloated. Sequential scans read pages sequentially (fast I/O); index scans jump randomly (slow I/O).
Q2: What is an index-only scan?
A: When all columns needed by the query are available in the index itself, PostgreSQL skips the heap read entirely. This is the fastest scan type. Enable it with covering indexes that include all queried columns.
13. Production Considerations
- CREATE INDEX CONCURRENTLY: Always use this for production tables. Regular CREATE INDEX locks the table for writes during creation, which can cause downtime on large tables.
- Monitor unused indexes: Query
pg_stat_user_indexesto find indexes with zero scans. Each unused index adds write overhead without benefit — drop them. - Index bloat: High-update tables cause index bloat (dead entries). Schedule
REINDEX CONCURRENTLYor ensure autovacuum is properly configured. - Disk space: Indexes can consume more disk than the table data itself. Budget accordingly and regularly audit index-to-data ratio.