Why MySQL InnoDB Uses B+ Trees for Indexes

The choice of B+ tree comes down to optimizing disk I/O. Index operations on a real database are dominated by how many 16KB pages the engine has to read, so the shape of the tree matters enormously. A hash index is O(1) for point lookups but useless for range queries or ORDER BY, which is what most SQL workloads need. A binary search tree has log base 2 depth — a million rows means about 20 levels, so 20 disk reads per query worst case. A B-tree improves on that by fanning out per node, but stores actual row data in every node, which limits how many keys each node can hold. The B+ tree's key innovation is that internal nodes contain only keys and child pointers — no data — so each 16KB page fits around 1000 keys. With that fanout, three levels index roughly a billion rows, and the top one or two levels stay resident in the InnoDB buffer pool, so a primary key lookup typically costs one actual disk read. The second crucial property is the leaf linked list — every leaf page points to the next, so range scans like WHERE id BETWEEN 100 AND 200 or ORDER BY id just walk the leaves sequentially without climbing back up the tree. In InnoDB specifically, the primary key defines the clustered index — the table itself IS the B+ tree, with full rows stored in the leaves. Secondary indexes store the primary key as the leaf value, which means a query using a secondary index first walks the secondary tree to find the PK, then walks the clustered tree to get the row — the "back to table" cost. A covering index sidesteps this by including all the columns the query needs directly in the secondary index, so the query never touches the clustered tree. That's why composite and covering indexes are such an important tuning tool.