Indexes & Query Optimization in System Designing

A Database Index is a specialized data structure (typically stored separate from the main table) that acts like an index at the back of a textbook. Instead of scanning every single row in a table from scratch (a Full Table Scan ), the database uses the index to find the exact location of the requested data almost instantly. In system design, indexing is the most impactful way to optimize the performance of the data tier. However, it introduces a classic architectural trade-off: it speeds up reads, but slows down writes. 1. The Core Trade-off: Read Speed vs. Write Speed Why Reads Get Faster: Without an index, finding a user by email ( WHERE email = 'alice@example.com' ) requires the database to look at every single block of data on the disk, resulting in an time complexity of $O(N)$ . With an index, the search complexity drops to $O(\log N)$ or $O(1)$ . Why Writes Get Slower: Whenever you execute a INSERT , UPDATE , or DELETE query, the database cannot just write the data to the main table and move on. It must also recompute and update the underlying index data structure to keep it synchronized. If a table has 5 different indexes, a single insert triggers 6 distinct write operations. 2. Common Index Data Structures The underlying data structure determines how an index searches and organizes your data. A. B-Tree (Balanced Tree) — The Default A self-balancing search tree optimized for systems that read and write large blocks of memory. How it works: It keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. Best for: Equality lookups ( = ) and Range Queries ( > , < , BETWEEN ). Because the data is sorted, finding all users created between two dates is incredibly fast. B. Hash Index How it works: Uses a hash function to map column values to specific buckets. Best for: Exact equality lookups only ( WHERE id = 50 ). It offers an ultra-fast $O(1)$ lookup time. The Flaw: It is completely useless for range queries or partial matching ( LIKE 'Ali%' ), because hashes are inherently unordered. 3. Composite Indexes (Multi-Column) A Composite Index is an index built on multiple columns simultaneously (e.g., an index on both [last_name, first_name] ). The Left-to-Right Rule (Prefix Rule): The order of columns inside a composite index matters completely. The database sorts the index by the first column, and then by the second column within matches of the first. An index on (last_name, first_name) can be used to accelerate a search for just last_name . It cannot be used to accelerate a search for just first_name , because the data is not globally sorted by first name. 4. Execution Analysis: EXPLAIN and ANALYZE When writing complex queries, you should never guess whether your indexes are working. You can use the EXPLAIN and EXPLAIN ANALYZE commands in SQL (PostgreSQL, MySQL) to see exactly how the database engine intends to execute your query. EXPLAIN : Shows the execution plan chosen by the database query planner without running the query. It highlights estimated costs and whether it will use an Index Scan or fall back to a slow Seq Scan (Sequential Scan) . EXPLAIN ANALYZE : Actually executes the query in a safe sandbox environment. It outputs the real execution times, memory usage, and number of loops alongside the plan, allowing you to catch discrepancy errors between estimated and actual costs. SQL -- Example usage in PostgreSQL EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'alice@example.com'; 5. System Design Takeaway When designing data architectures: Index foreign keys: You almost always perform joins on foreign keys ( user_id , order_id ). These should always be indexed. Avoid over-indexing: Do not blindly add an index to every single column. It consumes significant disk space and will choke your write throughput on high-traffic write systems. Low Cardinality Columns: Do not index columns with very few unique values (e.g., a boolean is_active column). The database optimizer will often ignore the index and run a full scan anyway.