MySQL Indexes: Master B+Tree Fundamentals to Nail Interview Questions

B+Tree Query Efficiency

Many think an index is merely a "directory" for a table, but a compelling interview answer describes the query path. In a B+Tree, only leaf nodes store actual row data while internal nodes hold index keys. This design keeps the tree height low—typically three to four levels for tens of millions of rows—so a lookup requires at most three disk I/O operations.

For example, to find id = 15, the search starts at the root node [1,18,36], moves left to the second‑level node [1,6,12], then proceeds right to the leaf node [12,15,17] where the key is found in three steps.

Why B+Tree Instead of Other Structures

Interviewers often follow up with "Why not use a B‑tree, binary tree, or hash table?" The answer is intuitive:

B‑tree stores data in internal nodes, reducing the number of keys per node, increasing tree height, and causing more I/O.

Binary trees have only two branches per node, giving a search complexity of O(log N). B+Tree nodes can hold hundreds of keys (d > 100), yielding O(log₁₀₀ N), an order‑of‑magnitude improvement.

Hash tables provide O(1) equality lookups but cannot handle range queries, which are common in real‑world WHERE clauses such as price > 100.

Thus, B+Tree uniquely supports equality, range, and ordered queries.

Five Common Index Failure Scenarios

Building an index does not guarantee performance; the optimizer may still choose a full table scan if the index cost exceeds a sequential scan. The five typical pitfalls are:

Leading wildcard in LIKE '%keyword' prevents the B+Tree from determining a start point.

Applying functions or calculations on indexed columns, e.g., WHERE YEAR(create_time)=2024, confuses the optimizer.

Implicit type conversion, such as comparing a string column to a numeric literal, causes the index to be ignored.

Composite indexes that do not satisfy the left‑most prefix rule, rendering trailing columns useless.

OR conditions where one side lacks an index, causing the whole query to revert to a full scan.

The core principle is that the optimizer always selects the plan with the lowest estimated cost.

Three Practical Optimization Strategies

Beyond theory, interviewers expect candidates to discuss real‑world index tuning:

Prefix Indexes: For very long strings (e.g., product names), index only the first N characters to reduce index size, though such indexes cannot be used for ORDER BY or covering scans.

Covering Indexes: Include all columns needed by a query in the index so the engine can retrieve results directly from the B+Tree without a row lookup, effectively halving I/O.

Composite (Joint) Indexes: Combine multiple columns into a single index, following the left‑most prefix rule. Place high‑cardinality columns first and prioritize equality columns before range columns.

Any optimization should be validated with EXPLAIN, focusing on the type column hierarchy: const > eq_ref > ref > range > index > ALL.

One‑Sentence Takeaway

MySQL indexes work by using a short, wide B+Tree to keep disk I/O under three reads and by applying thoughtful index design—prefix, covering, and composite—to avoid back‑table lookups and full scans.