The idea: the table is its primary-key B+ tree
InnoDB has no separate heap for rows. A table is stored as the B+ tree of its primary key, the clustered index (called PRIMARY). The leaf pages hold the whole rows in key order. The pages above them hold node pointers: (smallest key of a child, child page number). Every page in the tree is a 16 KB index page (innodb_page_size = 16384). Leaves on the same level are linked both ways (FIL_PAGE_PREV, FIL_PAGE_NEXT), so a range scan just walks along them.
Each row also has two hidden columns: DB_TRX_ID (6 bytes, the last transaction that changed the row) and DB_ROLL_PTR (7 bytes, a pointer to the undo record that rebuilds the previous version). A table without a primary key uses its first UNIQUE NOT NULL index, or a hidden 6-byte DB_ROW_ID. The table on this page, users (id, name, bio), has 1000-byte rows, so a page takes 15 of them. On load it has 40 rows on leaf pages 5, 6 and 7 of users.ibd. Page 3 is the root of PRIMARY, and page 4 is the root of the secondary index idx_name.
Inside the page
| Part | Size | What it holds |
|---|---|---|
| FIL header | 38 B | Checksum, page number (FIL_PAGE_OFFSET), FIL_PAGE_PREV / FIL_PAGE_NEXT siblings, the LSN of the last change, page type FIL_PAGE_INDEX. |
| Page header | 56 B | PAGE_N_DIR_SLOTS, PAGE_HEAP_TOP (end of the used heap), PAGE_N_HEAP, PAGE_FREE (list of deleted records), PAGE_GARBAGE (their bytes), PAGE_LAST_INSERT, PAGE_DIRECTION, PAGE_N_RECS, PAGE_LEVEL (0 = leaf), PAGE_INDEX_ID. |
| Infimum, supremum | 13 B each | Two fake records: smaller and bigger than any key. Every list starts at infimum and ends at supremum. |
| User records | grows up | Each record has a 5-byte header (delete flag, n_owned, heap_no, record type, next_record), then the columns. |
| Free space | Between PAGE_HEAP_TOP and the directory. | |
| Page directory | 2 B per slot | Slots grow back from the end of the page; each points at a record. |
| FIL trailer | 8 B | Checksum and the low 4 bytes of the LSN, to detect a torn write. |
Records: heap_no and next_record
A new record is written where there is room: at PAGE_HEAP_TOP, or in the space of a deleted record on the PAGE_FREE list. Its heap_no is its place in that physical heap: 0 is infimum, 1 is supremum, user records start at 2. Key order is a separate thing: a singly linked list through each record's next_record offset, from infimum to supremum. On page 6, ids arrived in order, so heap order and key order match and the arrows are short hops. With UUID keys (Demo: random UUID inserts split pages) the arrows jump back and forth across the heap. Row locks name a record by (space, page, heap_no), which is why heap_no matters outside the page too (see InnoDB Gap Locks).
The page directory: binary search, then a short walk
A linked list can't be binary searched. So the records are cut into groups, and the last record of each group, its owner, has n_owned set to the size of the group. A directory slot points at each owner. The infimum's slot owns only itself, the supremum's owns 1–8 records, every other slot owns 4–8. An insert adds one to its group's owner; at 9 the group splits into 4 + 5 and a new slot appears (page_dir_split_slot). A purge takes one away; under 4 the slot borrows a record from the next group or merges with it (page_dir_balance_slot).
A lookup in a page binary-searches the slots, comparing the key with the record each slot points at, then follows next_record through at most 8 records. In Demo: lookup by primary key the root sends id 26 to page 6. Its 4 slots point at infimum, 19, 23 and supremum. Two probes (19 < 26, so low = slot 1; 23 < 26, so low = slot 2) and a walk 24 → 25 → 26 find the row. The same search runs inside the root page to pick the child.
Secondary indexes and the bookmark lookup
A secondary index is a B+ tree of its own. Its leaf records hold the indexed column and the primary key: idx_name stores (name, id). It doesn't store a page address, because rows move between pages on every split and merge; the primary key never changes. So SELECT * FROM users WHERE name = 'Wes' searches idx_name, gets id 26, and then descends PRIMARY again to read the row: a bookmark lookup (Demo: secondary index, then primary key). If the query only needs columns that are in the secondary index (SELECT id FROM users WHERE name = 'Wes'), the index is covering and the second descent is skipped. Every secondary entry carries a copy of the primary key, so a wide primary key makes every secondary index bigger.
| InnoDB (clustered) | PostgreSQL (heap) | |
|---|---|---|
| Where rows live | In the primary-key B+ tree's leaves, sorted by key | In heap pages, in no order |
| An index entry holds | Key + primary key | Key + ctid (block, line pointer) |
| Lookup by primary key | One tree descent; the leaf is the row | Index descent, then one heap page |
| Lookup by another index | Secondary tree, then the primary tree | Index, then one heap page |
| When a row moves | Nothing to fix: secondary entries hold the key | A new version gets a new ctid; every index needs an entry unless HOT |
| Range scan by primary key | Sequential leaf pages | Index order, random heap reads (unless clustered by CLUSTER) |
| Dead rows go away by | Purge, in the background | Pruning and VACUUM |
The PostgreSQL side is drawn in Inside a PostgreSQL Heap Page.
Sequential and random primary keys
The MySQL manual says InnoDB tries to leave 1/16 of a page free, so pages filled in order end up about 15/16 full; here that is 15 rows of 1000 bytes. With AUTO_INCREMENT every new id goes to the end of the last leaf. PAGE_LAST_INSERT and PAGE_DIRECTION show that the inserts are sequential. When the page is full, btr_page_split_and_insert splits at the insert point: a new page is added to the right and the new row is its only record. Nothing moves, and the old page stays 15/16 full. In Demo: AUTO_INCREMENT fills pages to 15/16, ids 41–45 fill page 7 to 15 rows and id 46 opens page 8.
A random key, such as one from UUID(), lands somewhere inside a page. When that page is full, InnoDB splits it in the middle: 8 records stay, 8 move to the new page, and both are left at 49%. After many random inserts, pages sit anywhere between half full and 15/16 full. The same rows need more pages, more buffer pool memory and more I/O, and every insert dirties a random page. Demo: random UUID inserts split pages turns two full pages into four pages at 49–55% with three inserts. The usual fixes are an AUTO_INCREMENT key with the UUID as a secondary unique key, or UUID_TO_BIN(UUID(), 1), which swaps the time fields so the values grow over time.
DELETE, purge and page merges
DELETE doesn't remove the record. It sets the delete flag in the record header, writes its own DB_TRX_ID and a DB_ROLL_PTR to the undo record, and delete-marks the secondary index entries too. An older read view can still rebuild the row from the undo log. Later, once no read view needs it, the purge threads (innodb_purge_threads) remove it: the previous record's next_record skips it, its space goes on top of PAGE_FREE, PAGE_GARBAGE grows, and its slot owns one record fewer. The next insert into the page reuses that space and its heap_no (Demo: DELETE marks, purge removes). How purge decides that nobody needs a version is shown in InnoDB Undo and Purge.
When a delete leaves a page with less data than MERGE_THRESHOLD (default 50% of the page, 8192 bytes; set per table or index with COMMENT 'MERGE_THRESHOLD=40'), btr_compress tries to merge it into its left sibling, then its right one, if the rows fit. In Demo: page under 50% is merged, deleting ids 17–27 leaves page 6 with 4 rows (24%). The left page 5 has 15 rows (15 + 4 = 19, too many ✗); the right page 7 has 10 (10 + 4 = 14 ✓). Page 6's rows are copied into page 7, page 6 goes back to the segment, and the root drops its node pointer. A threshold set too high makes pages split and merge back and forth.
See also How MySQL Runs a Query for the whole path of a statement, B+ Tree for splits and merges in general, Database Index for index lookups and range scans, the InnoDB buffer pool for how these pages are cached, and MySQL Index Access for covering indexes and index condition pushdown.
See also Row store vs column store: the same table laid out row by row and column by column, and the pages each query reads.
What the page leaves out
Real records have variable length, with a list of field lengths and a null bitmap before the header, and a split picks its middle record by bytes, not by count; here every row is 1000 bytes and the 15/16 rule is the manual's description. The root never splits here: a full root really gets copied into a new page and the tree grows a level (btr_root_raise_and_insert). Non-leaf pages have their own directory, the secondary index grows into its own multi-level tree, and its changes may go through the change buffer. Extents and the leaf and non-leaf file segments, page reorganization, compressed pages, the min-rec flag's details, redo logging of every page change (mini-transactions), row locks, the undo log's own format and purge lag are not drawn. The drawing holds 6 leaf pages.