MySQL Internals: Pages, B+Trees, Indexes, the Optimizer, WAL, Binlog and Replication

We all use MySQL almost every day. We create a table, add a few indexes, write some queries, and it just works. But most of us never stop to ask what is actually happening when we run SELECT * FROM users WHERE id = 42. How does it find that one row out of ten million, and how does it make sure the row is still there after a crash?

Let me go top to bottom through MySQL, or more correctly InnoDB, the storage engine almost everyone uses. We start from the smallest unit on disk, the page, and build up to B+Tree indexes, clustered vs secondary indexes, how the optimizer decides whether to even use an index, when a normal index fails and you reach for spatial indexing, and finally how WAL, the binlog and replication keep everything durable and copied. By the end it should read as one connected story, not a bag of features.

---

The page: the unit of everything

Before indexes and trees, there is one idea that everything else sits on top of, the page.

(Quick word on InnoDB, since I keep saying it. InnoDB is MySQL’s default storage engine, the part that actually stores rows on disk and handles indexes, transactions and crash recovery. When people say “MySQL internals” today, they almost always mean InnoDB.)

InnoDB does not read or write single rows from the disk. It reads and writes in fixed size blocks called pages, and by default a page is 16 KB. Even if you want one small row, InnoDB pulls the whole 16 KB page that contains it into memory.

Why work in blocks like this? Because disk access is slow and it is slow in a very specific way. The expensive part is finding the data (the seek), not reading a bit more once you are there. So reading one row and reading 16 KB around it costs almost the same. It is much cheaper to read a decent block once than to go back to the disk again and again for tiny pieces.

These pages live on disk, but the hot ones are cached in memory in something called the buffer pool. The buffer pool is just a big chunk of RAM where InnoDB keeps the pages it is using. When you query a row, InnoDB first checks if its page is already in the buffer pool. If yes, no disk access at all. If not, it reads the page from disk into the buffer pool and then uses it. This is why the second run of the same query is often much faster than the first.

What one page actually holds

A page is not just a bag of rows. Crack one open and you find, top to bottom:

• a small header — what page this is, its type, and pointers to the previous and next page at the same level (this is what chains the leaves together),
• the rows themselves, kept in key order as a linked list; on a clustered-index leaf each row also carries two hidden fields, DB_TRX_ID and DB_ROLL_PTR, which are what make MVCC and rollback work,
• some free space that new rows grow into,
• a tiny page directory — a few slots pointing into the rows, so a lookup inside the page is a binary search and not a linear scan,
• and a trailer with a checksum, to catch a page that was only half written before a crash.

You do not need to memorise the layout. The one thing worth keeping is that a page is a self-contained little unit: its rows in sorted order, plus pointers to its neighbours. That is exactly what lets the tree on top of it work.

So the mental model to carry for the rest of this post is simple. The database is a pile of 16 KB pages, some on disk and some cached in memory, and almost everything is about reading as few pages as possible.

---

How the data is arranged: B-Tree, then B+Tree

Now, if the table is just a pile of pages, how do we find the right page quickly? If we had to scan every page to find id = 42, a large table would be painfully slow. This is the whole reason indexes exist, and the data structure behind them is the B+Tree.

Let me build up to it, because the “B+” part actually matters.

First, the B-Tree

A B-Tree is a balanced tree made for disk. Unlike a normal binary tree where each node has 2 children, a B-Tree node can have many children, hundreds of them. Each node holds a bunch of sorted keys, and between those keys are pointers to child nodes.

Why so many children per node? This goes straight back to the page. One tree node is stored in one page. A page is 16 KB, and a single entry (one key plus a child pointer) is only a handful of bytes, so a node can hold hundreds of entries. This “how many children per node” number is called the fan out, and keeping the fan out high is the whole game.

A quick clarification, because this genuinely trips people up. The 16 in “16 KB page” is the page size, it is not the number of children. A node does not have 16 children, it has as many as physically fit in that 16 KB. For a typical integer key that is roughly 16 KB / (key + pointer), which lands somewhere around 1000 children per node in practice (after row overhead, and because pages are not kept 100% full). So the fan out is in the hundreds to a thousand, not sixteen.

Now the height, which is the payoff. With a fan out of about 1000, the tree stays incredibly short:

height 1  →  ~1,000 rows
height 2  →  ~1,000,000 rows
height 3  →  ~1,000,000,000 rows

So even a table with hundreds of millions of rows is only 3 or 4 levels deep. Since the height is exactly how many pages you must read to reach any row, that means any row is 3 or 4 page reads away, and the top one or two levels are almost always sitting in the buffer pool already. That is the magic. And because these trees are always kept balanced (every leaf at the same depth), that shallow number is not the best case, it is the worst case, the same for every single row.

Two things set that fan out, and both are levers you can feel. One is the page size — a 16 KB page simply fits more entries than a 4 KB one. The other is the size of each entry — a compact INT key with a small child pointer packs far tighter than a fat random UUID. Shrink the entry and the node gets wider, the tree gets flatter, and every lookup costs one fewer page read. That is a good part of why 16 KB is the default (flat tree, but reads still cheap) and why a small integer primary key is worth reaching for: both keep the fan out high.

Here is the catch with a plain B-Tree, and it is exactly what your fan out depends on. In a plain B-Tree, the data itself (the row, or the value) is stored inline in every node, including the internal ones. That data takes up space. So each entry becomes key + data + pointer, which is fat, and far fewer entries fit in the 16 KB page. Fewer entries per node means a lower fan out, a lower fan out means a taller tree, and a taller tree means more page reads for every lookup. The very thing that made the tree fast, packing lots of children into one page, gets spoiled by carrying data around in the internal nodes.

Run a query on a B-Tree: every node stores rows, and there are no links between the bottom nodes. (open the B-Tree visualizer)

Now, the B+Tree (what databases actually use)

A B+Tree is a small but important variation:

• All the real data lives only in the leaf nodes, the bottom level. The internal nodes hold only keys and pointers, they act purely as a directory to guide you down.
• The leaf nodes are linked together like a linked list, left to right in sorted order.

These two changes give databases exactly what they need:

• Range queries become trivial. For WHERE id BETWEEN 40 AND 90, you walk down to the leaf holding 40 once, then just follow the leaf to leaf links to the right until you pass 90. No going back up the tree. A plain B-Tree cannot do this cleanly.
• The internal nodes stay tiny, because they hold only keys and pointers, no data. This is the direct fix for the B-Tree problem above. With no data bloating them, far more entries fit in each 16 KB page, so the fan out is high again and the tree is short again. All the fat data sits down in the leaves, where it does not hurt the fan out of the directory above it.
• Full ordered scans are just walking the leaf chain from left to right.

So the one line summary is, MySQL stores your indexes (and as we will see, your table itself) as B+Trees, and a B+Tree is basically a very short, very wide tree, tuned so that finding any row takes only a handful of page reads.

The same query on a B+Tree: only the leaves store rows, and they are linked — so a range scan glides straight along the leaf chain. (open the B+Tree visualizer)

---

Clustered vs secondary index (this is the part people miss)

Here is something that surprises a lot of people. In InnoDB, the table itself is a B+Tree. There is no separate “heap” of rows sitting somewhere with indexes pointing into it. The table is an index.

The clustered index

Every InnoDB table is physically stored as one big B+Tree, sorted by the primary key. This is called the clustered index. The leaf nodes of this tree do not just hold the key, they hold the entire row. So when you look up by primary key, you walk down the tree and the moment you reach the leaf, the full row is right there. One traversal, done.

This is also why the choice of primary key matters so much in InnoDB. Since the whole table is sorted and stored by it:

• A small, ever increasing primary key (like an auto increment integer) is ideal. New rows just get appended to the end, pages fill up neatly.
• A large or random primary key (like a random UUID) is worse. Inserts land in random places in the tree, causing pages to split and fragment, and every secondary index gets bigger too (I will explain why in a second).

If you do not define a primary key, InnoDB quietly creates a hidden one for you, so a clustered index always exists.

The secondary index

Now what about an index on some other column, say email? That is a secondary index. It is also a B+Tree, sorted by email this time. But here is the twist, its leaf nodes do not store the full row. They store the indexed column plus the primary key of that row.

So a lookup by email is actually two lookups:

1. Search the email B+Tree  ──►  find the leaf  ──►  it gives you the primary key
2. Search the clustered index by that primary key  ──►  finally get the full row

This second hop, from the secondary index back to the clustered index to fetch the rest of the row, is often called a bookmark lookup or “index back to table”. It is usually cheap, but it is not free, and it explains a couple of things:

• Why secondary indexes store the primary key, and therefore why a fat primary key makes every secondary index fatter.
• Why a covering index is so nice. If your query only needs columns that are already inside the secondary index, InnoDB can answer it entirely from that index and skip the second hop completely. For example, an index on (email, name) can answer SELECT name FROM users WHERE email = ? without ever touching the clustered index. This is a very common and very effective optimization.

So the picture is, one clustered index that is the table sorted by primary key, and any number of secondary indexes that point back to it using the primary key.

---

The optimizer: should it even use the index?

Here is a myth worth killing early. Adding an index does not guarantee it will be used. MySQL has a cost based optimizer, and for every query it estimates the cost of different plans and picks the cheapest one. Sometimes the cheapest plan is to ignore your index and just scan the whole table.

That sounds wrong at first, but think about it with the page model.

Using a secondary index means, for each matching row, do a bookmark lookup back into the clustered index. Those lookups jump around the tree, so they are close to random page reads. A full table scan, on the other hand, reads the clustered index leaves in order, which is a nice sequential sweep.

Now imagine your query matches most of the table, for example WHERE is_active = 1 where 90% of users are active. Using the index would mean doing a random bookmark lookup for 90% of all rows, which is far more expensive than just sweeping the table once in order. So the optimizer correctly chooses the full scan.

The idea behind this decision is selectivity (or cardinality). Selectivity is how many distinct values a column has, or put simply, how good the column is at narrowing things down:

• High selectivity (like email, almost unique) means an index lookup returns very few rows, so the index is a big win.
• Low selectivity (like a status column with 3 possible values, or a boolean) means the index returns a huge chunk of the table, and past a certain tipping point the optimizer will skip it.

How does the optimizer even know the selectivity without running the query? It keeps statistics, rough histograms and cardinality estimates for your columns, sampled from the pages. This is also why stale statistics can lead to bad plans, and why ANALYZE TABLE (to refresh stats) sometimes fixes a query that suddenly went slow.

The practical takeaways:

• Do not index low selectivity columns on their own and expect magic. A boolean index is rarely useful by itself.
• Composite index order matters. Put the most selective, most equality filtered column first.
• Use EXPLAIN to see what the optimizer actually decided. If it says it is doing a full scan when you expected an index, the answer is usually selectivity or stale statistics, not a broken index.

---

When a normal (scalar) index fails

Everything so far assumes we are indexing a single scalar value that has a natural order, a number, a date, a string. B+Trees are perfect for that, because the whole idea of the tree is “keep the keys sorted in one dimension”.

But that single dimension assumption is exactly where B+Trees break down.

Think about location data, a latitude and a longitude, and a query like “find all restaurants within 2 km of me”. This is a two dimensional question. You care about latitude and longitude together.

Suppose you put a B+Tree index on (latitude, longitude). The tree sorts primarily by latitude. So it can quickly narrow down “all points in this latitude band”, but within that band the longitudes are all over the place. To find a small 2 km box you would still have to scan a huge strip of the earth at the right latitude and filter longitude by hand. The index helps with one axis and is useless on the other.

The core problem is this. A B+Tree can only order data along one line. Space is not a line, it is a plane. There is no way to lay out 2D points on a single ordered line so that points near each other on the map are always near each other in the ordering. This is not a MySQL limitation, it is a property of the data structure, and to index space you need one that understands more than one dimension.

---

Geospatial indexing: quad-trees and R-trees

The fix is to divide space itself instead of ordering values on a line.

The quad-tree, just for intuition

The easiest way to picture space partitioning is a quad-tree. Take the whole map as one square. If a square holds too many points, split it into four quadrants, and keep splitting the crowded ones. A city ends up finely split, an ocean stays one big square.

Drop a latitude/longitude and press Run — watch the grid keep splitting into the dense area. (open the quadtree visualizer)

“Find everything within 2 km of me” becomes a tree walk: start at the root and only descend into the squares that overlap your search box, skipping the rest of the map. That pruning is exactly what a scalar index could not do in 2D.

What MySQL actually uses: the R-tree

A quad-tree is a great mental picture, but MySQL’s SPATIAL index (on GEOMETRY, POINT and similar) is built on an R-tree, not a quad-tree. An R-tree does not carve space up on a fixed grid. Instead it groups nearby objects together and stores a minimum bounding rectangle (MBR) around each group, the smallest box that encloses everything inside it. The leaves hold the actual geometries; the internal nodes hold boxes around boxes. To search, you start at the root and only walk down into the boxes that overlap your query box, pruning the rest.

The same location on an R-tree — far fewer boxes opened, and it stays shallow. (open the R-Tree visualizer)

Quad-tree vs R-tree

Both prune space to answer “near me” queries, so why does a database reach for the R-tree? It comes down to what each one actually divides.

	Quad-tree	R-tree
Divides	space, on a fixed grid	data — it groups the objects
Regions	disjoint, tile the plane, never overlap	bounding boxes that can overlap
Balanced?	no — deeper wherever points are dense	yes — every leaf at the same depth
Node shape	always 4 children	high fan-out, one node per page
Natural home	in memory (images, game maps)	on disk, in a database

The last two rows are the whole reason MySQL picks an R-tree. A quad-tree splits space blindly, so its depth follows the data, a dense city block pushes one branch very deep while an ocean stays shallow. That lopsided shape does not map neatly onto fixed-size disk pages. An R-tree instead splits an overflowing node to stay balanced and wide, exactly the short, page-per-node shape the rest of this post has been leaning on, so every leaf is the same few page reads from the root. That is what makes it a database index and not just a nice diagram.

The one price the R-tree pays for grouping data instead of tiling space is that its boxes can overlap. A quad-tree’s quadrants never overlap, so a search there follows a clean path down. In an R-tree, two sibling boxes can cover the same patch of map, so your query box might land inside several of them at once and the search has to walk down more than one branch. That is the trade for staying balanced and disk-friendly.

In practice you rarely touch any of this directly:

-- a spatial index on a POINT column
ALTER TABLE places ADD SPATIAL INDEX (location);

-- "find places whose location is inside this box"
SELECT name
FROM places
WHERE MBRContains(@search_area, location);

So the takeaway: a B+Tree orders values along one line and is perfect for = and range queries on a single dimension, while an R-tree carves space into (possibly overlapping) boxes and is what you reach for the moment the question is really “near me” or “inside this region”. When a scalar index falls apart on location data, the R-tree is the tool you were missing.

---

Durability: the Write Ahead Log (WAL)

We have covered how MySQL finds your data. Now the other half, how it does not lose your data when the power goes off mid write.

Here is the tension. All the changes happen on pages in the buffer pool, in memory. Writing those changed (dirty) pages back to disk immediately, for every single commit, would be terrible, because those page writes are scattered randomly across the file and random disk writes are slow. But if we keep changes only in memory and the server crashes, the changes are gone.

The way out is Write Ahead Logging, or WAL. The rule is simple:

Before a change is considered committed, write a small record of that change to a log first. Only then acknowledge the commit. The actual data pages can be flushed to disk later, lazily.

In InnoDB this log is the redo log (the ib_logfile files). It works like this:

COMMIT
  1. Change the page in the buffer pool (in memory)         [fast]
  2. Append what changed to the redo log, then fsync it     [fast, sequential]
  3. Acknowledge the commit to the client                   [done]
  ...later...
  4. Flush the dirty page to its real place on disk         [lazy, batched]

The important trick is that the redo log is written sequentially, appended to the end. Sequential disk writes are dramatically faster than random ones. So instead of doing slow random page writes on every commit, InnoDB does one fast sequential log append on commit, and pushes the slow random page writes to the background where they can be batched.

Now the crash safety. If the server dies after step 2 but before step 4, the data page on disk is stale, but the change is safely in the redo log. On restart, InnoDB does crash recovery: it reads the redo log and replays any changes that had not yet made it to the data pages. So a committed transaction survives even though its page was never written. The redo log is a fixed size ring that is reused in a circle, since once a dirty page is safely flushed, its old log records are no longer needed.

There is a matching undo log as well, which stores the previous version of rows. It is used to roll back a transaction that did not commit, and to give other transactions a consistent older snapshot to read (this is how MVCC and consistent reads work). But the one big idea to hold onto is WAL: log the change first, flush the pages later, replay the log after a crash.

---

The binlog, and how it is different from the redo log

Here is a point that confuses almost everyone the first time, because MySQL has two logs that sound similar but do completely different jobs.

The redo log we just saw is an InnoDB, storage engine level thing. It is physical (“page 5 byte 100 changed to this”), it is circular (overwritten once flushed), and its only purpose is crash recovery. Nobody outside InnoDB reads it.

The binlog (binary log) is a server level log, above the storage engine. It records the changes as logical events, and it is append only, kept around for as long as you configure. Its purpose is completely different, it is for:

• Replication, shipping changes to replica servers (the big one).
• Point in time recovery, restore last night’s backup, then replay the binlog up to 2 seconds before the bad DELETE.

The binlog can be in different formats:

• STATEMENT based, it logs the actual SQL (UPDATE users SET ...). Compact, but risky for non deterministic statements (think NOW() or RAND()).
• ROW based, it logs the actual before and after of each changed row. Safer and the common default today, at the cost of more log volume.
• MIXED, use statement where safe, fall back to row where not.

Because there are two logs, a commit has to make sure they agree, otherwise after a crash the redo log and the binlog could disagree about whether a transaction happened, and a replica would drift from the primary. InnoDB solves this with an internal two phase commit between the redo log and the binlog: prepare in the redo log, write the binlog, then mark the redo log committed. If a crash happens in the middle, recovery uses the presence of the binlog entry to decide whether to roll the transaction forward or back, so both logs always end up telling the same story.

Quick way to remember the two:

• Redo log, InnoDB, physical, circular, for surviving a crash.
• Binlog, server layer, logical, append only, for replication and recovery.

---

Replication: copying the data to other servers

Now the binlog pays off. Once you have a log of every change in commit order, you can hand that stream to another server and have it apply the same changes, and now you have a replica that stays in sync with the primary.

The basic flow:

   PRIMARY                                 REPLICA
 ┌──────────┐    binlog events    ┌────────────────────────┐
 │ writes   │ ──────────────────► │ I/O thread writes them  │
 │ + binlog │                     │ to a local relay log    │
 └──────────┘                     │ SQL thread replays them │
                                  └────────────────────────┘

The primary writes to its binlog as usual. Each replica has an I/O thread that pulls those binlog events over the network into a local relay log, and one or more SQL threads that replay the events to apply the exact same changes. The replica ends up with the same data.

The one tradeoff you must understand is how synchronous it is:

• Asynchronous (the default). The primary commits and tells the client “done” without waiting for any replica. Fast, but if the primary dies before a replica has caught up, those last few transactions can be lost. There is also a small replication lag, so a read from a replica can be a little behind the primary.
• Semi synchronous. The primary waits until at least one replica has received (not necessarily applied) the change before acknowledging the commit. Safer against data loss on failover, slightly slower.
• Group replication / fully synchronous setups go further and coordinate a group of nodes for stronger guarantees, at more cost and complexity.

What replication buys you:

• Read scaling. Send heavy read traffic to replicas and keep the primary for writes. Just remember the lag, a value you wrote a moment ago might not be on the replica yet, so read your own writes from the primary when it matters.
• High availability. If the primary dies, promote a replica to be the new primary (failover).
• Backups and analytics off a replica, so you do not load the primary.

This is also the exact same binlog machinery that tools like Debezium tap into for change data capture, streaming every row change out to systems like Kafka. So the humble binlog is not just for MySQL to MySQL replication, it is the source of truth for a whole world of downstream pipelines.

---

Locking: optimistic, pessimistic, and what InnoDB does by default

The moment two people touch the same row at the same time, something has to decide who waits. There are two broad philosophies.

Pessimistic locking assumes a clash is likely, so it locks the row up front and makes everyone else wait. In MySQL you ask for this with a locking read:

-- take an exclusive lock on the row until my transaction ends
SELECT * FROM accounts WHERE id = 7 FOR UPDATE;
-- ...now update it safely; anyone else touching row 7 blocks until I commit

FOR UPDATE takes an exclusive lock, FOR SHARE a shared one, and the lock is held until you commit or roll back. Great when contention is real and transactions are short. The cost is that blocked transactions sit and wait, and if two of them wait on each other you get a deadlock (InnoDB detects it and kills one).

Optimistic locking assumes clashes are rare, so it takes no lock at all. You read the row along with a version number (or an updated_at), do your work, and only at write time check that nobody changed it underneath you:

UPDATE accounts SET balance = 900, version = version + 1
WHERE id = 7 AND version = 42;

If that UPDATE touches 0 rows, someone else bumped the version first, so you re-read and retry. No waiting, no lock held across your think-time; the cost is the occasional retry. Note this is a pattern you build, a column plus a check, MySQL has no built-in optimistic mode (though ORMs like Rails and Hibernate ship a helper for it).

So what does MySQL default to? InnoDB is pessimistic for writes. Every UPDATE, DELETE and INSERT automatically takes row-level locks on the rows it touches (and, under the default REPEATABLE READ isolation, gap / next-key locks to keep phantoms out) — you do not ask for it, it just happens, and it is lock-based, not version-based. Plain SELECTs are the happy exception: thanks to MVCC (the undo log from earlier), a normal read takes no lock and simply sees a consistent snapshot, so readers never block writers and writers never block readers. Optimistic locking is never automatic, if you want it you add the version column yourself.

---

Putting it all together

If I compress the whole journey into a few lines:

Everything sits on 16 KB pages, read in blocks because disk seeks are the expensive part, and cached hot in the buffer pool. Data and indexes are stored as B+Trees, short and wide so any row is only a few page reads away, with linked leaves that make range scans cheap. The table itself is the clustered index sorted by primary key, and secondary indexes point back to it through the primary key, which is why covering indexes are so nice. The optimizer does not blindly use your index, it weighs selectivity and can prefer a full scan when an index would cause too many random lookups. A normal B+Tree only orders one dimension, so for “near me” location queries it fails, and you switch to a spatial (R-tree / quad-tree style) index that divides space into boxes. Durability comes from WAL, log the change to the redo log first and flush pages lazily, then replay the log after a crash. The binlog is a separate, logical, append only log that powers replication and point in time recovery, copying your data to replicas for read scaling and failover. And when two writers reach for the same row, row-level locks decide who waits, pessimistic by default, while MVCC lets plain reads skip locking altogether.

None of these are really separate features. They are all consequences of two simple facts, disk is slow and works in blocks, and memory is fast but not durable. Once you see MySQL through those two facts, most of its design stops being mysterious.

If you would rather poke at these ideas than read about them, I built a set of interactive data-structure simulators to go with this post: run a query through a B-Tree and a B+Tree, or hand a latitude/longitude to a quad-tree and an R-Tree and watch which one gets to you faster.

If you want me to go deeper into any one of these, MVCC and how reads stay consistent, or how EXPLAIN plans actually read, tell me in the comments and I will write a focused follow up.