How MySQL stores rows: the clustered index
Where the rows go
The previous article followed a row through PostgreSQL. There, a table is a heap: a pile of row versions in no particular order, with every index kept beside it as a separate structure that points in.
MySQL answers the same question differently from the first step. A row lives inside the primary key index. There is no heap. The leaf pages of the primary key’s B+ tree hold the complete rows, and that tree is the table. This article covers what the tree looks like on disk, what happens to it on every insert, update, delete and search, and how the other indexes find a row.
Two notes on names.
MySQL itself does not store rows. It hands that job to a storage engine, and since MySQL 5.5 the default engine is InnoDB. Everything below describes InnoDB, and “MySQL” in this article means MySQL with InnoDB tables.
An index that holds the table’s rows in its leaves is called a clustered index. That is an industry term, and textbooks also call a table stored this way an index-organized table. InnoDB uses the name “clustered index” directly. What follows is InnoDB’s own version of the idea, with its own page layout and its own rules for row versions.
This is the second of three articles on table storage. The first covers the same operations in PostgreSQL, and the third, still to come, compares the two.
The table is a B+ tree
Everything from the B+ tree article applies here, with one addition: the leaves hold rows, not just keys.
- Internal pages hold primary key values and the page numbers of their children, and nothing else. They route a search, exactly like the separators in the B+ tree article.
- Leaf pages hold the rows, sorted by primary key.
- The leaves are linked to both neighbours, so a scan can walk forward for
ORDER BY idand backward forORDER BY id DESC.
Every InnoDB table has a clustered index, whether you ask for one or not. InnoDB picks its key in this order:
- The
PRIMARY KEY, if the table declares one. - Otherwise, the first
UNIQUEindex whose columns are allNOT NULL. - Otherwise, a hidden 6-byte row ID that InnoDB generates. The index is then named
GEN_CLUST_INDEX, and you cannot query by its key.
Holding rows changes the fan-out at the bottom of the tree. An internal page holds only keys and page numbers, so with an integer key it has roughly a thousand children. A leaf page holds whole rows, so it fits far fewer entries: about 150 rows of 100 bytes each. A three-level tree therefore holds on the order of a hundred million such rows, and a lookup by primary key reads three pages and has the row.
Inside a page
InnoDB reads and writes pages of 16 kB by default, twice the size of a PostgreSQL page. An index page looks like this:
- The headers (94 bytes) record, among other things, the page number, the numbers of the previous and next pages on the same level, which index the page belongs to, how many records and directory slots it has, and where the free space starts.
- The records are the rows (or, in an internal page, the keys and child page numbers).
- The page directory is a small sorted array that lets a search skip through the records. It is explained below.
- The trailer (8 bytes) helps detect a damaged page. It is explained below too.
So “in primary key order” is strict between pages and logical inside one. Inserting a row into the middle of a page does not shift the rows after it. InnoDB writes the record into the free space and relinks the list.
Records: stored in arrival order, linked in key order
The records are not stored sorted. A new record is written at the start of the free space, wherever its key falls. (Space freed by purged records is tracked on a free list and reused, which this article skips.) The key order lives in the links: each record’s header stores the offset of the next record in key order. Two fixed records, the infimum (smaller than any key) and the supremum (larger than any key), mark the two ends. Following the links from the infimum visits every record from the smallest key to the largest.
It is a singly linked list: each record has a next offset and no previous offset. Records therefore only point forward. Walking backwards inside a page still works, and the page directory below is what makes it possible. The page-to-page links in the page header are the doubly linked part.
This answers the search question. A linked list cannot be binary searched, because reaching the middle means walking there, and InnoDB does not scan the list from the start either. It binary searches something else.
The page directory
The directory is an array of 2-byte slots at the end of the page, just before the trailer. It grows backwards from the page’s end, towards the records, as slots are added. Each slot holds the offset of one record, and the slots are kept in key order. The records are split into groups of four to eight neighbouring records in key order, and each slot points to the last record of its group, called the group’s owner. The owner’s header has a field, n_owned, with the size of its group. The infimum is always a group of its own, and the supremum owns the last group.
Take a page holding keys 1 to 10:
To find key 6 in this page:
- Binary search the slots. The slots are a plain array, so the binary search works as usual. It compares 6 with the key of the record each slot points to, and finds that slot 2 (key 8) is the first one whose key is not smaller than 6.
- Walk one group. The key must be in slot 2’s group, which starts right after slot 1’s owner. Start at key 4, follow the next link to 5, then to 6. Found.
A page with 100 records has about 20 slots, so the binary search takes around 5 comparisons and the walk at most 7 more links. It never scans the whole page, and it never needs a binary search over the list itself.
An insert uses the same search to find where the new record goes. The record is written into the free space and linked between its neighbours, and the n_owned of the group it joined goes up by one. If that group would grow past eight, it splits into two groups of about four and gets a new slot. So the only thing that ever shifts is the small array of 2-byte slots, never the records.
Walking backwards inside a page
A record points only to its successor, so no record can tell you which record comes before it. ORDER BY id DESC needs exactly that, one record at a time. InnoDB gets it from the page directory. To find the record before key 7, it:
- Finds the group that key 7 is in, which is the one owned by slot 2.
- Starts at the owner of the previous slot, key 4. That record is the last of the group before, so everything after it up to key 7 is in key order.
- Follows next links until the next record would be key 7. The record it stands on is the answer.
This costs a walk of at most one group, about eight links, for each step backwards. A scan in ascending order just follows the next link, so it is cheaper than one in descending order. Between pages, going backwards is simple because the pages have both a previous and a next page number.
The trailer
The 8-byte trailer is there to catch a page that was damaged or only half written. It holds two 4-byte values:
- A checksum of the page. InnoDB computes it when it writes a page from memory to disk, using CRC-32C by default, and stores it in the trailer and in the page’s header. It covers the page’s contents, headers, records and directory included, except for the checksum fields themselves. When a page is read from disk, InnoDB recomputes the checksum and compares it with the stored one. A mismatch means the page was corrupted, and InnoDB reports an error instead of using it.
- The low 32 bits of the LSN (log sequence number) of the last change to the page. The header stores the same number. A page is larger than the disk’s write unit, so a crash in the middle of a write can leave the first half new and the second half old. In that case the header and trailer disagree, and the page is known to be torn. InnoDB recovers such a page from its doublewrite buffer.
The checksum protects the page as a whole. It says nothing about whether the rows in it are correct, only that the bytes are the ones InnoDB wrote.
This is where the two databases part ways. A PostgreSQL row has a physical address, the TID, and indexes store that address. An InnoDB row has no address that anything outside its page relies on. Its identity is its primary key value, and the way to reach it is to search the tree. That is why InnoDB can move a row to another page, as a page split does, without telling any other index.
Every row has two hidden columns
InnoDB adds fields of its own to every row in the clustered index. Two of them explain almost everything else in this article:
DB_TRX_ID(6 bytes): the ID of the transaction that last inserted or updated the row. A delete counts as an update here, because it sets a flag in the record.DB_ROLL_PTR(7 bytes): the roll pointer. It points to a record in the undo log that holds what the row looked like before that transaction changed it.
A row in the clustered index is always the newest version of that row. Older versions are not kept in the table. Before a transaction changes a row, InnoDB writes what it needs to rebuild the old version into the undo log, a storage area separate from the table. Then it changes the row and points the row’s roll pointer at that undo record. The undo record holds the row’s previous DB_TRX_ID and roll pointer, so the versions form a chain that runs from the newest back to the oldest.
A reader works with a read view, InnoDB’s name for a snapshot. If the row’s DB_TRX_ID belongs to a transaction the read view can see, the reader uses the row as it is. If not, it follows the roll pointer and applies undo records until it reaches a version it is allowed to see.
This is MVCC again, the same industry term the PostgreSQL article used. The two databases implement it differently, and the difference is between storing old versions and rebuilding them.
PostgreSQL stores every version as a tuple in the heap. An update writes a new tuple, and the old one stays, linked to the new one, until VACUUM removes it.
InnoDB updates the clustered index record in place, and writes what it needs to rebuild the old version into the undo log. The record’s roll pointer, DB_ROLL_PTR, leads backward through that undo history, from the newest version to older ones.
A table to follow along with
The examples use the same table as the PostgreSQL article, in a database named bank, with one more index. The index on owner is there because a clustered index shows most of its consequences in the other indexes.
CREATE TABLE accounts (
id INT PRIMARY KEY,
owner VARCHAR(40),
balance INT,
KEY idx_owner (owner)
);
InnoDB has nothing like PostgreSQL’s pageinspect. No SQL function shows the contents of a page. So this article leans on what MySQL does expose, mainly its metadata views (the data dictionary, introduced just below) and EXPLAIN, and on the widget in the next section, which draws what a page inspector would show. All output is from MySQL 8.4.
InnoDB keeps metadata about every table and index in its data dictionary, and MySQL exposes it as read-only views in the information_schema database. This query lists the indexes of the bank/accounts table. Its output confirms two claims from above and previews a third:
SELECT i.NAME, i.TYPE, i.N_FIELDS, i.MERGE_THRESHOLD
FROM information_schema.INNODB_INDEXES i
JOIN information_schema.INNODB_TABLES t USING (TABLE_ID)
WHERE t.NAME = 'bank/accounts';
+-----------+------+----------+-----------------+
| NAME | TYPE | N_FIELDS | MERGE_THRESHOLD |
+-----------+------+----------+-----------------+
| PRIMARY | 3 | 5 | 50 |
| idx_owner | 0 | 2 | 50 |
+-----------+------+----------+-----------------+
TYPE3 is a clustered index, and 0 is an ordinary secondary index.- The table has three columns, but
PRIMARYhas five fields:id,DB_TRX_ID,DB_ROLL_PTR,ownerandbalance. The hidden columns are really there. idx_ownerwas declared on one column, but it has two fields:ownerandid. Every secondary index carries the primary key. Search explains why.
MERGE_THRESHOLD is the fill level, in percent, below which InnoDB tries to merge a page with a neighbour. The B-tree article covers merging.
See it move
The widget below holds the same table. It draws one page of each structure: the leaf page of PRIMARY, which is the table, the leaf page of idx_owner, and the undo log.
Press Insert and watch where the new row lands. Pick a row and find it by id, then by owner, and count the index descents. Update its balance, then its owner, and compare which structures change. Delete it, and then run Purge to see what is finally removed. Turn Autoplay off to move with Next step instead.
Further down, each operation has its own Watch and Step through buttons. They scroll back to this widget, set it up the way that case needs, and run it.
No separate primary key index. PRIMARY is that index and the table at once.
| owner | id | state |
|---|---|---|
| atom eve | 1 | live |
| invincible | 2 | live |
| omni-man | 3 | live |
| id | trx_id | roll_ptr | owner | balance | state |
|---|---|---|---|---|---|
| 1 | 750 | - | atom eve | 100 | live |
| 2 | 750 | - | invincible | 200 | live |
| 3 | 750 | - | omni-man | 300 | live |
| record | row | old value | old trx_id | old roll_ptr |
|---|---|---|---|---|
| no undo records | ||||
If the animation is too fast or too slow, change the speed for every visualization on this page:
Change the animation speed
The widget simplifies three things. It draws only leaf pages, not the levels above them. Every operation commits at once, so no transaction is ever left reading an old version. And it leaves out the short-lived undo records that inserts write, which Insert describes.
Insert
INSERT INTO accounts VALUES
(1, 'atom eve', 100),
(2, 'invincible', 200),
(3, 'omni-man', 300);
INSERT INTO accounts VALUES (5, 'cecil', 500);
INSERT INTO accounts VALUES (4, 'rex splode', 400);
SELECT * FROM accounts;
+----+------------+---------+
| id | owner | balance |
+----+------------+---------+
| 1 | atom eve | 100 |
| 2 | invincible | 200 |
| 3 | omni-man | 300 |
| 4 | rex splode | 400 |
| 5 | cecil | 500 |
+----+------------+---------+
Rex Splode was inserted last and comes back fourth. This query reads the whole table, which means walking the leaves of the clustered index from one end to the other, so the rows arrive in id order.
An insert does this:
- Search the clustered index for the leaf page where the new primary key belongs. The key decides the page. Free space elsewhere in the table does not matter.
- Write the row into that page, with
DB_TRX_IDset to the current transaction. InnoDB also writes a small undo record that names the new row, so that a rollback can find and remove it. That record is thrown away as soon as the transaction commits. - Split the page if it has no room, exactly as a B+ tree leaf splits: about half the rows move to a new page, and a separator goes up to the parent.
- Add an entry to every secondary index. Each entry holds the indexed columns and the row’s primary key.
There is no separate primary key index to update in step 4. In PostgreSQL, a table with a primary key and one more index does one heap write and two index inserts for a new row. Here it does one insert into the clustered index and one into idx_owner.
Keys that arrive in order, and keys that do not
Step 1 has a consequence that a heap does not have: the order in which keys arrive shapes the table.
- Increasing keys, such as an
AUTO_INCREMENTcolumn, always land at the right-hand edge of the tree. InnoDB notices the pattern. When the last page fills up, it starts a new page for the new row and does not split the full one in half. Pages end up about 15/16 full. - Random keys, such as a random UUID, land all over the tree. Any page can be the one that fills up, and it splits in the middle. Pages end up anywhere from half full to 15/16 full. Each insert also needs a different leaf page in memory.
To measure it, I loaded the same 200,000 rows into two copies of the table, once in id order and once in random order:
| Rows inserted | Leaf pages in PRIMARY |
Size |
|---|---|---|
In id order |
520 | 8.1 MB |
| In random order | 723 | 11.3 MB |
Same rows, 39% more pages. The page counts come from InnoDB’s own statistics:
SELECT index_name, stat_value AS leaf_pages
FROM mysql.innodb_index_stats
WHERE table_name = 'accounts' AND stat_name = 'n_leaf_pages';
Update
Now change Invincible’s balance:
UPDATE accounts SET balance = 250 WHERE id = 2;
SELECT * FROM accounts;
+----+------------+---------+
| id | owner | balance |
+----+------------+---------+
| 1 | atom eve | 100 |
| 2 | invincible | 250 |
| 3 | omni-man | 300 |
| 4 | rex splode | 400 |
| 5 | cecil | 500 |
+----+------------+---------+
Invincible’s row is still second. In PostgreSQL, the same update wrote a new tuple at a new address, and the row came back last. Here nothing moved. An update does three things:
- Finds the row by searching the clustered index.
- Writes an undo record with the old values of the columns that are about to change, plus the row’s current
DB_TRX_IDand roll pointer. - Changes the row in place: the new values,
DB_TRX_IDset to the current transaction, and the roll pointer set to the new undo record.
If the new values are longer and no longer fit where the row was, InnoDB rewrites the record inside the same page, and splits the page if there is no room at all. Either way the row keeps its place in key order.
What happens to the indexes
That depends on which column changed. There are three cases.
A column that no secondary index contains. Nothing happens to any index. The update above is this case: balance is in no index, so idx_owner was not touched. Unlike a PostgreSQL HOT update, this does not depend on the page having room, and it cannot fail to apply.
A column in a secondary index. Only the indexes that contain the column change. In each one, InnoDB delete-marks the old entry and inserts a new one. The old entry stays for now, because a transaction with an older read view may still need it.
UPDATE accounts SET owner = 'mark grayson' WHERE id = 2;
In idx_owner, (invincible, 2) is delete-marked and (mark grayson, 2) is added. Any other secondary index on the table is left alone. Its entries refer to the row as “primary key 2”, and that is still true.
The primary key. Now the row belongs somewhere else in the tree. InnoDB delete-marks the old row, inserts a new row at the new key, and replaces the entry in every secondary index, because all of them stored the old key. This is the most expensive update there is, which is one reason primary keys should never change.
Compare this with PostgreSQL’s write amplification. On a table with five secondary indexes, an update to one indexed column touches one index in InnoDB. In PostgreSQL, a normal update adds a new entry to all of them.
Seeing an old version
The undo log is invisible until two transactions look at the same row. Open two sessions:
-- Session A: open a transaction and take a read view now.
START TRANSACTION WITH CONSISTENT SNAPSHOT;
-- Session B: change the row and commit.
UPDATE accounts SET balance = 290 WHERE id = 2;
-- Session A
SELECT balance FROM accounts WHERE id = 2; -- returns 250
The clustered index now holds 290. Session A reads that row, sees a DB_TRX_ID that its read view cannot see, follows the roll pointer into the undo log and rebuilds the version with 250. Once session A commits, the same query returns 290.
Delete
DELETE FROM accounts WHERE id = 3;
A delete does not remove anything. InnoDB writes an undo record, sets a delete mark on the row, which is one bit in the record’s header, and stamps the row with the deleting transaction’s ID. It delete-marks the row’s entry in every secondary index too. The row stays in its page, and transactions with an older read view can still read it.
The row stops taking up space once no transaction could still see it. That work belongs to purge.
Purge: cleaning up old versions
Updates and deletes leave two kinds of leftovers. Undo records hold versions that nobody will ever read again, and delete-marked records sit in the clustered index and the secondary indexes. InnoDB’s background purge threads remove both:
- Read the history list. This is the list of undo logs from committed transactions, in the order they committed. Purge works through it from the oldest, and stops at the first one that some open read view might still need.
- Remove delete-marked records that those undo logs point to, first from the secondary indexes and then from the clustered index.
- Free the undo records themselves.
Two things differ from PostgreSQL’s VACUUM:
- Purge does not scan the table. The undo log already says which rows changed, so purge goes straight to them. VACUUM has to scan the heap, apart from the pages the visibility map lets it skip, to find dead tuples.
- An update leaves nothing behind in the table. The row was changed in place, so there is no dead version in the clustered index to remove. Only the undo record goes, plus a delete-marked secondary index entry if an indexed column changed.
Purge runs all the time, and you do not schedule it. It has the same weakness as VACUUM, though: it cannot remove anything that the oldest open read view might still need. One transaction left open for hours holds up purge for the whole server. The number to watch is the history list length:
SHOW ENGINE INNODB STATUS;
The result is one row with a long text report in its Status column. Look for this line in the TRANSACTIONS section:
History list length 39
In the mysql command-line client, end the statement with \G instead of ; to print the report as readable text. \G is a feature of that client, not SQL, so a GUI client or a driver sends it to the server and gets a syntax error.
A value that keeps climbing means purge is being held back, almost always by a long-running transaction. Meanwhile the undo log grows, and readers that need old versions walk longer and longer chains.
One job that VACUUM has is missing here. PostgreSQL has to freeze old tuples because its transaction IDs are 32 bits wide and wrap around. DB_TRX_ID is 48 bits wide, so InnoDB has no such chore.
Search
Every query has to get from “which rows match?” to the rows. In InnoDB, how far that is depends on whether the query arrives with a primary key or with something else.
Primary key lookup. Search the clustered index for the key. The row is in the leaf, so that is the whole lookup: one descent, and no second structure to visit.
Primary key range scan. Descend once to the start of the range, then walk along the leaves. This is the range scan from the B+ tree article, except that the leaves hold the rows themselves. Rows with neighbouring keys sit on the same page or on neighbouring pages, so a range of 1,000 rows reads a handful of pages.
EXPLAIN FORMAT=TREE SELECT * FROM accounts WHERE id BETWEEN 2 AND 4;
-> Filter: (accounts.id between 2 and 4) (cost=0.861 rows=3)
-> Index range scan on accounts using PRIMARY over (2 <= id <= 4) (cost=0.861 rows=3)
Full table scan. With no usable index, InnoDB walks every leaf of the clustered index from one end to the other. EXPLAIN calls it a table scan, but there is no separate table to scan.
Secondary index lookup. Search the secondary index for the key. Its entry holds a primary key value, not a location. Then search the clustered index for that primary key to reach the row. That is two descents for one row.
EXPLAIN FORMAT=TREE SELECT * FROM accounts WHERE owner = 'invincible';
-> Index lookup on accounts using idx_owner (owner='invincible') (cost=0.35 rows=1)
That second descent is the price of a clustered index. For a range over 1,000 secondary index entries, it means 1,000 separate searches of the clustered index. The upper levels of the tree stay cached, but each search ends in a leaf page that can be anywhere in the table. When a range covers a large share of the table, the optimizer gives up on the index and scans the whole table instead.
Covering index. If the secondary index contains every column the query needs, the second descent is skipped. Because every secondary index carries the primary key, this query is covered by idx_owner even though id was never declared in it:
EXPLAIN FORMAT=TREE SELECT id FROM accounts WHERE owner = 'invincible';
-> Covering index lookup on accounts using idx_owner (owner='invincible') (cost=0.35 rows=1)
There is a catch, and it is the same one as PostgreSQL’s index-only scan. Secondary index entries carry no DB_TRX_ID, so an entry cannot say which transactions may see it. InnoDB keeps one number per secondary index page instead: the ID of the newest transaction that changed anything on that page. If that transaction is visible to the reader and the entry is not delete-marked, the entry can be trusted. Otherwise InnoDB looks up the row in the clustered index after all.
The optimizer has two more ways to cut down the second descent:
- Index condition pushdown. Conditions on indexed columns are checked in the secondary index first, so rows that fail them never cost a clustered index lookup.
EXPLAINshows it asUsing index condition. - Multi-range read. MySQL collects the primary keys from the secondary index, sorts them, and then visits the clustered index in key order. It is the same idea as PostgreSQL’s bitmap heap scan.
EXPLAINshows it asUsing MRR, and the optimizer chooses it only when it expects the sorting to pay off.
Descending order with LIMIT
A descending scan with a LIMIT is a good test of how the leaves are used. To make it cross a page boundary I loaded 40 rows, with ids 1 to 40, into the same accounts table.
SELECT id FROM accounts WHERE id >= 12 ORDER BY id DESC LIMIT 14;
40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27
The rows come back from the largest id downwards, and nothing is sorted. The plan says why:
EXPLAIN FORMAT=TREE SELECT * FROM accounts WHERE id >= 12 ORDER BY id DESC LIMIT 14;
-> Limit: 14 row(s) (cost=6.07 rows=14)
-> Filter: (accounts.id >= 12) (cost=6.07 rows=29)
-> Index range scan on accounts using PRIMARY over (12 <= id) (reverse) (cost=6.07 rows=29)
The plan is a range scan over 12 <= id on the clustered index, read in reverse. The traditional EXPLAIN shows the same thing as Backward index scan in its Extra column, and it has no Using filesort.
The scan does not start at id 12. The range is 12 <= id, so its upper end is the end of the table, and a reverse scan begins there. Id 12 is only where the scan would stop. Here it never gets that far, because LIMIT 14 is satisfied at id 27.
This is not the same query as WHERE id >= 12 ORDER BY id LIMIT 14. That one starts at 12, goes up, and returns 12 to 25. The descending one returns the 14 largest ids that are 12 or higher. Both read about 14 rows and touch only the pages they pass through, however large the table is.
Every other index goes through the primary key
Putting it all together: in InnoDB the table is the clustered index, and every other index maps its key to a primary key value.
In the industry’s terms, InnoDB has exactly one clustered index per table, and every other index is a secondary index. PostgreSQL, as the last article showed, has only secondary indexes and no clustered index at all.
The design has consequences in both directions:
- Primary key lookups and range scans are as short as they can be. The search ends at the row.
- Every other lookup pays for two descents, unless a covering index avoids the second.
- The primary key is stored in every secondary index entry. A long primary key makes every index on the table bigger. I loaded the same 200,000 rows into a table with an
INTprimary key and into one with aCHAR(36)UUID primary key.idx_owner, which is declared the same way on both, took 278 leaf pages on the first and 686 on the second. - A row can move and no index has to know. Page splits and merges move rows between pages all the time. Index entries hold a primary key, not a location, so they stay correct.
- The primary key is a storage decision, not just a constraint. It should be short, because every index repeats it. It should increase, because random keys split pages. And it should never be updated. An
AUTO_INCREMENTinteger is the usual choice. A random UUID stored as text is the worst case on the first two counts.
Two more InnoDB mechanisms deal with the cost of maintaining B+ trees. Both get a closer look in the comparison article that will close this series:
- InnoDB tries to merge a page with a neighbour only when it falls below
MERGE_THRESHOLD, 50% by default, as the B-tree article mentioned. - The change buffer can hold back changes to secondary index pages that are not in memory and apply them later in batches. Since MySQL 8.4 it is switched off by default.
Summary
| Operation | Clustered index (the table) | Secondary indexes | Undo log |
|---|---|---|---|
| Insert | New row at its place in key order. A full page splits | New entry with the key and the primary key, in every index | A record that is dropped at commit |
| Update, column not indexed | Row changed in place | Nothing | Old values |
| Update, indexed column | Row changed in place | Old entry delete-marked and new entry added, only in indexes on that column | Old values |
| Update, primary key | Old row delete-marked, new row inserted | Entry replaced in every index | Old row |
| Delete | Row delete-marked. It stays | Entries delete-marked | What is needed to bring the row back |
| Search | By primary key, the search ends at the row | Gives a primary key, then a second descent. A covering index skips it | Read only by transactions that need an older version |
| Purge | Removes delete-marked rows | Removes delete-marked entries | Frees records no read view needs |
InnoDB’s design comes down to one choice: the row lives in the primary key index, and only its newest version lives there. That makes primary key reads short, keeps most updates away from the indexes, and keeps old versions out of the table. The price is paid in secondary index lookups that search two trees, in a primary key that is copied into every index and dictates where each insert goes, and in rollbacks and old read views that have to work their way through the undo log.
The final article in this series will put this design next to PostgreSQL’s heap, operation by operation.