How MySQL’s B+ Tree Indexes Supercharge Query Speed and Reliability

Indexing in MySQL

When a table has no index, MySQL must read every row to evaluate a WHERE clause. This full‑table scan incurs one I/O operation per data page, which becomes a severe bottleneck once the table reaches millions of rows.

Binary search trees and their drawbacks

Early indexing ideas used simple binary search trees. A binary tree stores a single key per node and has at most two child pointers. After many insertions the tree can become highly unbalanced, turning into a linked list. Each lookup then requires a number of disk reads proportional to the tree height, which is unacceptable for large data sets.

B‑tree

A B‑tree groups many sorted keys in a single node and allows many child pointers. Because each node spans an entire disk page, the tree height stays low even for very large tables, reducing the number of I/O operations per lookup to a handful.

B+‑tree in InnoDB

MySQL’s default InnoDB storage engine implements indexes as B+‑trees. All row pointers (the primary key value for the clustered index, or the hidden row ID for secondary indexes) are stored in the leaf nodes, while internal nodes contain only separator keys and child pointers. This design guarantees a uniform search depth for every key and enables fast sequential scans because leaf nodes are linked together in order.

Key properties of the InnoDB B+‑tree:

Uniform depth : every lookup traverses the same number of levels, eliminating the “fast near‑root / slow near‑leaf” variance of plain B‑trees.

Range scans : the linked leaf pages allow the engine to read a contiguous range of rows with a single sequential I/O stream.

Clustered primary index : the table’s data rows are stored in the leaf pages of the primary key’s B+‑tree, so a primary‑key lookup reads the row directly.

Secondary indexes : each secondary index stores the indexed column values in its leaf pages together with the primary‑key value that points back to the clustered data.

Hash and bitmap indexes

For workloads where equality lookups dominate and the indexed column has high cardinality, MySQL can use a hash index (available on the MEMORY engine and as an optional InnoDB adaptive hash index). A hash index maps a key directly to a bucket, providing O(1) lookup time but offering no ordering, so range queries are impossible.

Bitmap indexes store a bit vector for each distinct value of a column. They are efficient for low‑cardinality columns (e.g., flags, enums) because logical operations on bitmaps can combine multiple predicates quickly. Native MySQL does not expose bitmap indexes, but they are supported by some third‑party storage engines and analytical extensions.

Practical usage in MySQL

Creating and inspecting indexes is straightforward:

-- Create a secondary index on column `email`
CREATE INDEX idx_user_email ON users(email);

-- Show indexes defined on a table
SHOW INDEX FROM users;

-- Use EXPLAIN to verify that the optimizer chooses the index
EXPLAIN SELECT * FROM users WHERE email = '[email protected]';

When designing indexes, consider the following guidelines:

Prefer B+‑tree indexes for columns used in range predicates ( BETWEEN, >, LIKE 'prefix%').

Use hash indexes only for pure equality lookups on high‑cardinality columns and when the underlying engine supports them.

Avoid indexing columns with very low selectivity unless they are part of a composite index that together provides sufficient discrimination.

Remember that InnoDB’s primary key is clustered; choosing a good primary key (small, immutable, and frequently used) reduces page splits and improves overall I/O.

By leveraging B+‑tree indexes (the default in MySQL), developers can keep query latency low even as tables grow to hundreds of millions of rows, while hash or bitmap indexes can be employed for specialized workloads that demand faster point lookups or bit‑wise predicate evaluation.