Beyond Adding Indexes: From Disk Pages to B+Tree – Master MySQL Index Design and Operation

Why indexes matter

Database queries are slow mainly because disk I/O is about 10 ms per random read—roughly 100 000 times slower than memory access. Scanning a 10 GB table row‑by‑row would take ~100 seconds, while an index can turn an O(n) scan into an O(log n) tree lookup, cutting I/O to a handful of page reads.

Pages as the I/O unit

InnoDB stores data in 16 KB pages, not individual rows. Even a single row read loads the whole page into memory, exploiting temporal and spatial locality. A page contains a file header, page header, infimum + supremum, user records, free space, page directory, and a trailer for checksum.

B+Tree evolution

Binary search trees (≈24 levels for 10 M rows) still require many disk reads. Balanced trees (AVL/Red‑Black) reduce height but remain binary. B‑trees (multi‑way) lower height further (≈3–4 levels). B+Tree improves on B‑tree by storing only keys in non‑leaf nodes and linking leaf nodes with a doubly‑linked list, enabling fast range scans and stable query performance.

Assuming an 8 B bigint key and a 6 B pointer, a 16 KB page can hold about 1 170 keys. Thus a 2‑level B+Tree indexes ~1.8 × 10⁴ rows, a 3‑level tree indexes ~2.19 × 10⁷ rows, and a 4‑level tree indexes ~2.56 × 10⁹ rows—meaning a 20 M‑row table needs at most three page reads.

Clustered vs. secondary indexes

InnoDB’s clustered index stores the full row in leaf pages ordered by the primary key; each table has exactly one clustered index. If no primary key is defined, InnoDB creates a hidden 6‑byte ROW_ID as the clustered key.

Secondary indexes store the indexed column values plus the primary key. Querying a secondary index requires a “back‑table” lookup: first find the primary key in the secondary B+Tree, then fetch the full row from the clustered index.

Example:

SELECT * FROM user WHERE name = '张三';
-- 1. Use secondary index on name to get primary key (e.g., id=123)
-- 2. Use primary key to fetch the full row from the clustered index
-- 3. Return the result

Composite indexes and the left‑most prefix rule

A composite index (a, b, c) is ordered first by a, then b, then c. Queries can use the index only if the WHERE clause starts with the leftmost columns. Range conditions ( >, <, BETWEEN, LIKE 'prefix%') stop index usage for subsequent columns.

Examples: WHERE a = 1 → uses index on

a

WHERE a = 1 AND b = 2

→ uses index on

a, b

WHERE b = 2

→ cannot use the index (skips leftmost a) WHERE a = 1 AND b > 2 AND c = 3 → uses a and b only; c is ignored

Eight common index‑ineffective scenarios

Applying functions or arithmetic to indexed columns (e.g., YEAR(create_time) = 2026)

Implicit type conversion (e.g., comparing a VARCHAR column with a numeric literal)

LIKE patterns that start with a wildcard (e.g., LIKE '%foo')

OR conditions that involve a non‑indexed column

Using !=, <>, or NOT IN when the result set is large

IS NULL / IS NOT NULL on columns with many NULLs

Composite indexes that do not follow the left‑most prefix

Very small tables where the optimizer prefers a full scan

Seven golden rules for index design

Prefer auto‑increment integer primary keys; avoid UUIDs which cause page splits and larger secondary indexes.

In composite indexes place equality columns first, then range columns, and put high‑frequency columns at the front.

Build indexes that cover ORDER BY, GROUP BY, or DISTINCT to eliminate filesort and temporary tables.

Avoid redundant indexes; a (a, b) index makes a separate (a) index unnecessary.

For long string columns use prefix indexes (e.g., INDEX idx_title_prefix(title(20))) with an appropriate length.

Use covering indexes to avoid back‑table lookups for frequent queries.

Regularly monitor and maintain indexes: check execution plans with EXPLAIN, drop unused indexes, and rebuild fragmented indexes with OPTIMIZE TABLE.

Understanding these low‑level mechanisms turns “just add an index” from a blind guess into a systematic design process, enabling developers to craft the minimal set of indexes that serve the maximum number of query patterns.