Indexing
Creating lookup tables to speed up read queries, though this can slow down write operations
Overview
Database indexes are data structures that improve the speed of data retrieval operations. Like a book's index, they allow the database to find data without scanning every row.
Indexes trade write speed and storage space for dramatically faster reads. Choosing what to index is a critical performance optimization.
Key Concepts
B-Tree Index
Most common index type. Balanced tree structure. Good for range queries and equality searches.
Hash Index
Fast for equality searches (WHERE id = 123) but cannot do range queries. Used for exact matches.
Composite Index
Index on multiple columns. Order matters! Index on (lastName, firstName) works for queries on lastName alone, but not firstName alone.
Covering Index
Index contains all columns needed for a query. Database never touches the actual table (super fast).
How It Works
Without Index: SELECT * FROM users WHERE email = 'john@example.com'
- Scans entire table (Full Table Scan)
- 1 million rows = 1 million checks
- O(n) time complexity
With Index on email:
- B-tree lookup finds data in log(n) time
- 1 million rows = ~20 checks
- Returns row immediately
Cost:
- Index takes storage space
- Inserts/updates slower (must update index too)
- Trade-off: Fast reads, slower writes
Use Cases
Primary keys (always indexed)
Foreign keys for joins
Columns in WHERE clauses
Columns in ORDER BY
Columns frequently searched
Columns in JOIN conditions
Best Practices
Index columns used in WHERE, JOIN, ORDER BY clauses
Use EXPLAIN/EXPLAIN ANALYZE to see query execution plan
Don't over-index (diminishing returns, slower writes)
Composite indexes: order matters (most selective first)
Drop unused indexes (monitor index usage)
Consider partial indexes for large tables
Rebuild/reindex periodically to avoid fragmentation
Index foreign keys
Interview Tips
What Interviewers Look For
- •
Explain B-tree structure (most common index type)
- •
Discuss the read-write trade-off: indexes speed up reads, slow down writes
- •
Mention EXPLAIN command to analyze query performance
- •
Talk about when NOT to index: small tables, columns with low cardinality (few unique values)
- •
Explain covering indexes (index-only scans)
- •
Discuss composite indexes and column order importance
- •
Know O(log n) lookup time for indexed queries vs O(n) for full table scan