B+trees for real

The choice of data structure follows from one fact: storage is read in blocks, and a block read costs the same whether you use one byte of it or all 16384. Everything follows.

The arithmetic that decides it

A B+tree node is one page. Internal nodes hold only keys and child pointers, so they pack tightly. With a BIGINT key (8 bytes) plus a child pointer (6 bytes), one 16KB page holds roughly:

          16384 bytes / (8 + 6) bytes per entry ≈ 1170 children per internal node


          height 1  →  1170 leaves

          height 2  →  1170² = 1.37M leaves

          height 3  →  1170³ = 1.6 billion leaves


          at ~75 rows per 16KB leaf page: a 3-level tree addresses ~100 billion rows

So any row in a table of a hundred million is three page reads away — and the root, plus most of the level below it, is permanently in the buffer pool. In practice a point lookup costs one physical read, often zero.

Why not the alternatives

In InnoDB there is no separate table storage. The primary key's B+tree is the table. Leaf pages contain complete rows, in primary key order.

What InnoDB does if you don't give it a primary key

It picks one, in this order:

1. The declared PRIMARY KEY.
2. Failing that, the first UNIQUE index whose columns are all NOT NULL.
3. Failing that, a hidden 6-byte DB_ROW_ID it maintains itself.

Option three is the bad one, and it is not merely wasteful. That hidden row id is assigned from a single global counter shared across the entire server, not per table. Every insert into any table without a usable primary key contends on the same mutex. On a write-heavy server with several such tables, this is a measurable, mysterious bottleneck.

-- Any table relying on the hidden row id? Fix these.
SELECT t.table_schema, t.table_name
FROM information_schema.tables t
LEFT JOIN information_schema.table_constraints c
  ON c.table_schema = t.table_schema
 AND c.table_name   = t.table_name
 AND c.constraint_type = 'PRIMARY KEY'
WHERE t.table_type = 'BASE TABLE'
  AND t.table_schema NOT IN ('mysql','sys','information_schema','performance_schema')
  AND c.constraint_name IS NULL;

-- 8.0+ has a dedicated view for exactly this:
SELECT * FROM sys.schema_tables_with_full_table_scans LIMIT 10;

A secondary index is its own B+tree, keyed on the indexed columns. Its leaves do not hold rows and do not hold physical pointers. They hold the primary key value.

So looking up by a secondary index takes two tree descents: one through the secondary index to find the PK, then one through the clustered index to find the row. This has three consequences that come up constantly.

• A wide primary key inflates every secondary index. A 36-char UUID stored as CHAR(36) means every entry in every secondary index carries 36 extra bytes. Five secondary indexes on a 10M-row table is 1.8GB of pure overhead, all of it competing for buffer pool space.
• Covering the query avoids the second descent entirely. If every column you selected is in the secondary index, InnoDB stops after the first tree. That is the mechanism behind Using index (chapter 35).
• The PK is implicitly appended to every secondary index, so an index on (status) is physically (status, id). This is why WHERE status='x' ORDER BY id needs no sort, and it is free — you do not need to declare it.

An insert is not "append to the end of the page". The sequence is:

1. Descend the tree to the leaf page where the key belongs.
2. Check free space. If the record does not fit, split (chapter 28).
3. Write the record bytes into the record heap — physically wherever there is room, typically at the heap top, not in key order.
4. Fix up the next_record offsets so the linked list stays in key order: find the predecessor, point the new record at what the predecessor pointed to, point the predecessor at the new record.
5. Update the page directory if a slot now owns too many records.
6. Write a redo log record describing the change (Part 6).

Step 3 is the one people get wrong. Physical order inside a page is insertion order; logical order is the linked list. This is why a page can be "in order" logically while its bytes are scrambled, and why OPTIMIZE TABLE — which rewrites pages so physical and logical order coincide — can speed up scans.

The single most important mechanism in this part. When a record will not fit in its target page, InnoDB must make room by splitting the page in two and adding a pointer to the new page in the parent.

The two split strategies

A naive 50/50 split is correct but wasteful for the commonest write pattern — appending ascending keys — because the left half is never inserted into again and stays half empty forever. InnoDB detects this.

The INDEX header keeps two fields, PAGE_LAST_INSERT and PAGE_DIRECTION, tracking whether recent inserts have been climbing. When inserts are sequential and the new key lands at the page's right edge, InnoDB performs an asymmetric split: it leaves the existing records alone and starts a new, nearly empty page for the incoming record. The result is pages that stay ~100% full rather than 50%.

The inverse operation. When deletes empty a page below a threshold, InnoDB tries to merge it with a sibling and free the page back to the tablespace's free list.

The default threshold is 50%, configurable per index with MERGE_THRESHOLD in the index comment (5.7+). A page that falls under it is merged with its left or right sibling if their combined contents fit in one page.

CREATE TABLE events (
  id BIGINT PRIMARY KEY,
  kind VARCHAR(32),
  INDEX idx_kind (kind) COMMENT 'MERGE_THRESHOLD=40'
);

Lowering the threshold makes merges rarer, which is what you want on a table with churn around the boundary — otherwise a page can merge, then split again on the next insert, then merge again. That merge–split thrash burns IO and redo for no benefit, and lowering the threshold to 30–40 is the standard fix.

Fragmentation in InnoDB means three different things. Distinguish them:

• Internal (page-level): pages are half empty after splits and deletes. Costs buffer pool efficiency — you cache air.
• External (extent-level): logically adjacent pages are physically scattered across the file, so a "sequential" scan seeks. Matters far less on SSD than it did on spinning disks.
• Row-level: updates that grow a row can force it off-page or leave gaps behind.

The measurable one is internal fragmentation, and you can see it directly:

-- Real fill factor per index, straight from the buffer pool.
-- A healthy PK on sequential keys sits near 15000+ of 16384.
SELECT index_name,
       COUNT(*)                        AS pages,
       ROUND(AVG(data_size))           AS avg_used_bytes,
       ROUND(AVG(data_size)/16384*100) AS pct_full
FROM information_schema.innodb_buffer_page
WHERE table_name = '`yourdb`.`users`'
  AND page_type = 'INDEX'
GROUP BY index_name;

-- The rough file-level view: free space sitting inside the .ibd.
SELECT table_name,
       ROUND(data_length/1024/1024)  AS data_mb,
       ROUND(index_length/1024/1024) AS index_mb,
       ROUND(data_free/1024/1024)   AS free_mb
FROM information_schema.tables
WHERE table_schema = DATABASE()
ORDER BY data_free DESC;

-- The rebuild. Needs disk for a full second copy; see ch 100 first.
-- ALTER TABLE users ENGINE=InnoDB, ALGORITHM=INPLACE, LOCK=NONE;

This is the highest-leverage schema decision in MySQL, and everything you need to reason about it is now on the table. Watch the same thousand inserts under both key types:

Why random keys cost so much

1. Every insert targets a different page. With sequential keys, the rightmost leaf page is always in the buffer pool and a thousand inserts touch one page. With random keys, a thousand inserts touch a thousand pages — each of which must be read from disk first, because you cannot modify a page you do not have.
2. The working set becomes the whole index. Sequential inserts need only the right edge cached. Random inserts need everything, so once the index exceeds the buffer pool, write throughput falls off a cliff.
3. Splits are 50/50 instead of right-edge. Pages settle at ~50% fill, so the index is roughly twice the size it needs to be — which makes point 2 worse.
4. The key is wide. CHAR(36) is 36 bytes versus 8 for a BIGINT, and that width is copied into every secondary index (chapter 26).

If you need a UUID, use a sortable one

The problem is randomness, not UUIDs. UUIDv1 has a timestamp but puts it in the wrong byte order; MySQL 8.0's UUID_TO_BIN(uuid, 1) swaps the time-low and time-high fields so the value sorts chronologically, and stores it as 16 binary bytes instead of 36 characters. UUIDv7 (RFC 9562, 2024) was designed for exactly this and is the modern answer — a 48-bit timestamp prefix followed by randomness.

-- Build two tables that differ ONLY in key locality, then measure.
CREATE TABLE k_seq  (id BIGINT AUTO_INCREMENT PRIMARY KEY, pad CHAR(200));
CREATE TABLE k_rand (id BINARY(16) PRIMARY KEY,           pad CHAR(200));
CREATE TABLE k_v7   (id BINARY(16) PRIMARY KEY,           pad CHAR(200));

-- Insert 200k rows into each (use a script or a recursive CTE).
--   k_rand: UUID_TO_BIN(UUID())        → random
--   k_v7  : UUID_TO_BIN(UUID(), 1)     → time-ordered

-- Now compare. Size first:
SELECT table_name,
       ROUND(data_length/1024/1024,1) AS data_mb,
       table_rows
FROM information_schema.tables
WHERE table_name LIKE 'k\_%';

-- Then fill factor — this is where the story is:
SELECT table_name, ROUND(AVG(data_size)/16384*100) AS pct_full
FROM information_schema.innodb_buffer_page
WHERE page_type = 'INDEX' AND table_name LIKE '%k\_%'
GROUP BY table_name;

-- And the split counters, before and after each load:
SELECT name, count FROM information_schema.innodb_metrics
WHERE name LIKE 'index_page_splits'
   OR name LIKE 'index_page_merge%';

A problem specific to secondary indexes: when you insert a row, every secondary index must be updated too. Those index pages are scattered by the indexed value, so each one may need a disk read — even though the user only asked to insert one row.

The change buffer avoids that. If the target secondary index page is not in the buffer pool, InnoDB records the intended change in a small B-tree inside the system tablespace and returns immediately. The change is merged into the real page later, when something reads that page anyway, or gradually by a background thread.

Tuning is via innodb_change_buffering (what to buffer: inserts, deletes, changes, all, none) and innodb_change_buffer_max_size (percent of buffer pool, default 25).

Status note: the change buffer is deprecated as of 8.0.35 and disabled by default in 8.4, because on modern SSDs the read it avoids is cheap while the complexity and crash-recovery cost are not. Know it for older systems and for the concept; do not design around it in new work.

InnoDB watches index access patterns. When it sees the same index prefix being searched repeatedly, it builds a hash index in memory mapping that key directly to the page, letting subsequent lookups skip the tree descent entirely. You do not create it, cannot see it in EXPLAIN, and cannot target it.

When it works, it turns a 3-level descent into one hash probe. When it does not, it is a liability: the structure is protected by latches (btr_search_latch), and on a workload with high concurrency and poor hit rate, maintaining it costs more than it saves. The classic symptom is heavy btr_search_latch contention in SHOW ENGINE INNODB STATUS under load.

SHOW VARIABLES LIKE 'innodb_adaptive_hash_index%';

-- The hit ratio lives in the INSERT BUFFER AND ADAPTIVE HASH INDEX
-- section of this output. Look for "hash searches/s" vs
-- "non-hash searches/s" — if hash searches are a small fraction,
-- you are paying for the structure without benefit.
SHOW ENGINE INNODB STATUS\G

-- Safe to turn off at runtime; measure both ways under real load.
-- SET GLOBAL innodb_adaptive_hash_index = OFF;

The optimizer needs to know how many rows a condition will match. It has two ways to find out, and both are approximations.

Index dives are the accurate one: for a given range, InnoDB descends to the start and end of the range and estimates the rows between them by counting pages. Accurate, but costs real IO — so it is capped by eq_range_index_dive_limit (default 200). An IN list with more than 200 values stops diving and falls back to statistics, which is why a query can change plan dramatically when a generated IN list crosses that boundary.

Persistent statistics are the cheap one: sampled cardinality per index, stored in mysql.innodb_index_stats. Sampling reads innodb_stats_persistent_sample_pages pages (default 20) out of the whole index. Twenty pages out of a million is a very thin sample, which is exactly why EXPLAIN's row estimates are often wrong by orders of magnitude on skewed data.

-- The stored statistics the optimizer is actually using.
SELECT index_name, stat_name, stat_value, sample_size, stat_description
FROM mysql.innodb_index_stats
WHERE database_name = DATABASE() AND table_name = 'users';

-- How thin is the sample?
SHOW VARIABLES LIKE 'innodb_stats_persistent_sample_pages';
SHOW VARIABLES LIKE 'eq_range_index_dive_limit';

-- Raise the sample for one table with skewed data:
-- ALTER TABLE users STATS_SAMPLE_PAGES = 200;
-- ANALYZE TABLE users;

-- Compare the estimate to reality — this is the diagnostic that matters.
EXPLAIN SELECT * FROM users WHERE status = 'active';   -- estimated
SELECT COUNT(*) FROM users WHERE status = 'active';    -- actual

Three optimizations that all exist to reduce work at the handler-API boundary from chapter 14.

Covering index — Using index

If every column the query needs appears in the secondary index, InnoDB never touches the clustered index. The second tree descent from chapter 26 disappears entirely.

-- needs a row fetch per match
SELECT id, email, name FROM users WHERE status = 'active';
  INDEX (status)                      → descend twice, per row
-- covered: everything is in the index
INDEX (status, email, name)         → Using index one descent, no row fetch

Index Condition Pushdown — Using index condition

When part of the WHERE clause references indexed columns that cannot be used for the range seek, MySQL pushes that condition down to the engine so it can reject rows before copying them across the API boundary.

INDEX (last_name, first_name)
SELECT * FROM people
WHERE last_name LIKE 'Ade%' AND first_name LIKE '%femi';

without ICP: engine returns every 'Ade%' row, server filters      → 50,000 crossings
with ICP:    engine applies the first_name test itself            →    120 crossings

Multi-Range Read — Using MRR

When a secondary index scan produces many primary keys in random order, MRR buffers and sorts them before fetching rows, converting random IO into something closer to sequential. Useful on spinning disks, marginal on SSD, and off by default in many builds.

Prefix indexes index the first N bytes of a column:

CREATE INDEX idx_email ON users (email(20));

Smaller index, but the engine must still fetch the row to verify the full value, so a prefix index can never be covering and cannot be used for ORDER BY. Choose N by measuring selectivity:

SELECT COUNT(DISTINCT LEFT(email,10))/COUNT(*) AS sel_10,
       COUNT(DISTINCT LEFT(email,20))/COUNT(*) AS sel_20,
       COUNT(DISTINCT email)/COUNT(*)          AS sel_full
FROM users;
-- pick the smallest N whose selectivity is close to sel_full

Functional indexes (8.0.13+) index an expression, which is the proper fix for the sargability problem in chapter 74:

-- this cannot use an index on created_at
WHERE DATE(created_at) = '2026-09-21'
-- either rewrite as a range (best)
WHERE created_at >= '2026-09-21' AND created_at < '2026-09-22'
-- or index the expression itself (8.0.13+)
CREATE INDEX idx_d ON events ((DATE(created_at)));   -- note double parens

Multi-valued indexes (8.0.17+) index arrays inside JSON, with one index entry per array element — the only way to index JSON arrays usefully:

CREATE INDEX idx_tags ON docs (
  (CAST(payload->'$.tags' AS CHAR(32) ARRAY))
);
SELECT * FROM docs WHERE 'mysql' MEMBER OF (payload->'$.tags');

Before 8.0, CREATE INDEX ... (col DESC) was parsed and silently ignored. You got an ascending index. MySQL could scan it backwards, which works for a single column, but backward scans are slower than forward ones — leaf pages are optimized for forward traversal, and read-ahead does not help.

The case a backward scan cannot serve is mixed-direction ordering:

SELECT * FROM posts ORDER BY author_id ASC, created_at DESC;

-- 5.7: INDEX (author_id, created_at) cannot serve this.
--      Reading it backwards gives author_id DESC too. → filesort.
-- 8.0: a genuinely descending index exists.
CREATE INDEX idx ON posts (author_id ASC, created_at DESC);   -- no sort

This pattern — group ascending, time descending — is the shape of nearly every feed, timeline and activity list, so it comes up far more than its obscurity suggests.

8.0 lets an index exist and be maintained while being hidden from the optimizer. This solves a genuinely hard operational problem: you believe an index is unused, but dropping it on a large table is expensive to undo — the rebuild can take hours, during which queries that did need it are scanning.

ALTER TABLE users ALTER INDEX idx_old INVISIBLE;   -- instant
-- watch dashboards for a day or a week
ALTER TABLE users ALTER INDEX idx_old VISIBLE;     -- instant undo
-- only then:
ALTER TABLE users DROP INDEX idx_old;

Combine it with the unused-index view to find candidates:

-- Indexes the server has never used since last restart.
-- Caveat: "since restart" — a monthly report's index looks unused
-- for 29 days. Check uptime before believing this.
SELECT * FROM sys.schema_unused_indexes;
SHOW GLOBAL STATUS LIKE 'Uptime';

-- Redundant indexes: a prefix of another index, so it earns nothing.
SELECT * FROM sys.schema_redundant_indexes;

-- Which indexes are invisible right now?
SELECT table_name, index_name, is_visible
FROM information_schema.statistics
WHERE table_schema = DATABASE() AND is_visible = 'NO';

A FULLTEXT index is an inverted index: word → list of documents containing it. InnoDB implements it with a set of hidden auxiliary tables holding the index, split into six buckets by the first character of the word for parallel maintenance.

Each row gets an FTS_DOC_ID. If you do not declare one, InnoDB adds a hidden column — and adding a FULLTEXT index to a table that lacks it requires a full table rebuild. Declaring FTS_DOC_ID BIGINT UNSIGNED NOT NULL AUTO_INCREMENT UNIQUE up front avoids that.

Inserts do not update the index synchronously; they go to an index cache flushed in batches, which is why a freshly inserted row may not be findable immediately. Deletes only add to a "deleted" table — the real removal happens during OPTIMIZE TABLE with innodb_optimize_fulltext_only=ON.

B+trees index one dimension. Geographic queries are two-dimensional, and there is no ordering of (lat, lng) pairs that keeps nearby points adjacent.

InnoDB's answer is an R-tree: nodes store minimum bounding rectangles, and a search descends into every rectangle that overlaps the query region. Unlike a B+tree, sibling rectangles may overlap, so a search can follow several branches.

CREATE TABLE places (
  id BIGINT PRIMARY KEY,
  loc POINT NOT NULL SRID 4326,      -- SRID is required for the index
SPATIAL INDEX (loc)
);

SELECT id, ST_Distance_Sphere(loc, @me) AS m
FROM places
WHERE ST_Within(loc, ST_Buffer(@me, 0.01))
ORDER BY m LIMIT 20;

Two practical notes: the column must be NOT NULL and carry an SRID for the index to be usable, and MySQL's spatial support is substantially behind PostGIS. For anything beyond proximity search, this is a genuine reason to reach for Postgres.

You can now see the structure your data lives in. Part 4 adds time to it: multiple versions of the same row coexisting, and the rules deciding which one your transaction is allowed to see.