Algocraft / System Design / Database Indexing

🌲

Database Indexing

Make queries 1000× faster by creating the right indexes

B-Tree Index Query Optimization O(log n) Lookup PostgreSQL / MySQL
SQL Query
SELECT * FROM users WHERE id = 4271;
📋 Table Scan
idnameemailagecity
Ready to query
🌲 B-Tree Index Structure
Ready
Execution Plan (EXPLAIN)
No Index
—
Full Table Scan · O(n)
—
B-Tree Index
—
Index Seek · O(log n)
—
Composite Index
—
Covering Index · O(log n)
—

Key Concepts

🎯 When to Index
  • Columns in WHERE clauses
  • JOIN columns (foreign keys)
  • ORDER BY / GROUP BY columns
  • Primary keys (always indexed)
⚖️ Trade-offs
  • Each index slows down INSERT/UPDATE
  • Indexes consume disk space
  • Too many indexes = optimizer confusion
  • LIKE '%prefix%' can't use B-Tree
🎓 Interview Tips
  • Covering index: all cols in index
  • Partial index: index a subset of rows
  • Cardinality matters: high = better index
  • Use EXPLAIN to verify index is used