Understanding Indexes: From Binary Search Trees to B+ Trees in InnoDB

Preface

Hello, I am A‑Star.

This article follows the previous post "InnoDB Principle: How Data Pages Become Indexes" and continues the discussion on indexes.

It is recommended to read the previous article first for the best understanding.

Index

Imagine reading a thick book without a table of contents; finding a specific chapter would take a long time, but a table of contents makes it instant.

An index improves data query efficiency, just like a book's table of contents; for a database table, an index is essentially its directory.

Binary Search Tree

There are many ways to implement indexes, such as ordered arrays, hash tables, and trees; among these, tree structures are widely used in databases.

We start with the most basic structure: the binary search tree.

The characteristic of a binary search tree is that all nodes in the left subtree of a parent have values less than the parent, and all nodes in the right subtree have values greater than the parent, as shown in the figure.

To search for id=4 , the traversal order is Index Page A → Index Page B → Index Page D → Data Page 0 , with a time complexity of O(log(N)) .

This means the search speed depends on the tree height; a taller tree performs worse. For a table with one million rows, a binary tree would have a height of about 20, and each random disk read takes roughly 10 ms, so locating a single row could take about 20 × 10 ms = 200 ms, which is very slow.

N‑ary Search Tree

To reduce random I/O, the tree height must be kept low; therefore, instead of a binary tree we use an N‑ary tree, where N represents the size of a data block.

In InnoDB, this is realized as a B+ tree.

For an integer column in InnoDB, a page is 16 KB. An 8‑byte BIGINT plus a 6‑byte pointer means a single index page can store roughly 1 200 entries (16 KB / 14 B ≈ 1 170).

If the B+ tree height is 4, it can store 1 200⁴ ≈ 1.7 billion rows.

Because the root node is always kept in memory, and the second level often fits in memory as well, a search typically requires only two disk I/O operations.

Why are the root and second‑level nodes in memory while deeper levels are not? The answer lies in their size:

The root node is a 16 KB index page that can hold about 1 200 index entries, easily fitting in memory.

The second level consists of 1 200 index pages, totaling 1 200 × 16 KB ≈ 20 MB, which still fits in memory.

The third level would contain 1 200 × 1 200 = 1.44 million pages, i.e., 1.44 million × 16 KB ≈ 23 GB, too large for memory.

The fourth level is the data pages themselves, which cannot be fully loaded into memory.

Index Search Process

Assume a table with 100 million rows has a B+ tree primary key index on id . To find id=2699 , the steps are:

Fetch the root index page from memory and perform a binary search to locate the second‑level index page.

Fetch the second‑level index page from memory and binary‑search to locate the third‑level index page.

Load the third‑level index page from disk into memory, binary‑search to locate the fourth‑level data page.

Load the fourth‑level data page from disk, binary‑search within the page to find the exact row.

This concludes the article; further details about indexes will be covered in subsequent posts.