What MySQL Index Interview Questions Reveal About B‑Tree, Hash, and Optimization

Index Concepts and Models

Indexes are data structures that allow MySQL to locate rows without scanning the whole table. In high‑traffic systems that generate millions of rows per day, proper index design is essential for performance.

Definition: An index stores a sorted representation of column values and pointers to the corresponding rows.

MySQL storage engines: InnoDB uses B+Tree as the default index structure; hash indexes exist but are limited to equality searches.

Hash vs. B+Tree

Hash indexes store key‑value pairs without order, support only equality predicates, and cannot be used for range scans or ordering.

B+Tree indexes are ordered multi‑way trees; they support range queries, sorting, and can be used for prefix matching in composite indexes.

Clustered and Covering Indexes

In InnoDB, the primary key is implemented as a clustered index: a B+Tree whose leaf nodes contain the entire row. A non‑clustered (covering) index is a B+Tree whose leaf nodes contain only the primary‑key values, allowing the index to satisfy a query without accessing the table.

Example of a covering index query:

SELECT key2 FROM covering_index_sample WHERE key1='keytest';

The optimizer can retrieve key2 directly from the index because the index already contains all columns referenced in the SELECT list and WHERE clause.

Composite Indexes and Left‑most Prefix Matching

When creating a multi‑column index, place the most selective or most frequently filtered columns first. MySQL can use the index for any leftmost prefix of the defined column list. For an index on (col1, col2, col3), queries that filter on col1, (col1, col2), or (col1, col2, col3) can all use the same index.

Index Condition Pushdown (ICP) and Query Optimization

MySQL 5.6 introduced Index Condition Pushdown, which pushes additional predicate evaluation (e.g., LIKE or >=) down to the storage engine. This reduces the number of rows that need to be transferred to the SQL layer.

Example:

SELECT * FROM people WHERE zipcode='95054' AND lastname LIKE '%etrunia%' AND address LIKE '%Main Street%';

With ICP enabled, MySQL first uses the zipcode index to locate candidate rows, then applies the LIKE conditions directly on the index entries. Rows that do not satisfy the conditions are discarded before being sent to the server, decreasing I/O and CPU usage.

The optimizer enumerates all feasible execution plans, estimates their costs (full‑table scan vs. various index usages), and selects the plan with the lowest estimated cost.

Practical Tips for Index Usage

Run EXPLAIN on queries to verify whether an index is being used and to see the estimated rows examined.

Covering indexes eliminate the need for a “back‑table” lookup, improving query latency.

An index may be ignored if the query does not satisfy the leftmost‑prefix rule, applies functions to indexed columns, or the optimizer estimates that a full scan is cheaper due to low selectivity.