Why MySQL Chooses B+ Trees: From BSTs to High-Performance Indexes

Preface

In MySQL, both InnoDB and MyISAM use B+ trees as the index structure (hash and other indexes are not considered here). This article starts with the simplest binary search tree, gradually explains the problems each tree solves and the new issues they introduce, and shows why MySQL chooses B+ trees for indexing.

Table of Contents

1. Binary Search Tree (BST): Imbalance

2. Balanced Binary Tree (AVL): Rotation Overhead

3. Red‑Black Tree: Tall Trees

4. B‑Tree: Designed for Disk

5. B+‑Tree

6. Experiencing the Power of B+‑Tree

7. Summary

1. Binary Search Tree (BST): Imbalance

A Binary Search Tree (BST) is a binary tree where the left subtree of any node contains values less than or equal to the node’s value, and the right subtree contains values greater than or equal to it. The average search time is O(log n), but a BST can become unbalanced and degenerate into a linked list, resulting in O(n) time.

2. Balanced Binary Tree (AVL): Rotation Overhead

AVL trees are strictly balanced binary trees where the height difference between left and right sub‑trees of any node does not exceed 1. Searches, insertions, and deletions are O(log n). However, maintaining balance requires rotations; deletions may trigger O(log n) rotations, making AVL trees inefficient for write‑heavy workloads.

3. Red‑Black Tree: Tall Trees

Red‑black trees relax strict balance, guaranteeing that the longest path from root to leaf is at most twice the shortest. They use node colors (red or black) and a set of rules to maintain approximate balance. Compared with AVL trees, red‑black trees have slightly slower queries due to greater height, but deletions are much faster because only a constant number of rotations and recolorings are needed. Red‑black trees are widely used (e.g., Java’s TreeMap, HashMap’s tree bins). For disk‑based data such as MySQL indexes, red‑black trees are still too tall, leading to excessive I/O.

4. B‑Tree: Designed for Disk

B‑trees are multi‑way balanced search trees designed for secondary storage. Each non‑leaf node can have up to *m* children (the order *m*). This reduces tree height dramatically compared with binary trees, cutting disk I/O. All leaf nodes reside on the same level, and the structure exploits locality of reference by storing nearby keys in the same node, improving cache hits.

5. B+‑Tree

B+‑trees are a variant of B‑trees with two main differences:

Only leaf nodes store actual data; internal nodes store only keys.

Leaf nodes are linked together via a doubly‑linked list.

Advantages over B‑trees include:

Fewer I/O operations because internal nodes are smaller and the tree height is lower.

Better support for range queries—once the lower bound is found, the linked leaf list can be scanned sequentially.

Stable query performance: all data reside in leaves, so search cost is proportional to tree height only.

The main drawback is increased space usage due to key duplication, but the performance gains usually outweigh this cost.

6. Experiencing the Power of B+‑Tree

In InnoDB, a typical B+‑tree index has a height of 2–4 levels. Assuming a 16 KB page size, a non‑leaf page can hold about 1 000 key‑pointer pairs, and a leaf page about 100 records. A three‑level B+‑tree can therefore index roughly 100 million rows, whereas a binary tree would need about 26 levels for the same amount of data.

7. Summary

Different tree structures address different problems:

BST: basic ordered storage but can become unbalanced.

AVL: strict balance via rotations, but rotation overhead hurts deletions.

Red‑black: relaxed balance with cheap deletions, yet still too tall for disk.

B‑tree: multi‑way balance reduces height for disk storage.

B+‑tree: internal nodes store only keys, leaves store data and are linked, giving the lowest height, fewer I/O operations, and efficient range queries—hence its widespread use in databases.