Inside MySQL's B+ Tree Index: Structure, Speed, and Storage

Indexes are a critical part of databases, and query optimization often relies on them. To fully leverage their capabilities, you must understand how they work internally and what data structure stores them.

What Is a B+ Tree Index?

Indexes are saved on disk as B+ trees. A B+ tree resembles a binary search tree: for each node, all values in the left subtree are smaller than the node's value, and all values in the right subtree are larger.

Key Differences from Binary Search Trees

A B+ tree node can contain many keys — typically thousands — giving it a large branching factor and making the tree much shallower than a binary search tree.

All values are stored in leaf nodes; non-leaf nodes hold only index entries. All leaf nodes sit at the same depth, so every index lookup performs the same number of B+ tree searches.

Leaf nodes are linked left-to-right in a linked list, keeping values ordered and making range scans highly efficient.

A Typical B+ Tree

The diagram below illustrates a typical B+ tree structure.

Why Use a B+ Tree?

The primary reason is speed. Memory is limited, so most data resides on disk, which is far slower than RAM. Without a tree structure, the DBMS would have to scan all records sequentially — impractical for a billion rows.

With a B+ tree, a billion keys (pointers to rows) fit within the 3rd, 4th, or 5th level, so each search requires only 3–5 disk accesses, drastically reducing I/O.

B+ trees are chosen over other tree structures because they are extremely shallow. Each lookup translates to one disk access per level, and disk accesses are proportional to tree height; a shallower tree means fewer I/O operations.

How a B+ Tree Is Organized

B+ trees are organized by matching node size to the storage engine's page size. Disk reads fetch entire pages, not partial data, because that is far cheaper.

Concrete Example: InnoDB Page Size

InnoDB uses a 16 KB page. Assume an integer index column of 4 bytes. A single node can hold: 16 * 1024 / 4 = 4096 keys, and up to 4097 child nodes.

For a tree of height 1 (root plus one leaf level):

Root node holds 4096 keys.

Leaf level holds 4096 * 4097 = 16,781,312 key values.

This demonstrates B+ tree efficiency: over 16 million keys fit in the first leaf level, each reachable with just two lookups.

Why Index Value Size Matters

The example shows index value size plays a crucial role:

Longer indexes mean fewer keys fit in a node, increasing tree height.

A taller tree requires more disk accesses.

More disk accesses degrade performance.

Therefore, index value size directly impacts performance. Keeping the B+ tree shallow is vital because it reduces the number of disk I/O operations.