Explain database indexes, the classic data structure, and write-heavy trade-offs

WHAT THIS TESTS: Whether you see indexing not as a magic speed button but as a physical data structure with concrete read, write, and storage costs. At the senior level, interviewers want you to connect the logical concept of fast lookups to the mechanical reality of disk I/O, tree rebalancing, and write amplification.

A GOOD ANSWER COVERS: First, the definition: an index is a separate data structure that maps column values to row locations so the engine can avoid scanning every row. Second, the classic structure: B-Trees, specifically B+ Trees in most systems, because they keep data sorted, support O(log N) lookups, range scans, and sequential disk access, and self-balance with minimal reorganization. Third, the write-heavy trade-offs: every write to the table likely requires updating every index on that table, which means additional random I/O, tree node splits and merges, and WAL or transaction log overhead. Fourth, storage cost: the index itself consumes disk space, sometimes comparable to or larger than the table for wide or numerous indexes. Fifth, the nuance that read replicas or caching do not eliminate the primary node write penalty.

COMMON WRONG ANSWERS: Saying the classic structure is a binary search tree rather than a B-Tree, which ignores the page-oriented reality of disk storage. Claiming indexes only slow down inserts while forgetting updates and deletes. Asserting that indexes always improve performance without mentioning that too many indexes can degrade write throughput by an order of magnitude. Confusing an index with a materialized view or table partitioning. Saying hash indexes are the classic answer without acknowledging their limitation with range queries.

LIKELY FOLLOW-UPS: How would you choose which columns to index on a write-heavy table? When would a covering index change the trade-off? How do composite indexes differ from multiple single-column indexes in terms of write amplification? What is the difference between a clustered and a non-clustered index? How do LSM trees change this calculus?

ONE CONCRETE EXAMPLE: Consider a user events table with ten million rows and five secondary indexes. Adding a single event row requires one table write plus five index writes. If each index update triggers a random 4 KB page read-modify-write on disk, that is roughly 24 KB of random I/O for one logical insert. At one thousand writes per second, the disk must sustain 24 MB per second of random writes just for indexing overhead, which can saturate IOPS budget before the table data itself becomes the bottleneck.