Understanding MySQL Indexes: How They Enable Near‑Second Queries on 200 Million Rows

During a recent interview, a candidate was asked why MySQL can retrieve a single row from 200 million records in less than a second when using an index, while a full table scan takes about 23 days.

MySQL indexes are data structures that allow the storage engine to locate rows quickly, similar to the alphabetical lookup in a phone contacts list. Without an index, the database performs a full‑table scan (O(N)), reading each row sequentially; with an index, it uses a balanced tree or B‑tree (O(log N)) to jump directly to the target rows.

Example without index:

Query: select*from User where ID=4 The engine scans every page and record, resulting in roughly 20 billion ms (≈200 0000 seconds) for 200 million rows, i.e., about 23 days.

Example with index:

Using a B‑tree index, the same query requires only about 40 lookups, completing in under one second. The time complexity drops to O(log N), dramatically improving performance as data volume grows.

Key advantages of indexes include:

Significantly faster query execution by quickly locating rows.

Reduced I/O through fewer scanned rows, improving sorting and grouping.

Enforcement of uniqueness via unique indexes.

Additional constraints for data integrity.

However, indexes also introduce drawbacks:

Additional storage space consumption.

Increased overhead for INSERT, UPDATE, DELETE operations as indexes must be maintained.

Index creation and maintenance time grows with data size.

In practice, the decision to add an index should weigh these pros and cons against specific query patterns; very small tables may benefit more from full scans, and columns with many duplicate values gain little from indexing.

Overall, mastering MySQL indexes is essential for both performance optimization and success in technical interviews.