Indexing & Performance Engineering
Mastering B-Trees, query optimization, the EXPLAIN planner, and the architectural tradeoffs of indexing.
The Physical Reality of Disk I/O
When a database receives a query like SELECT * FROM users WHERE email = 'test@example.com';, the naive execution method is a Sequential Scan (or Full Table Scan). The database engine must read every single row from the disk into memory, checking if the email matches.
If the table has 10,000 rows, this happens instantly. If the table has 100 million rows, the CPU must wait for the storage drive to physically fetch gigabytes of data. This disk I/O bottleneck is the primary cause of API latency and system timeouts.
The B-Tree Index
To avoid sequential scans, engineers create Indexes. An index in a database is fundamentally identical to an index at the back of a textbook: it is a separate, highly organized data structure containing the sorted keys (e.g., email addresses) and a pointer to the physical location of the full row on the disk.
Most relational databases use a Balanced Tree (B-Tree) data structure for indexing.
Because the B-Tree remains mathematically balanced, traversing it to find a specific record takes $O(\log N)$ time. Even in a table with a billion rows, the database only needs to traverse a handful of nodes (often already cached in RAM) to find the exact disk block containing the data.
The Write Penalty: Why Over-Indexing Kills Systems
A common anti-pattern among junior engineers is to put an index on every single column to “make read queries faster.”
This destroys system performance. An index is a physical data structure. Every time you execute an INSERT, UPDATE, or DELETE, the database must not only write the data to the main table, but it must also synchronously traverse, update, and rebalance every single index attached to that table.
Composite Indexes and the Left-Prefix Rule
When queries filter on multiple columns (e.g., WHERE last_name = 'Smith' AND first_name = 'John'), engineers use Composite Indexes—an index spanning multiple columns.
However, composite indexes are bound by the Left-Prefix Rule. An index on (last_name, first_name) sorts the tree first by last_name, and then by first_name within that bucket (exactly like a telephone book).
- A query for
last_name = 'Smith' AND first_name = 'John'will use the index. - A query for
last_name = 'Smith'will use the index. - A query for
first_name = 'John'WILL NOT use the index. The database cannot skip the primary sorting column, forcing a sequential scan.
Visibility: The EXPLAIN Command
You do not have to guess if your query is performant. Every modern relational database provides the EXPLAIN command (or EXPLAIN ANALYZE in PostgreSQL).
Prepending this command to your query instructs the Query Optimizer to output its physical execution plan without (or before) actually returning the data. It reveals exactly whether it chose a Seq Scan, an Index Scan, or a Hash Join, along with the estimated computational cost.