InnoDB Internals: Clustered Index, Buffer Pool, Redo, Undo, Locks

Read this lesson against PostgreSQL Internals: Heap, Tuples, Shared Buffers, WAL, VACUUM: the general concepts are identical, the implementations are close to mirror images. PostgreSQL keeps versions *in* the table and garbage-collects with VACUUM; InnoDB keeps versions *outside* it in undo logs and purges in commit order. PostgreSQL indexes store physical addresses; InnoDB indexes store primary keys. PostgreSQL protects torn pages with full-page images in WAL; InnoDB with a doublewrite buffer. Neither is "better" — each is a coherent set of choices, and the choices explain the operational advice you have heard for years (UUID primary keys, long transactions, gap-lock deadlocks).

Every InnoDB table is exactly one B+ tree keyed by the primary key, with the complete row stored in each leaf entry. There is no separate heap and no row address: the primary key *is* the address. The consequences follow mechanically. A lookup by PK reaches the row in one descent (three levels for tens of millions of rows with 16 KB pages, so root and internal pages are in memory and the cost is ~1 leaf read). A range scan by PK walks linked leaves in physical order. Rows with adjacent keys share pages, which is locality for free when the key correlates with access (an order and its items with a composite (order_id, line_no) key) and useless when it does not.

Insert order matters because the tree is the table. A monotonic key appends to the rightmost leaf; when that leaf is full, InnoDB uses a split-at-insert-point optimisation that opens a new page for the new record instead of moving half the page, so pages stay full and only the right edge is hot. A random key (UUIDv4, a hash) lands anywhere: the target leaf is usually not in the buffer pool (a read), it splits in half (two writes, and a parent update), and average fill drops toward 50–70 %. Ten million rows with a UUID PK occupy roughly 1.5× the pages of the same rows with a bigint, plus the same factor in every secondary index. If UUIDs are required, use a time-ordered one (UUIDv7, ULID) so inserts are still monotonic.

A secondary index is a second B+ tree whose leaf entries are (indexed columns, primary-key columns). Nothing in it says where the row is on disk, because rows move: a split in the clustered tree relocates half a page of rows, and if secondary indexes stored addresses every one of them would need rewriting. Storing the PK makes secondary indexes immune to row movement — at the price of a second descent: find the PK in the secondary tree, then find the row in the clustered tree. With both upper levels cached that is typically one extra leaf read, but for a query returning thousands of rows it is thousands of extra descents; MySQL's Multi-Range Read sorts the PKs first so the clustered leaves are visited in order.

Two things follow. Covering indexes are unusually powerful here: because the PK is already in every secondary leaf, an index on (status, created_at) covers SELECT id, created_at FROM orders WHERE status = ? with no second descent at all (Extra: Using index). And the PK size is paid N times: a 36-byte CHAR(36) UUID key adds 32 bytes over a bigint to every secondary entry in every index, which is what people mean when they say the primary key should be short, immutable and monotonic. Changing a row's PK moves the row and rewrites every secondary entry — an UPDATE that is really a DELETE plus INSERT everywhere.

The buffer pool (innodb_buffer_pool_size, typically 50–75 % of RAM on a dedicated server, split into instances to spread mutex contention) caches 16 KB pages on an LRU list divided at the midpoint: the newer 5/8 are the young sublist, the older 3/8 the old sublist. A page read from disk is inserted at the midpoint, i.e. at the head of the old sublist. It is promoted to young only when accessed again *after* innodb_old_blocks_time milliseconds — so a full table scan or a mysqldump, which touches each page once, cycles through the old sublist and never evicts the hot set. SHOW ENGINE INNODB STATUS reports the young/old split and the "young-making rate"; a low hit rate with a high young-making rate means the working set does not fit.

The change buffer (part of the pool, up to 25 % by default) absorbs modifications to secondary-index leaf pages that are not currently in memory: instead of reading a random index page to insert one entry, InnoDB records the change and merges it when the page is read for another reason or by a background thread. For tables with several secondary indexes and random insert keys this converts a random read+write per index per row into occasional sequential merges. It only works for non-unique indexes (a unique check needs the page) and it is why a crash leaves pending merges that recovery must complete. The adaptive hash index is the third resident: a hash table over frequently accessed B+ tree leaf entries that short-cuts descents for equality lookups.

The redo log is a fixed-size ring of files (#innodb_redo/, sized by innodb_redo_log_capacity, 100 MB default, often set to hours of writes). Every page modification appends a physiological record — "on page P, apply this change to record R" — at the next LSN, a byte offset that only increases. COMMIT flushes the log up to the transaction's last LSN (innodb_flush_log_at_trx_commit = 1; 2 writes to the OS cache and fsyncs per second, 0 neither — both trade durability for throughput exactly like PostgreSQL's synchronous_commit = off). Dirty pages sit on a flush list ordered by the LSN of their oldest modification; a fuzzy checkpoint advances the checkpoint LSN to the oldest such LSN once those pages are written. The ring may only be overwritten behind the checkpoint, so if dirty pages are not flushed fast enough the log fills and every writer stalls — "checkpoint age" is the metric.

A 16 KB page is written with multiple system calls and a crash can leave it half old, half new. Redo cannot fix that: a physiological record needs the page it is applied to be intact. So each batch of dirty pages is first written sequentially to the doublewrite buffer (its own files since 8.0.20), fsynced, then written to the pages' home locations. On recovery, any page whose checksum fails is restored from the doublewrite copy before redo is replayed from the checkpoint LSN. PostgreSQL solves the same problem the other way, by putting a full page image into the WAL on first touch after each checkpoint; InnoDB's choice keeps the redo log small and pays a second sequential write instead.

InnoDB updates rows in place and preserves the previous version in an undo log record written to a rollback segment in the undo tablespaces. The row's hidden DB_ROLL_PTR points at that record, which in turn points at the one before it, so a row's history is a chain that starts in the table page and runs backwards through undo. Undo records serve two masters: rollback (apply them in reverse to restore the row) and MVCC (reconstruct the version a reader is entitled to). Because they are written to pages in the buffer pool, undo is itself covered by redo; a crash mid-transaction is rolled back after redo replays by applying the undo records of every transaction with no commit record.

A reader's read view (created at the first consistent read under REPEATABLE READ, per statement under READ COMMITTED) records the low and high water marks of transaction ids and the list of ids active in between. For each row the reader checks DB_TRX_ID: if it is visible under the view, use the row as it is; otherwise follow DB_ROLL_PTR and apply undo records until reaching a version whose trx id is visible. The cost is proportional to how many versions have accumulated — which is why a long-running SELECT (or an idle open transaction) that prevents purge from removing old undo records slows *every* reader of a hot row, and why "History list length" in the engine status is watched like n_dead_tup in PostgreSQL. Delete-marked rows are physically removed by purge as well, once no read view can need them.

Consistent reads take no locks. Writes — and SELECT … FOR UPDATE / FOR SHARE — take row locks on the index records they touch, held until COMMIT, in a lock hash keyed by page and record heap number. Under REPEATABLE READ (the default), a locking scan also takes gap locks on the intervals *between* index records it examined and next-key locks (record + the gap before it), so no other transaction can insert a row into a range this one has read with intent to write. That is how InnoDB prevents phantoms without the predicate locks a textbook would require, and it works only because scans are over ordered B+ tree records — the gap is a real, nameable thing. An INSERT takes an insert-intention lock that waits on any gap lock covering its position.

The practical consequences: locking WHERE status = 'pending' without an index on status locks *every* row (the scan examined them all); a range WHERE id BETWEEN 10 AND 20 FOR UPDATE blocks inserts of 15 by anyone; and two transactions inserting into the same gap after each taking a shared next-key lock deadlock instantly — the most common InnoDB deadlock in the wild. READ COMMITTED drops gap locks (except for foreign-key and duplicate checks) and releases locks on non-matching rows after the statement, which is why many high-concurrency deployments choose it. The deadlock detector walks the waits-for graph on every lock wait (Deadlock Detection: The Waits-For Graph) and rolls back the transaction with the fewest modified rows; SHOW ENGINE INNODB STATUS prints the last one with both transactions' lock lists.