Why MySQL Chooses B+ Trees for Indexing: Deep Dive & Interview Answers

Interview Reference Answers

MySQL chooses B+ tree as the index structure for several core reasons:

1. Disk I/O efficiency optimal . B+ tree is a short, wide multi‑way balanced search tree; its height is usually only 3‑4 levels for tens of millions of rows, meaning a query needs at most 3‑4 disk I/Os, and disk I/O is the most time‑consuming operation in database queries.

2. Data storage more dense . Non‑leaf nodes store only index keys and pointers, allowing each 16 KB page to hold thousands of index entries, whereas a B tree stores data in non‑leaf nodes and can only hold dozens to a few hundred entries per page.

3. Range query performance excellent . All leaf nodes are linked by a doubly‑linked list and are ordered by key, so a range query (e.g., BETWEEN, ORDER BY) only needs to locate the start position and then scan sequentially.

4. Query performance stable . All data reside in leaf nodes, so every query follows the same path length, giving stable time complexity, unlike B tree or hash indexes that may fluctuate.

Compared with other structures, hash indexes are fast for equality but do not support range queries; red‑black trees have higher height; B tree stores data in all nodes, leading to smaller node capacity and more I/O.

Deep Analysis

(1) Why need indexes?

Without an index, MySQL must perform a full table scan, comparing each row sequentially, which can take seconds for a table with ten million rows. An index works like a book's table of contents, allowing direct location of the target page.

(2) Why not simple array or linked list?

Ordered arrays enable binary search with O(log n) comparisons, but inserting or deleting requires moving many elements, which is unacceptable for a dynamic database. Linked lists allow cheap inserts/deletes but require O(n) scans for queries.

(3) Why not binary search tree?

A binary search tree (BST) has average O(log n) operations, but if inserted data are sorted (e.g., auto‑increment IDs), the tree degenerates into a linked list, making the height equal to the number of nodes and degrading performance to O(n).

(4) Why not red‑black tree?

Red‑black trees add a self‑balancing mechanism, keeping height logarithmic, but they are still binary trees with only two children per node. For ten million rows, even a perfectly balanced red‑black tree may need 24 levels, meaning 24 disk I/Os.

(5) Multi‑way search tree: from binary to multi‑branch

Increasing the fan‑out reduces height dramatically. If each node can have 100 children, ten million rows can be stored in only 2‑3 levels, cutting I/O from 24 to 4.

(6) B‑Tree: multi‑way balanced search tree

Each node can contain multiple keys and children

All leaf nodes are on the same level (balanced)

Node key count has upper and lower bounds

A typical B‑Tree node looks like this:

(7) From B‑Tree to B+‑Tree: key optimizations

Adjustment 1: Non‑leaf nodes do not store data

In a B‑Tree, every node stores both keys and the corresponding data record. In a B+‑Tree, non‑leaf nodes store only keys and pointers; the actual rows are stored exclusively in leaf nodes. This greatly increases the number of index entries per page (e.g., ~1 170 entries vs. ~15 in a B‑Tree).

Adjustment 2: Leaf nodes linked as an ordered doubly‑linked list

This design makes range queries a simple sequential scan along the linked list, turning them into sequential I/O.

Adjustment 3: All queries must reach leaf nodes

Because non‑leaf nodes contain no data, any key lookup must descend to the leaf level. Although this adds one extra level, it yields perfectly stable query cost and simplifies optimizer cost estimation.

(8) B+‑Tree in InnoDB practical use

Primary key index (clustered index)

In InnoDB, each table has a primary key index whose leaf nodes store the full data rows. Height calculation example: with a BIGINT primary key (8 bytes) and a 16 KB page, a three‑level B+‑Tree can hold about 20 million rows; a four‑level tree can hold billions.

Secondary index (non‑clustered index)

When you create an index on a non‑primary column (e.g., phone number), InnoDB builds a secondary B+‑Tree whose leaf nodes store only the indexed column value plus the primary key value.

(9) B+‑Tree vs other data structures

B+‑Tree vs Hash index

Hash indexes provide O(1) equality lookups but cannot support range queries, ORDER BY, or left‑most prefix matches, and suffer from collisions.

B+‑Tree vs B‑Tree

For a range query (e.g., age BETWEEN 25 AND 35), a B‑Tree must locate the start key, then repeatedly move up and down the tree, causing many random I/Os. A B+‑Tree locates the start leaf once and then scans sequentially along the leaf chain, resulting in far fewer I/Os.

B‑Tree: ~10 random I/Os for a small range.

B+‑Tree: 1 random I/O to locate the start + sequential reads.

(10) B+‑Tree optimization tricks

1. Page split performance impact

Splitting a full page requires allocating a new page, moving data, updating the parent, and possibly cascading splits. Using an auto‑increment primary key makes inserts always go to the rightmost leaf, reducing splits. Random primary keys (e.g., UUID) cause frequent splits and fragmentation.

2. Index covering usage

When all columns required by a query are present in the index, the engine can satisfy the query using only the index (covering index), avoiding a table lookup.

SELECT name, age FROM users WHERE name = '张三';

3. Composite index left‑most prefix principle

A composite index (a, b, c) can be used for queries that specify a, a+b, or a+b+c, but not for queries that skip the leftmost column.

WHERE a = 1 → usable

WHERE a = 1 AND b = 2 → usable

WHERE b = 2 → not usable

(11) Why the "+" in B+‑Tree?

The “+” indicates enhancements over a plain B‑Tree: non‑leaf nodes store only keys (higher fan‑out), leaf nodes are linked (fast range scans), and all queries end at the leaf level (stable performance). It is analogous to C++ being an enhanced version of C.

Interview Extension Questions

Q1: Why must InnoDB have a primary key? Because InnoDB stores rows in a clustered B+‑Tree; without an explicit primary key it creates a hidden 6‑byte ROWID.

Q2: Why recommend an auto‑increment primary key? It guarantees sequential inserts at the rightmost leaf, minimizing page splits and fragmentation.

Q3: Why avoid overly long primary key columns? Long primary keys enlarge secondary index leaf nodes (they store the primary key), reducing cache hit rate.

Q4: How many columns can a composite index contain? MySQL limits it to 16 columns, though practical designs should keep it reasonable.