Digging into MariaDB's Source 10: InnoDB Part 1 — Pages, the Buffer Pool and B-trees

What this post covers

This is the tenth post in the "Digging into MariaDB's Source" series. In Part 9 we followed the server layer's executor through wrappers such as handler::ha_rnd_next(), ha_index_read_map() and ha_write_row() down to the engine's virtual functions ha_innobase::rnd_next(), index_read() and write_row(). The server layer stops there. Where InnoDB keeps a row underneath, in what shape, and how it finds it again is none of the server layer's business.

This post zooms into the area below ⑦ the handler boundary, ⑧ the engine, on the Part 2 map. It is the first of three InnoDB posts (Parts 10–12) and looks at the containers that hold data: pages, the buffer pool and B-trees. Transactions and locks come in Part 11, the redo log and recovery in Part 12.

Blue boxes are what this post reads; grey boxes are covered in the posts before and after.

There are four questions to answer.

• How is the InnoDB source divided, and which layers does a call pass through from ha_innobase down to the disk?
• What does one "page" of innodb_page_size=16384 contain, and in what order? Can we open an .ibd file and read it ourselves?
• How is the memory from innodb_buffer_pool_size used? Which pages stay, which get pushed out, and when are modified pages written to disk?
• Where in the source is "an InnoDB table is a B-tree sorted by primary key"? What happens when a page fills up?

Every line number in this post refers to that commit. Part 1 explains how to get the source at the same commit and build the Docker image used for the examples.

storage/innobase/ alone has over 300,000 lines of C++, and buf0buf.cc and btr0cur.cc, which this post reads, are thousands of lines each. This post keeps only the main path one SELECT and one INSERT take. What was left out is named, with its location, under "What this post leaves out" at the end.

Terms to know first

Page. The smallest unit InnoDB moves between disk and memory. The default size is 16KB (innodb_page_size, UNIV_PAGE_SIZE_DEF = 1 << 14, univ.i line 211); even if you want one row, InnoDB reads the whole 16KB page that holds it. Pages are numbered from 0 inside a tablespace (one .ibd file per table, or the system tablespace ibdata1), and the pair (tablespace id, page number) is a page's address, page_id_t.

Buffer pool. The cache that keeps pages read from disk in memory. innodb_buffer_pool_size (default 128MB) is its size. Whether InnoDB reads or writes a row, it works on a page in the buffer pool; in ordinary reads and writes it never modifies a page on disk directly (exceptions that edit the file directly, such as importing a tablespace with ALTER TABLE … IMPORT TABLESPACE, are not covered here).

Dirty page. A page modified in the buffer pool but not yet written to disk. Even a commit does not write it right away; why that is still safe is the redo log, covered in Part 12.

B-tree and clustered index. Every InnoDB index is a B-tree (strictly, a B+tree whose leaves are linked), and one node of the tree is one page. The leaves of the clustered index (usually the PRIMARY KEY) hold every column of the row, so in InnoDB "the table = the clustered index". The leaves of a secondary index hold the indexed columns plus the primary key.

Latch and mini-transaction (mtr). A latch is a short lock that stops several threads from touching one page at the same time. It is different from the row locks users take (SELECT … FOR UPDATE, Part 11); it is held only for the microseconds it takes to read or modify a page. A mini-transaction, mtr_t, is the object that handles "latch a few pages, modify them, record the changes as redo, release the latches" as one bundle. Within one user transaction (BEGIN … COMMIT) countless mtrs start and finish.

LSN (Log Sequence Number). A position in the redo log counted in bytes, a 64-bit number that only ever grows. Every page records in its header "the LSN of the last change that modified this page". In this post we only meet it as a number in page headers; the details are in Part 12.

1. A map of the InnoDB folders — the layers below the handler

The InnoDB source is split across 30-odd folders under storage/innobase/. File names follow a rule, so the name alone tells you roughly what lives where.

• <module>0<name>.cc — what comes before the digit 0 is the module (folder) name. buf0buf.cc is the core of the buf module, buf0lru.cc its LRU part, buf0flu.cc its flush (writing to disk) part.
• Declarations are gathered in include/ — include/buf0buf.h, with small inline functions in .inl files such as include/btr0cur.inl.
• Function names start with the module name too — buf_page_get_gen(), btr_cur_t::search_leaf(), page_cur_search_with_match(), mtr_t::commit().

Here are the folders this post visits, from top to bottom, that is, from the side closest to the server layer to the side closest to the disk.

Yellow boxes are memory and files; grey boxes are not covered in this post.

(The file counts are the .cc and .h files counted with ls at the reference commit.)

The bridge: ha_innobase and row_prebuilt_t

When the server layer opens a table it gets one handler object (Part 2). For an InnoDB table that is class ha_innobase final : public handler (handler/ha_innodb.h line 63), and that object holds its InnoDB-side partner, a row_prebuilt_t (m_prebuilt, line 518).

struct row_prebuilt_t {
	ulint		magic_n;	/*!< this magic number is set to
					ROW_PREBUILT_ALLOCATED when created,
					or ROW_PREBUILT_FREED when the
					struct has been freed */
	dict_table_t*	table;		/*!< Innobase table handle */
	dict_index_t*	index;		/*!< current index for a search, if
					any */
	trx_t*		trx;		/*!< current transaction handle */
// ...
	btr_pcur_t*	pcur;		/*!< persistent cursor used in selects
					and updates */
	btr_pcur_t*	clust_pcur;	/*!< persistent cursor used in
					some selects and updates */

storage/innobase/include/row0mysql.h lines 463–559

As the name says, it is a bundle of things "built in advance". Just as the server layer's handler is "one open table", row_prebuilt_t is "one open table" seen from InnoDB's side. It holds InnoDB's table definition (dict_table_t), the index used for the current search (dict_index_t), the current transaction (trx_t, Part 11), and a persistent cursor, btr_pcur_t, that remembers a position in the B-tree. This struct travels along when ha_innobase::index_read() carries its key down into row_search_mvcc(), and when ha_innobase::write_row() goes down into row_insert_for_mysql(). The conversion table between the server layer's row format (TABLE::record[0]) and InnoDB's record format (mysql_template) lives here too.

We confirm the actual call order with gdb in example 4 of section 5.

2. One 16KB page

The FIL header and trailer — common to every page

Whatever its type (index, undo, allocation data …), a page in an InnoDB file starts with a 38-byte FIL header and ends with an 8-byte FIL trailer. include/fil0fil.h writes the byte positions down as #defines (lines 1234–1292).

The page type values are in the same file. In the first four pages of a new .ibd file we meet FIL_PAGE_TYPE_FSP_HDR = 8 (page 0, the tablespace header), FIL_PAGE_IBUF_BITMAP = 5 (page 1, a bitmap of the old change buffer, no longer used), FIL_PAGE_INODE = 3 (page 2, file segment information) and FIL_PAGE_INDEX = 17855 (page 3, the root of the first index) (lines 1329–1364).

Part of the LSN is written again in the trailer so that a "torn page", one where power failed mid-write leaving new content at the front and old content at the back, can be detected. With full_crc32, the default checksum format at the reference commit, the last 4 bytes of the page hold a CRC-32C of everything before them (buf_flush_assign_full_crc32_checksum(), buf/buf0flu.cc lines 428–439).

The index page — header, records, directory

An index page, a node of a B-tree, puts an index page header right after the FIL header (at byte 38).

#define	PAGE_HEADER	FSEG_PAGE_DATA	/* index page header starts at this
				offset */
/*-----------------------------*/
#define PAGE_N_DIR_SLOTS 0	/* number of slots in page directory */
#define	PAGE_HEAP_TOP	 2	/* pointer to record heap top */
#define	PAGE_N_HEAP	 4	/* number of records in the heap,
				bit 15=flag: new-style compact page format */
#define	PAGE_FREE	 6	/* pointer to start of page free record list */
#define	PAGE_GARBAGE	 8	/* number of bytes in deleted records */
#define	PAGE_LAST_INSERT 10	/* pointer to the last inserted record, or
				0 if this info has been reset by a delete,
				for example */
// ...
#define	PAGE_N_RECS	 16	/* number of user records on the page */
// ...
#define	PAGE_LEVEL	 26	/* level of the node in an index tree; the
				leaf level is the level 0.  This field should
				not be written to after page creation. */
#define	PAGE_INDEX_ID	 28	/* index id where the page belongs.
				This field should not be written to after
				page creation. */

storage/innobase/include/page0page.h lines 48–111

After the header, from byte 94 (PAGE_DATA), come the records. They always begin with two fake records called infimum and supremum. The infimum is smaller than any key and the supremum larger than any key; they mark the boundaries, so "before the first record" and "after the last record" need no special cases. On a new-format page (COMPACT, DYNAMIC) the infimum sits at byte 99 and the supremum at byte 112 (PAGE_NEW_INFIMUM, PAGE_NEW_SUPREMUM, lines 141–146).

The record heap grows from front to back, the directory from back to front, and the free space lies between.

Records are stacked on the heap in insertion order. Key order is kept by a "next record" pointer in each record's header. Sorting is done with a linked list and storage only ever stacks, so the bytes in a page need not be shuffled to keep things in order. The 5-byte header of a new-format record (REC_N_NEW_EXTRA_BYTES = 5) looks like this.

/* Offsets of the bit-fields in a new-style record. NOTE! In the table the
most significant bytes and bits are written below less significant.

	(1) byte offset		(2) bit usage within byte
	downward from
	origin ->	1	8 bits relative offset of next record
			2	8 bits relative offset of next record
				  the relative offset is an unsigned 16-bit
				  integer:
				  (offset_of_next_record
				   - offset_of_this_record) mod 64Ki,
				  where mod is the modulo as a non-negative
				  number;
				  we can calculate the offset of the next
				  record with the formula:
				  relative_offset + offset_of_this_record
				  mod srv_page_size
			3	3 bits status:
					000=REC_STATUS_ORDINARY
					001=REC_STATUS_NODE_PTR
					010=REC_STATUS_INFIMUM
					011=REC_STATUS_SUPREMUM
					100=REC_STATUS_INSTANT
					1xx=reserved
				5 bits heap number
			4	8 bits heap number
			5	4 bits n_owned
				4 bits info bits
*/

storage/innobase/include/rem0rec.inl lines 48–76

• next: the relative distance to the next record (2 bytes). Because it is a distance, not an absolute position, nothing needs fixing when the whole page is copied elsewhere.
• status: ordinary record (000), node pointer in a non-leaf B-tree node (001), infimum (010), supremum (011).
• heap number: the order in which the record was created on the heap. The infimum is 0, the supremum 1, user records start at 2 (page0page.h lines 153–158). Row locks use this number to point at a record (Part 11).
• n_owned: a value tied to the page directory below.

With only a linked list, finding one record would mean following it from start to end. That is why the end of the page holds a page directory. For every group of 4–8 records (PAGE_DIR_SLOT_MIN_N_OWNED = 4, PAGE_DIR_SLOT_MAX_N_OWNED = 8; the first and last slots may own fewer than 4 — lines 187–191) it stores the position of the group's last record in a 2-byte slot, and that record's n_owned says "how many I represent". The slots are in key order, so they can be binary-searched (section 5).

Example 1: opening an .ibd file with od

We create a three-row table, run FLUSH TABLES … FOR EXPORT (a statement that returns once all of the table's dirty pages are on disk), and read the .ibd file with od. All examples in this post were run with MariaDB 13.2.0 (13.2.0-MariaDB-debug), a Debug build of the reference commit (c894d97781) as-is, in a Docker container (Ubuntu 24.04).

# Example written for this post (not MariaDB source)
mariadb -e "CREATE DATABASE lab;
  CREATE TABLE lab.t (id INT PRIMARY KEY, name VARCHAR(20)) ENGINE=InnoDB;
  INSERT INTO lab.t VALUES (1,'one'),(2,'two'),(3,'three');"
# ... (the SELECTs that print the settings and the root page number from INNODB_SYS_INDEXES are omitted)
F=/var/lib/mariadb-lab/lab/t.ibd
# FLUSH TABLES ... FOR EXPORT returns after writing all of this table's dirty pages to disk.
# The connection has to stay open meanwhile, so hold it with SLEEP and read the file in between.
mariadb -e "FLUSH TABLES lab.t FOR EXPORT; SELECT SLEEP(4)" > /dev/null &
sleep 2
# ... (the part that prints the file size is omitted)
# u16, u32, u64: small helpers that read 2-, 4- and 8-byte big-endian integers with od (omitted)
for p in 0 1 2 3; do
  b=$(( p * 16384 ))
  printf "%-5s %-12s %-10s %-6s\n" $p $(u32 $F $b+4) $(u64 $F $b+16) $(u16 $F $b+24)
done
# ... (the parts that read the page header, records and directory go with the output below)

The full script is ex/u10-page-header/run.sh in the examples folder. The first part of the output:

+--------------------+-----------------------------+-----------------------------+
 @@innodb_page_size | @@innodb_default_row_format | @@innodb_checksum_algorithm |
+--------------------+-----------------------------+-----------------------------+
              16384 | dynamic                     | full_crc32                  |
+--------------------+-----------------------------+-----------------------------+
+------------+-----------+-------+
 index_name | root_page | SPACE |
+------------+-----------+-------+
 PRIMARY    |         3 |     8 |
+------------+-----------+-------+
--- 1. file size and number of 16KB pages
65536 bytes
4 pages
--- 2. FIL header of each page (FIL_PAGE_OFFSET @4, FIL_PAGE_LSN @16, FIL_PAGE_TYPE @24)
page  offset_field lsn        type
0     0            53441      8
1     1            53120      5
2     2            53441      3
3     3            54811      17855
--- 3. first 38 bytes of page 3 (the FIL header)
0049152 00 00 00 00 00 00 00 03 ff ff ff ff ff ff ff ff
0049168 00 00 00 00 00 00 d6 1b 45 bf 00 00 00 00 00 00
0049184 00 00 00 00 00 08
0049190

• The file is four 16KB pages, and their types are, as above, 8 (FSP header) → 5 (old bitmap) → 3 (INODE) → 17855 (index). This matches root page 3 that INNODB_SYS_INDEXES reported for PRIMARY.
• Reading page 3's FIL header byte by byte: from byte 4, 00 00 00 03 (page number 3); then ff ff ff ff twice (no previous or next page — FIL_NULL); from byte 16 the 8-byte LSN …d6 1b (=54811); at byte 24 45 bf (=17855); at byte 34 00 00 00 08 (tablespace id 8).
• Re-running this example, which starts from an empty data directory and does the same steps, gave the same LSN values, but they change with different server settings or a different history.

Next, the index page header and the records.

--- 4. index page header of page 3 (starts at byte 38)
PAGE_N_DIR_SLOTS = 2
PAGE_HEAP_TOP    = 203
PAGE_N_HEAP      = 32773  (bit 15 = compact format)
PAGE_N_RECS      = 3
PAGE_LEVEL       = 0
PAGE_INDEX_ID    = 23
--- 5. bytes 94..157 of page 3: infimum, supremum, first user record
0049246 01 00 02 00 1c 69 6e 66 69 6d 75 6d 00 04 00 0b  >.....infimum....<
0049262 00 00 73 75 70 72 65 6d 75 6d 03 00 00 00 10 00  >..supremum......<
0049278 1b 80 00 00 01 00 00 00 00 00 13 84 00 00 00 2e  >................<
0049294 01 10 6f 6e 65 03 00 00 00 18 00 1b 80 00 00 02  >..one...........<
0049310
--- 6. page directory: last bytes of page 3 (slots, then 8-byte FIL trailer)
0065520 00 00 00 00 00 70 00 63 00 00 d6 1b 51 90 4b 4c
0065536

Hold each byte up against the definitions in the source and the page reads itself.

1. Header: 3 records (PAGE_N_RECS), a leaf (PAGE_LEVEL = 0 — with only three rows, the root is also the leaf), 5 records on the heap (the low bits of PAGE_N_HEAP = 0x8005 — infimum, supremum and 3 user records; the top bit marks the new format).
2. infimum (bytes 94–106): the 5-byte header 01 00 02 00 1c followed by the literal text infimum\0. Decoded, the header says n_owned=1, heap number 0 with status 010 (infimum), next=0x1c=28 — so the first user record is at 99+28=127.
3. supremum (bytes 107–119): header 04 00 0b 00 00 (n_owned=4 — it represents itself and the 3 user records; heap number 1 with status 011; next=0 — the end), then supremum.
4. First user record: the 03 at byte 120 is the length of the name column (3 bytes) and the 00 at byte 121 is the NULL bitmap (no column is NULL) — variable-length column lengths and NULL bits are stored in reverse in front of the record header. Bytes 122–126 are the header 00 00 10 00 1b (heap number 2, next=27 → byte 154), and the data starts at byte 127. 80 00 00 01 is id = 1 (integers are stored big-endian with the sign bit flipped so that they sort correctly), the next 6 bytes 00 00 00 00 00 13 are the hidden column DB_TRX_ID (the id of the transaction that inserted the row), the next 7 bytes 84 00 00 00 2e 01 10 are DB_ROLL_PTR (a pointer to an undo record, Part 11), and then one. The next record (03 00 00 00 18 00 1b 80 00 00 02 …) starts right after.
5. Directory and trailer: the last 8 bytes 00 00 d6 1b | 51 90 4b 4c are the trailer (the low 4 bytes of the LSN, d6 1b, match the LSN in the header; the last 4 bytes are the CRC-32C), and right before them 00 63 (=99, the infimum) and 00 70 (=112, the supremum) are the two directory slots (PAGE_N_DIR_SLOTS = 2). You can see the directory growing forward from the end of the page.

The lengths of DB_TRX_ID (6 bytes) and DB_ROLL_PTR (7 bytes) match DATA_TRX_ID_LEN and DATA_ROLL_PTR_LEN in include/data0type.h (lines 156–159). These two hidden columns are attached to every record of a clustered index; we see where that happens in section 5. After stopping the server, summarizing the same file with the bundled tool innochecksum -S gives the same picture: 1 index page, 1 INODE page, 1 bitmap page and 1 FSP header page (step 7 of the example script prints it; it is not shown here).

Easy to confuse: an .ibd file on a running server can be stale

If you read the file right after INSERT without FLUSH TABLES … FOR EXPORT, the records may not be there. A commit writes only the redo log to disk and leaves the pages dirty in the buffer pool (section 4). That is why the example uses FOR EXPORT to get all of the table's pages written before reading.

3. The buffer pool — keeping pages in memory

buf_pool_t, buf_block_t, buf_page_t

There is one buffer pool per server (extern buf_pool_t buf_pool;, include/buf0buf.h line 1964). Inside it are thousands to millions of slots, each holding one page; one slot is a buf_block_t, and its first member is the descriptor of one page, buf_page_t.

Only the members used in this post are shown.

These are the buf_page_t members this post uses (include/buf0buf.h lines 484–591).

• id_ — which page of which tablespace (page_id_t).
• frame — the memory address of the 16KB page contents. The bytes we read with od in section 2 live here in memory.
• lock — this page's latch.
• oldest_modification_ — the LSN of the oldest change that dirtied this page. 0 means a clean page.
• access_time — the time of the first access (or the last promotion). Used by the LRU (section 4).
• list, LRU — the links that hang it on one of the lists below.

buf_pool_t manages pages with one hash table and three lists.

At startup buf_pool_t::create() takes innodb_buffer_pool_size worth of memory, carves it into slots and puts them all on the free list.

  for (char *extent= memory,
         *end= memory + block_descriptors_in_bytes(n_blocks);
       extent < end; extent+= innodb_buffer_pool_extent_size)
  {
    buf_block_t *block= reinterpret_cast<buf_block_t*>(extent);
    const buf_block_t *extent_end= block + pages_in_extent[ssize];
    if (reinterpret_cast<const char*>(extent_end) > end)
      extent_end= reinterpret_cast<buf_block_t*>(end);
    MEM_MAKE_DEFINED(block, (extent_end - block) * sizeof *block);
    for (byte *frame= reinterpret_cast<byte*>(extent) +
           first_frame_in_extent[ssize];
         block < extent_end; block++, frame+= srv_page_size)
    {
      ut_ad(!memcmp(block, field_ref_zero, sizeof *block));
      block->page.frame= frame;
      block->page.lock.init();
      UT_LIST_ADD_LAST(free, &block->page);
      ut_d(block->page.in_free_list= true);
    }

storage/innobase/buf/buf0buf.cc lines 1475–1493

Within the same chunk of memory, an array of block descriptors (buf_block_t) comes first and the 16KB frames follow (repeating every innodb_buffer_pool_extent_size, which is 8MB on 64-bit — the comment at buf0buf.h lines 1161–1164). So 128MB gives a little fewer than 128MB ÷ 16KB = 8192 page slots — POOL_SIZE shows 8096 in example 2. At the reference commit, a larger address range (innodb_buffer_pool_size_max, 8TB by default on 64-bit) is reserved first and only the requested size is backed by real memory (my_virtual_mem_reserve(), my_virtual_mem_commit(), lines 1373–1453). The point is to let SET GLOBAL innodb_buffer_pool_size change the size while the server runs.

buf_page_get_gen() — the entrance to every page access

Almost every piece of InnoDB code that needs a page calls buf_page_get_gen() (or a function wrapping it). The B-tree search in section 5 does too. Its arguments are the page address, the latch mode wanted (RW_S_LATCH for reading, RW_X_LATCH for writing …) and the mini-transaction this access belongs to.

	/* A memory transaction would frequently be aborted here. */
	hash_lock.lock_shared();
	block = reinterpret_cast<buf_block_t*>(
		buf_pool.page_hash.get(page_id, chain));
	if (UNIV_LIKELY(block != nullptr)) {
		state = block->page.fix();
		hash_lock.unlock_shared();
		goto got_block;
	}
	hash_lock.unlock_shared();
// ...
	/* Page not in buf_pool: needs to be read from file */
	switch (mode) {
	case BUF_GET_IF_IN_POOL:
	case BUF_PEEK_IF_IN_POOL:
		break;
	default:
		block = buf_read_page(page_id, err, chain);

storage/innobase/buf/buf0buf.cc lines 2906–2923

1. Look it up in page_hash. If it is there (a hit), pin the block with fix(). Pinning (buffer-fix) means "someone is using this, don't hand this slot to another page".
2. If not (a miss), buf_read_page() reads it from disk.
3. Finally, take the wanted latch, record the block in the mini-transaction's memo (mtr->memo_push()) and return it (lines 3075–3110). The latch is released not by this function but later, by mtr_t::commit() (section 6).

On a miss, buf_read_page() (buf/buf0rea.cc lines 510–550) gets an empty block from buf_LRU_get_free_block(), registers that block in page_hash and the LRU first in buf_page_init_for_read(), and then reads the file.

    block= nullptr;
    reinterpret_cast<buf_block_t*>(bpage)->
      initialise(page_id, ssize, READ_BUF_FIX);
    /* x_unlock() will be invoked
    in buf_page_t::read_complete() by the io-handler thread. */
    bpage->lock.x_lock(true);
    /* Insert into the hash table of file pages */
    buf_pool.page_hash.append(chain, bpage);
    hash_lock.unlock();

    /* The block must be put to the LRU list, to the old blocks */
    buf_LRU_add_block(bpage, true/* to old blocks */);

storage/innobase/buf/buf0rea.cc lines 113–124

The block goes into page_hash before the read finishes so that another thread wanting the same page waits on this block instead of reading the disk a second time (during the read the block is locked with the READ_FIX state and an X latch). And, as the comment says, a freshly read page goes into the old part of the LRU list. That is the topic of the next section. When the read completes, buf_page_t::read_complete() checks the checksum (buf_page_check_corrupt()) and, for a corrupted page, evicts it from the buffer pool and returns an error (from line 3718).

The upper box is a hit and the lower one a miss. Either way it ends with "take the latch and record it in the mtr".

In SHOW GLOBAL STATUS, Innodb_buffer_pool_read_requests counts page requests and Innodb_buffer_pool_reads counts how many of them went to disk. Example 2 watches both.

Easy to confuse: there is one buffer pool

If you have seen innodb_buffer_pool_instances (splitting the buffer pool into several pieces) in older explanations or blogs, the reference commit has no such structure. buf_pool is a single global object, and contention is reduced in other ways, such as splitting page_hash across several latches (page_hash_latch, from line 1494). This post did not trace in the source when that changed.

4. The LRU list and dirty pages — what to keep and when to write

The old part: so that a one-off scan does not push out the cache

When empty blocks run short, InnoDB evicts from the tail of the LRU list (the least recently used end). But one full scan of a big table could turn thousands of pages nobody will look at again into "recently used pages" and push out the pages that really are used often. InnoDB's answer is to split the LRU list into two parts.

• The young part (about 63% at the head) and the old part (about 37% at the tail). buf_pool.LRU_old points at the boundary, and the ratio is innodb_old_blocks_pct (default 100 * 3 / 8 = 37, handler/ha_innodb.cc lines 20194–20197).
• A page freshly read from disk goes near the front of the old part (buf_LRU_add_block(bpage, true)). A newly created page (a new page made by INSERT) and a promoted page go to the head (false).
• A page in the old part only becomes eligible to move up to young when it is accessed again after innodb_old_blocks_time (default 1000 milliseconds, lines 20199–20204) has passed since its first access. A full scan reads a page in a burst of a few milliseconds and moves on, so it never earns that eligibility; the page stays in the old part and is pushed out at the tail.

buf_LRU_add_block(
	buf_page_t*	bpage,	/*!< in: control block */
	bool		old)	/*!< in: true if should be put to the old blocks
				in the LRU list, else put to the start; if the
				LRU list is very short, the block is added to
				the start, regardless of this parameter */
{
	mysql_mutex_assert_owner(&buf_pool.mutex);
	ut_ad(!bpage->in_LRU_list);

	if (!old || (UT_LIST_GET_LEN(buf_pool.LRU) < BUF_LRU_OLD_MIN_LEN)) {
		UT_LIST_ADD_FIRST(buf_pool.LRU, bpage);
	} else {
// ... (UNIV_LRU_DEBUG checks omitted)
		UT_LIST_INSERT_AFTER(buf_pool.LRU, buf_pool.LRU_old,
			bpage);

		buf_pool.LRU_old_len++;
	}

storage/innobase/buf/buf0lru.cc lines 644–670

While the LRU list is still short (under BUF_LRU_OLD_MIN_LEN = 512 pages, include/buf0lru.h line 41) there is no old part at all and everything goes to the head.

Promotion is split into "flagging" and "moving" — something new in recent versions

At the reference commit there is a catch. When a page is accessed again it is not moved to the head of the LRU list on the spot. The LRU list is guarded by the single buf_pool.mutex, and taking that mutex on every page touch was a bottleneck. Instead, the accessing side only leaves a promotion flag, with touch() (buf/buf0buf.cc lines 3239–3254). On a first access touch() stamps the time (access_time) and then calls the function below.

inline void buf_page_t::touch_no_stamp() noexcept
{
  if (zip.is_promote())
    return;
  const uint16_t threshold= buf_pool.LRU_old_threshold;
  if (threshold)
  {
    const uint16_t t= access_time;
    /* access_clock advances once per refresh_clock(), so a difference
    of threshold ticks can span less than threshold seconds. One more
    tick ensures that at least threshold seconds have elapsed. */
    if (!t || uint16_t(buf_pool.access_clock - t) <= threshold)
      return;
  }
  zip.set_promote();
}

storage/innobase/include/buf0buf.h lines 2141–2156

On the first access the difference from the time just stamped is 0, so it simply returns (if innodb_old_blocks_time is 0, threshold is 0 and the flag is set from the first access); on a later access it sets the promotion flag (set_promote()) only if more than LRU_old_threshold seconds (innodb_old_blocks_time rounded up to seconds) have passed since the first access. The actual moving of the block to the head is done by whoever walks the LRU list or the flush_list while holding buf_pool.mutex anyway — the page cleaner's LRU and flush_list sweeps, and the LRU scan looking for an empty block — with make_young_if_needed() as they pass by (buf/buf0flu.cc line 1324, line 1519, buf/buf0lru.cc line 233). If the flag is set, make_young() clears it, stamps a new time, takes the block off the LRU list and puts it back at the head (buf_LRU_add_block(this, false), buf/buf0lru.cc lines 710–719).

According to the git history of the reference commit, this design came in with commit db94f391be4 in November 2025 ("MDEV-33966: buf_page_make_young() is a contention point"). Its commit message says that "before, such a block was moved on any access". We did not compare this with the source of the commonly used LTS releases (11.4, 11.8), so all we can say about the behaviour in this section is "this is how it is at the reference commit".

The blue boxes are the two steps of promotion at the reference commit.

Getting an empty block: buf_LRU_get_free_block()

Reading a page from disk needs an empty block. The comment at the head of buf_LRU_get_free_block() sums up the steps (buf/buf0lru.cc lines 326–346). A user thread only ever takes blocks from the free list. If the free list is empty it scans up to 100 pages at the LRU tail to evict a clean page, and if that fails it wakes the page cleaner and waits. A dirty page cannot be evicted right away even at the tail — throwing it away before writing it would lose the changes. When such waiting happens, buf_pool.stat.LRU_waits goes up, and if it goes on for long a warning appears in the error log (buf_pool_t::LRU_warn()).

Dirty pages and the page cleaner

When a page is modified (mtr_t::commit() in section 6) it goes onto the flush_list. Writing to disk is the job of a single background thread called the page cleaner (buf_flush_page_cleaner(), buf/buf0flu.cc lines 2804–3105). While it has work it wakes up every second (or when someone wakes it) and decides what to write and how much; once it has nothing to do and goes idle, it sleeps until someone wakes it (page_cleaner_wakeup(), lines 2851–2865). In broad strokes:

1. If empty blocks are urgently needed (buf_pool.need_LRU_eviction()), it writes and evicts from the LRU tail (buf_flush_LRU()).
2. Otherwise it computes the ratio of dirty pages.

    const ulint dirty_blocks= UT_LIST_GET_LEN(buf_pool.flush_list);
    /* We perform dirty reads of the LRU+free list lengths here.
    Division by zero is not possible, because buf_pool.flush_list is
    guaranteed to be nonempty, and it is a subset of buf_pool.LRU. */
    const double dirty_pct= double(dirty_blocks) * 100.0 /
      double(UT_LIST_GET_LEN(buf_pool.LRU) + UT_LIST_GET_LEN(buf_pool.free));
    pct_lwm= srv_max_dirty_pages_pct_lwm;
// ...
    else if (dirty_pct < srv_max_buf_pool_modified_pct)
    possibly_unemployed:
// ...
      if (!soft_lsn_limit && !af_needed_for_redo(oldest_lsn))
        goto set_idle;

storage/innobase/buf/buf0flu.cc lines 2975–3023

3. If the ratio is below innodb_max_dirty_pages_pct (default 90, ha_innodb.cc lines 19710–19713), innodb_max_dirty_pages_pct_lwm (default 0) is off, and there is no need to hurry because of redo log space (af_needed_for_redo()), it writes nothing and goes idle (goto set_idle).
4. Otherwise it writes from the tail of the flush_list (the oldest changes) with buf_flush_list_holding_mutex(). How many pages is decided by innodb_adaptive_flushing (adaptive flushing) and innodb_io_capacity.

Step 3 matters. As example 2 shows, on an idle server dirty pages simply stay unwritten. If the same page is modified again, one disk write can carry several changes at once, so postponing pays off, and if the server dies in the meantime the redo log can bring the changes back (Part 12). The limit of that postponing is when the redo log fills up and the checkpoint has to move forward (af_needed_for_redo() and buf_flush_sync_lsn, Part 12).

Example 2: looking inside the buffer pool through information_schema

INNODB_BUFFER_PAGE shows the buffer pool's pages one row per page (handler/i_s.cc), and INNODB_BUFFER_POOL_STATS shows the lengths of the lists above. We load a 40,000-row table (200 bytes per row) and look inside. pages.sql is a query on INNODB_BUFFER_PAGE that counts the pages with TABLE_NAME = '`lab`.`big`' — the number of pages, how many of them are dirty (OLDEST_MODIFICATION > 0), how many are in the old part (IS_OLD), and the average number of rows per page.

# Example written for this post (not MariaDB source)
mariadb -e "CREATE DATABASE lab;
  CREATE TABLE lab.big (id INT PRIMARY KEY, pad CHAR(200)) ENGINE=InnoDB;
  INSERT INTO lab.big SELECT seq, REPEAT('x',200) FROM lab.seq_1_to_40000;"
# ... (the SELECT @@… that prints the settings and the echo lines that print step titles are omitted)
mariadb -t < pages.sql                 # 1. right after INSERT
# ... (the SELECT on INNODB_BUFFER_POOL_STATS is omitted)
sleep 5; mariadb -t < pages.sql        # 2. 5 seconds later
mariadb -e "SET GLOBAL innodb_max_dirty_pages_pct=0"
sleep 3; mariadb -t < pages.sql        # 3. after lowering the dirty-ratio limit to 0
# Empty the buffer pool and restart. Turn off reloading the page list saved at shutdown so it starts empty.
lab-stop
lab-start --innodb-buffer-pool-load-at-startup=0
mariadb -t < pages.sql                 # 4. right after the restart (empty: no lab.big pages yet)
mariadb -t lab < scan.sql              # 5-7. two full scans, then an UPDATE

(seq_1_to_40000 is a virtual table of the SEQUENCE engine that returns the numbers 1 to 40000 as rows.) This server runs with the defaults: innodb_buffer_pool_size 128MB, innodb_old_blocks_pct 37, innodb_old_blocks_time 1000, innodb_max_dirty_pages_pct 90, innodb_max_dirty_pages_pct_lwm 0 (checked with SELECT @@… in the example). The first part of the output (partly shown):

--- 1. right after INSERT: pages of lab.big in the buffer pool
+------------+-----------+-------+-------+------+----------+
 INDEX_NAME | PAGE_TYPE | pages | dirty | old  | avg_recs |
+------------+-----------+-------+-------+------+----------+
 PRIMARY    | INDEX     |   599 |   599 |   17 |       68 |
+------------+-----------+-------+-------+------+----------+
+-----------+--------------+----------------+--------------------+-------------------------+
 POOL_SIZE | FREE_BUFFERS | DATABASE_PAGES | OLD_DATABASE_PAGES | MODIFIED_DATABASE_PAGES |
+-----------+--------------+----------------+--------------------+-------------------------+
      8096 |         7153 |            943 |                328 |                     657 |
+-----------+--------------+----------------+--------------------+-------------------------+
--- 2. 5 seconds later: still dirty
(same table as step 1 — all 599 pages dirty)
--- 3. SET GLOBAL innodb_max_dirty_pages_pct=0, 3 seconds later
+------------+-----------+-------+-------+------+----------+
 INDEX_NAME | PAGE_TYPE | pages | dirty | old  | avg_recs |
+------------+-----------+-------+-------+------+----------+
 PRIMARY    | INDEX     |   599 |     0 |   27 |       68 |
+------------+-----------+-------+-------+------+----------+

• 40,000 rows take 599 pages (68 rows each on average). All 599 are dirty. The commit is done, yet not a single page has been written to disk.
• POOL_SIZE 8096 = FREE_BUFFERS 7153 + DATABASE_PAGES 943 (pages on the LRU list, system tables and so on included). As noted above, a little under 8192.
• Because INSERT created these pages, only 17 are old — consistent with new pages going to the head (buf_LRU_add_block(bpage, false)).
• Five seconds later all 599 are still dirty. The dirty ratio is 657 ÷ 8096 ≈ 8%, far below 90%, and on a freshly started server there is plenty of redo space, so the page cleaner went idle in step 3.
• After lowering innodb_max_dirty_pages_pct to 0, the count drops to 0 within 3 seconds. The comparison dirty_pct < srv_max_buf_pool_modified_pct became false, so it took step 4.

Next, the output after emptying the buffer pool and restarting (scan.sql uses a stored procedure that snapshots status variables and prints the differences; the full file is in the examples folder).

| --- 5. 1st full scan (cold) |
 INNODB_BUFFER_POOL_PAGES_MADE_YOUNG |     0 |
 INNODB_BUFFER_POOL_READ_REQUESTS    |   624 |
 INNODB_BUFFER_POOL_READS            |   609 |
 DATABASE_PAGES | OLD_DATABASE_PAGES | MODIFIED_DATABASE_PAGES |
            880 |                344 |                       1 |
 PRIMARY    | INDEX     |   599 |     0 |  136 |       68 |

 --- 6. 2nd full scan, 3 seconds later (warm) |
 INNODB_BUFFER_POOL_PAGES_MADE_YOUNG |     0 |
 INNODB_BUFFER_POOL_READ_REQUESTS    |   614 |
 INNODB_BUFFER_POOL_READS            |     0 |
 DATABASE_PAGES | OLD_DATABASE_PAGES | MODIFIED_DATABASE_PAGES |
            880 |                344 |                       1 |
 PRIMARY    | INDEX     |   599 |     0 |  136 |       68 |

 --- 7. UPDATE every row, then let the page cleaner flush |
 INNODB_BUFFER_POOL_PAGES_MADE_YOUNG |    302 |
 INNODB_BUFFER_POOL_READ_REQUESTS    | 124024 |
 INNODB_BUFFER_POOL_READS            |      1 |
 DATABASE_PAGES | OLD_DATABASE_PAGES | MODIFIED_DATABASE_PAGES |
            881 |                345 |                       0 |
 PRIMARY    | INDEX     |   599 |     0 |   67 |       68 |

(The table border lines were removed. The numbers in step 7 vary a little from run to run depending on when the page cleaner sweeps — a second run gave PAGES_MADE_YOUNG 331 and 64 old pages.)

• First scan: 609 of 624 page requests went to disk (a miss in buf_page_get_gen() → buf_read_page()). Second scan: 614 requests, 0 disk reads — all hits.
• Across the whole buffer pool, 344 of the 880 LRU pages are old, 39%, close to innodb_old_blocks_pct = 37. lab.big's pages entered near the front of the old part, but the boundary (LRU_old) kept sliding toward the tail to hold the ratio, so some of the pages read first ended up in front of it (young) and only 136 stayed old (buf_LRU_old_adjust_len(), from buf0lru.cc line 446).
• The second scan came 3 seconds later, and still PAGES_MADE_YOUNG is 0. Even if the accesses left promotion flags, nobody has walked the LRU list yet, so no page has been moved.
• Only after we UPDATE every row and let the page cleaner walk the flush_list does PAGES_MADE_YOUNG rise by 302 and lab.big's old pages drop from 136 to 67. The make_young_if_needed<false, true>() called in the flush_list sweep only moves flagged blocks that are in the old part (buf0flu.cc lines 1516–1519). This example cannot tell whether those 302 pages were flagged by the second scan or by the UPDATE. What it shows is just this: "moving happens not on access, but when someone walks the list".

5. B-trees — the table is the clustered index

Clustered and secondary indexes

The rows of an InnoDB table live in the leaves of the clustered index. When a table is created, if it has a primary key that index is created first and becomes the clustered index; if not, InnoDB creates a GEN_CLUST_INDEX ordered by a hidden 6-byte row number, DB_ROW_ID.

	if (m_form->s->keys == 0 || primary_key_no == -1) {
		/* Create an index which is used as the clustered index;
		order the rows by their row id which is internally generated
		by InnoDB */
		ulint flags = m_table->flags;
		dict_index_t* index = dict_mem_index_create(
			m_table, GEN_CLUST_INDEX.str,
			DICT_CLUSTERED, 0);
// ...
	if (primary_key_no != -1) {
		/* In InnoDB the clustered index must always be created
		first */
		if ((error = create_index(m_trx, m_form, o, m_table,
					  (uint) primary_key_no))) {

storage/innobase/handler/ha_innodb.cc lines 13079–13102

When InnoDB builds its internal index definition, it appends the hidden columns DB_TRX_ID and DB_ROLL_PTR after the key columns of the clustered index (and DB_ROW_ID before them if there is no primary key) (dict_index_build_internal_clust(), dict/dict0dict.cc lines 2315–2374) — those are the 6 and 7 bytes we saw after id in example 1. A secondary index gets the clustered index's key columns appended after its own columns.

	/* Add to new_index the columns necessary to determine the clustered
	index entry uniquely */

	for (i = 0; i < clust_index->n_uniq; i++) {
		field = dict_index_get_nth_field(clust_index, i);

		if (!indexed[field->col->ind] || index->is_spatial()) {
			dict_index_add_col(new_index, table, field->col,
					   field->prefix_len,
					   field->descending);
		}
	}

storage/innobase/dict/dict0dict.cc lines 2482–2493

So what you find in a secondary index leaf is not the row's location (a page number) but the primary key value, and if other columns are needed InnoDB has to descend the clustered index once more with that key. This design means that when a page split moves a row to another page, secondary indexes need no fixing. The price is that a long primary key makes every secondary index bigger.

A tree of height 2. One page is one node, and the root page number never changes.

The records in the tree's non-leaf nodes are node pointers: the smallest key in a child page paired with that child's page number (REC_NODE_PTR_SIZE = 4 bytes), with status 001 in the record header (section 2). Leaves are PAGE_LEVEL = 0, the level above is 1, then 2 …, and pages on the same level are linked both ways by the FIL header's FIL_PAGE_PREV/FIL_PAGE_NEXT, so a range search (WHERE id BETWEEN …) or a full scan can move sideways along the leaves alone.

btr_cur_t::search_leaf() — from the root to a leaf

The function that finds a leaf for one key is btr_cur_t::search_leaf(). It spans lines 1095–1606, over 500 lines, but most of that is about how to take and release latches; the skeleton is a single loop.

  /* Start with the root page. */
  page_id_t page_id(index()->table->space_id, index()->page);
// ...
 search_loop:
  auto block_savepoint= mtr->get_savepoint();
  buf_block_t *block=
    buf_page_get_gen(page_id, zip_size, rw_latch, guess, BUF_GET, mtr, &err);
  if (!block)
  {
    btr_read_failed(err, *index());
    goto func_exit;
  }
// ...
  const bool not_first_access{block->page.touch()};
// ...
  uint32_t page_level= btr_page_get_level(block->page.frame);
// ...
  if (!height)
  {
    /* We reached the leaf level. */
// ...
  reached_latched_leaf:
    if (!(tuple->info_bits & REC_INFO_MIN_REC_FLAG))
    {
      if (page_cur_search_with_match_bytes(*tuple, mode, &up_match, &low_match,
                                           &page_cur, &up_bytes, &low_bytes))
        goto corrupted;
    }
    else if (page_cur_search_with_match(tuple, mode, &up_match, &low_match,
                                        &page_cur, nullptr))
      goto corrupted;
// ...
  guess= nullptr;
  if (page_cur_search_with_match(tuple, page_mode, &up_match, &low_match,
                                 &page_cur, nullptr))
    goto corrupted;
  offsets= rec_get_offsets(page_cur.rec, index(), offsets, 0, ULINT_UNDEFINED,
                           &heap);
// ...
  /* Go to the child node */
  page_id.set_page_no(btr_node_ptr_get_child_page_no(page_cur.rec, offsets));

  if (!--height)
// ...
  goto search_loop;

storage/innobase/btr/btr0cur.cc lines 1234–1605

1. It starts at the root. The index's root page number is in the index definition (dict_index_t::page). INNODB_SYS_INDEXES.PAGE_NO in example 1 is this value.
2. It gets the page with buf_page_get_gen() (section 3) and records the access with touch() (section 4).
3. If the page is not a leaf, it finds the node pointer the key belongs under with page_cur_search_with_match(), switches page_id to the child page number stored there, and goes back to search_loop.
4. At a leaf (height == 0) it finds the position inside the leaf and finishes. At the leaf it uses (except in the special case of looking for the smallest record, REC_INFO_MIN_REC_FLAG) page_cur_search_with_match_bytes(), which compares down to bytes (to leave information the adaptive hash index can use, up_bytes and low_bytes); at non-leaf nodes it uses page_cur_search_with_match(). The two search the same way.

On the way down, latches are handed over from top to bottom. The child's latch is taken and then the parent's latch is released (mtr->rollback_to_savepoint() drops the parent block from the memo and releases its latch, lines 1349–1352), so a read search holds latches on only one or two pages at a time. The latch on the whole index (index()->lock) is normally taken in S mode; only for writes that may change the tree's shape (BTR_MODIFY_TREE) is it taken in SX/X mode (lines 1183–1217).

At the head of the function there is also a shortcut that skips the tree using the adaptive hash index (AHI, btr_search_guess_on_hash()), but at the reference commit the default is innodb_adaptive_hash_index=OFF (ha_innodb.cc lines 19848–19855).

Searching inside a page — binary search on the directory + a short linear search

  size_t low= 0, up= ulint{page_dir_get_n_slots(page)} - 1;
  const rec_t *mid_rec;

  /* Perform binary search until the lower and upper limit directory
  slots come to the distance 1 of each other */
  while (up - low > 1)
  {
    const size_t mid= (low + up) / 2;
    mid_rec=
      page_dir_slot_get_rec_validate(page, page_dir_get_nth_slot(page, mid));
    if (UNIV_UNLIKELY(!mid_rec))
      return true;
    uint16_t cur= std::min(low_fields, up_fields);
    int cmp= page_cur_dtuple_cmp(*tuple, mid_rec, index, &cur, comp, leaf);
    if (cmp > 0)
    low_slot_match:
      low= mid, low_fields= cur;
    else if (cmp)
    up_slot_match:
      up= mid, up_fields= cur;
    else if (mode == PAGE_CUR_G || mode == PAGE_CUR_LE)
      goto low_slot_match;
    else
      goto up_slot_match;
  }

storage/innobase/page/page0cur.cc lines 870–894

This is where the page directory from section 2 is used. The slots are in key order, so a binary search narrows the low and up slots down to neighbours, and the 4–8 records between them are compared linearly by following next pointers (lines 903–938). Worth noticing: the comparison carries along how many leading fields are already known to match (low_fields, up_fields) and starts comparing from the next field. Before all that, a "last insert position shortcut" (page_cur_try_search_shortcut(), which looks at PAGE_LAST_INSERT and PAGE_N_DIRECTION, lines 845–857) skips even the binary search while sequential inserts continue.

A 16KB page holds hundreds of node pointers, so trees are very shallow. As example 3 shows, even 150,000 rows of 200 bytes make a tree of height 3. A primary key lookup reads three pages, and the higher a page is in the tree, the more lookups pass through it, so it tends to stay in the buffer pool.

When a page is full: splitting

row_ins_clust_index_entry() first descends optimistically, latching only the leaf page (BTR_MODIFY_LEAF), and simply tries to insert with btr_cur_optimistic_insert(). If there is no room (DB_FAIL), it descends again pessimistically, also taking the index tree latch (BTR_MODIFY_TREE) (row/row0ins.cc lines 3324–3346), and if there is still no room, btr_cur_pessimistic_insert() calls btr_root_raise_and_insert() if the page is the root, or btr_page_split_and_insert() otherwise (btr/btr0cur.cc lines 2651–2665).

The root is not split; it is raised one level. All of the root's records are moved to a new page, only one node pointer to that new page is left in the root, and then the new page is split (btr/btr0btr.cc lines 1832–1834). So the root page number (page 3 in a new .ibd) stays the same however much the tree grows, and the tree grows upward.

btr_page_split_and_insert() numbers its steps — 1. decide where to split, 2. allocate a new page, 3. find the first record of the upper half, 4. fix the tree structure first (the parent's node pointer, the sibling links), 5. move the records, 6–8. retry the insert (from line 2819). The interesting one is step 1.

	/* 1. Decide the split record; split_rec == NULL means that the
	tuple to be inserted should be the first record on the upper
	half-page */
	bool insert_left = false;
	uint32_t hint_page_no = block->page.id().page_no() + 1;
	byte direction = FSP_UP;

// ...
	} else if (btr_page_get_split_rec_to_right(cursor, &split_rec)) {
	} else if ((split_rec = btr_page_get_split_rec_to_left(cursor))) {
		direction = FSP_DOWN;
		hint_page_no -= 2;
	} else {
		/* If there is only one record in the index page, we
		can't split the node in the middle by default. We need
		to determine whether the new record will be inserted
		to the left or right. */

		if (page_get_n_recs(page) > 1) {
			split_rec = page_get_middle_rec(page);

storage/innobase/btr/btr0btr.cc lines 2884–2909

Where to split is decided by looking at the insert pattern.

• If this insert lands right after the previous insert (PAGE_LAST_INSERT), InnoDB assumes sequential inserts to the right (btr_page_get_split_rec_to_right(), from line 2066): almost all existing records stay on the left page, and the new record onward goes to the new right page. With inserts that always land at the end, like an AUTO_INCREMENT primary key, the left page stays full and no new rows come to it.
• For sequential inserts in the other direction, it splits to the left (btr_page_get_split_rec_to_left()).
• Otherwise it splits in the middle (page_get_middle_rec()), leaving two half-full pages.

Before splitting, it also tries inserting into the right sibling page if that has room (btr_insert_into_right_sibling()). Splits are counted in buf_pool.pages_split, visible as Innodb_buffer_pool_pages_split in SHOW GLOBAL STATUS. Note that the counter is bumped at the very start of btr_page_split_and_insert(), before the right-sibling attempt (line 2853), so it also counts cases that ended with an insert into the right sibling and never actually split.

Example 3: growing a table and counting height and splits

We grow rows of the same shape (id INT PRIMARY KEY, pad CHAR(200)) in order, read the root page's (page 3) PAGE_LEVEL with od each time, and count splits. Then we compare the leaf pages of a table that got 40,000 rows in order with one that got the same rows shuffled.

# Example written for this post (not MariaDB source)
# ... (creating the seq_ins, seq40 and rnd40 tables and defining u16 are omitted)
# Read PAGE_LEVEL and PAGE_N_RECS from the root page (page 3) of table $1, after FOR EXPORT gets its dirty pages written.
tree() {
  mariadb -e "FLUSH TABLES lab.$1 FOR EXPORT; SELECT SLEEP(2)" > /dev/null &
  sleep 1
  b=$(( 3*16384 + 38 ))     # index page header of page 3
  echo "$1: rows=$2 ... PAGE_LEVEL=$(u16 /var/lib/mariadb-lab/lab/$1.ibd $b+26) ..."   # (shortened)
  wait
}

done_rows=0
for n in 1 60 70 1000 40000 150000; do
  mariadb -e "INSERT INTO lab.seq_ins SELECT seq, REPEAT('x',200) FROM lab.seq_$((done_rows+1))_to_$n"
  tree seq_ins $n            # splits are counted from Innodb_buffer_pool_pages_split before and after (omitted)
  done_rows=$n
done
# The same 40000 rows in order (seq40) / shuffled (rnd40): (seq*7919) % 40000 + 1 yields each of 1..40000 once, shuffled
mariadb -e "INSERT INTO lab.seq40 SELECT seq, REPEAT('x',200) FROM lab.seq_1_to_40000"
mariadb -e "INSERT INTO lab.rnd40 SELECT (seq*7919) % 40000 + 1, REPEAT('x',200) FROM lab.seq_0_to_39999"
# ... (the tree output for both tables and the SELECT that counts leaf pages in INNODB_BUFFER_PAGE are omitted)

--- 1. sequential inserts: height grows as rows grow
    page splits during this batch: 0
seq_ins: rows=1 root_page=3 PAGE_LEVEL=0 (height 1) root_PAGE_N_RECS=1 file_pages=4
    page splits during this batch: 0
seq_ins: rows=60 root_page=3 PAGE_LEVEL=0 (height 1) root_PAGE_N_RECS=60 file_pages=4
    page splits during this batch: 1
seq_ins: rows=70 root_page=3 PAGE_LEVEL=1 (height 2) root_PAGE_N_RECS=2 file_pages=6
    page splits during this batch: 14
seq_ins: rows=1000 root_page=3 PAGE_LEVEL=1 (height 2) root_PAGE_N_RECS=16 file_pages=21
    page splits during this batch: 582
seq_ins: rows=40000 root_page=3 PAGE_LEVEL=1 (height 2) root_PAGE_N_RECS=598 file_pages=1088
    page splits during this batch: 1644
seq_ins: rows=150000 root_page=3 PAGE_LEVEL=2 (height 3) root_PAGE_N_RECS=3 file_pages=2816
--- 2. 40000 rows in order vs. the same 40000 rows shuffled
    seq40 page splits: 597
    rnd40 page splits: 966
seq40: rows=40000 root_page=3 PAGE_LEVEL=1 (height 2) root_PAGE_N_RECS=598 file_pages=1088
rnd40: rows=40000 root_page=3 PAGE_LEVEL=1 (height 2) root_PAGE_N_RECS=953 file_pages=1600
--- 3. leaf pages (every page except the root 3, since the height is 2) and how full they are
+---------------+------------+----------+----------------+------------+
 TABLE_NAME    | leaf_pages | avg_recs | avg_data_bytes | pct_of_16k |
+---------------+------------+----------+----------------+------------+
 `lab`.`seq40` |        598 |       67 |          15050 |         92 |
 `lab`.`rnd40` |        953 |       42 |           9444 |         58 |
+---------------+------------+----------+----------------+------------+

• Up to 60 rows the root is the leaf (height 1, 60 records in the root). While rows 61–70 go in, the root is raised one level to height 2 and keeps only 2 node pointers to the two leaves. The root number is still 3.
• At 40,000 rows there are 598 leaves and 598 node pointers in the root, still height 2. At 150,000 rows the root is raised again to height 3 (the root holds 3 pointers to 3 non-leaf nodes).
• The same 40,000 rows fill 598 leaves to 92% when inserted in order, but 953 leaves to only 58% when shuffled. The split counts are 597 versus 966 (for seq40, 598 leaves = 597 splits + 1 exactly; rnd40 has 14 fewer leaves than 966 + 1 — apparently because, as noted above, the counter also counts inserts that ended in the right sibling). With sequential inserts the "sequential inserts to the right" rule keeps the left page full; with shuffled inserts pages are split in the middle and half-full pages appear. This is why a random primary key such as a UUID makes a table bigger and lets less of it fit in the buffer pool.
• file_pages (file size ÷ 16KB) is larger than the actual number of index pages, apparently because the page allocation module (fsp/) extends the tablespace file several pages at a time; this post did not trace that code.

Because the split point differs, the same number of rows needs 1.6 times as many leaf pages. The numbers are Example 3's actual output (parts 2 and 3).

Example 4: how SELECT and INSERT reach the B-tree (gdb)

We attach gdb to the running mariadbd and print the call stack at the moment (1) a primary key lookup reaches btr_cur_t::search_leaf() and (2) an INSERT starting from the 61st row splits a page. Background threads (such as purge, which cleans up old row versions and deleted rows that are no longer needed, Part 11) also read B-trees, so we first stop at ha_innobase::index_read and then stop at search_leaf only in that thread.

# Example written for this post (not MariaDB source)
# Stop at index_read first, then stop at search_leaf only in the same thread (to avoid background threads)
gdb -p "$(cat /tmp/mariadbd.pid)" -batch \
    -ex 'break ha_innobase::index_read' -ex 'continue' \
    -ex 'break btr_cur_t::search_leaf thread $_thread' -ex 'continue' -ex 'bt' \
    -ex 'print index()->name.m_name' -ex 'print index()->page' \
    -ex 'delete' -ex 'detach' > /tmp/g1.txt 2>/dev/null &
sleep 5
mariadb -e "SELECT id FROM lab.t WHERE id = 42" > /dev/null
# ... (creating the 60-row lab.t, trimming the backtrace, and the second gdb run
#      that stops at btr_page_split_and_insert while inserting rows 61-70 are omitted)

=== 1. SELECT ... WHERE id = 42 : ha_innobase::index_read -> btr_cur_t::search_leaf
#0  btr_cur_t::search_leaf at storage/innobase/btr/btr0cur.cc:1098
#1  btr_pcur_open_with_no_init at storage/innobase/include/btr0pcur.inl:322
#2  row_search_mvcc<InnoDBPolicy<true, true> > at storage/innobase/row/row0sel.cc:4909
#3  ha_innobase::index_read at storage/innobase/handler/ha_innodb.cc:9220
#4  handler::index_read_map at sql/handler.h:4443
#5  handler::index_read_idx_map at sql/handler.cc:7862
#6  handler::ha_index_read_idx_map at sql/handler.cc:4249
#7  join_read_const at sql/sql_select.cc:26187
#8  join_read_const_table at sql/sql_select.cc:26037
#9  make_join_statistics at sql/sql_select.cc:6084
#10 JOIN::optimize_inner at sql/sql_select.cc:2779
#11 JOIN::optimize at sql/sql_select.cc:2032
#12 mysql_select at sql/sql_select.cc:5447
...
#17 dispatch_command at sql/sql_parse.cc:1903
#18 do_command at sql/sql_parse.cc:1437
$1 = 0x7711fc043e48 "PRIMARY"
$2 = 3

(Arguments and addresses were removed, and #13–#16 are handle_select → execute_sqlcom_select → mysql_execute_command → mysql_parse, so they were cut. The address in $1 differs from run to run.)

• ha_innobase::index_read() → row_search_mvcc() (line 9220) → btr_pcur_open_with_no_init(), which opens a persistent cursor → search_leaf(). That cursor is the pcur held by the row_prebuilt_t from section 1.
• The index searched is PRIMARY, and the root page number it starts from (index()->page) is 3, the same number we read from the file in examples 1 and 3.
• This lookup happened during optimization, not execution (#9 make_join_statistics → join_read_const_table). With an equality on the primary key like WHERE id = 42 there is at most one row, so the optimizer reads it in advance and turns it into a constant — the "constant table" of Part 8.

=== 2. INSERT of the 61st..70th row: btr_page_split_and_insert
#0  btr_page_split_and_insert at storage/innobase/btr/btr0btr.cc:2844
#1  btr_root_raise_and_insert at storage/innobase/btr/btr0btr.cc:2005
#2  btr_cur_pessimistic_insert at storage/innobase/btr/btr0cur.cc:2656
#3  row_ins_clust_index_entry_low at storage/innobase/row/row0ins.cc:2958
...
#9  row_insert_for_mysql at storage/innobase/row/row0mysql.cc:1311
#10 ha_innobase::write_row at storage/innobase/handler/ha_innodb.cc:7970
#11 handler::ha_write_row at sql/handler.cc:8666
#12 Write_record::single_insert at sql/sql_insert.cc:2396
#13 Write_record::write_record at sql/sql_insert.cc:2438
#14 select_insert::send_data at sql/sql_insert.cc:4564
...
#27 do_command at sql/sql_parse.cc:1437
$1 = 0x7711fc043e48 "PRIMARY"
$2 = 0
$3 = 4

(#4–#8 are row_ins_clust_index_entry → row_ins_index_entry → row_ins_index_entry_step → row_ins → row_ins_step, and #15–#26 are select_result_sink::send_data_with_check followed by end_send → evaluate_join_record → sub_select → do_select → JOIN::exec … dispatch_command, seen in Part 9, so they were cut.)

• Part 9's write path Write_record::single_insert() → handler::ha_write_row() → ha_innobase::write_row() continues straight into row_insert_for_mysql() → row_ins_clust_index_entry_low(), which inserts into the clustered index → the pessimistic insert → raising the root → the split.
• The page being split is page 4, at height 0 (a leaf): the new page the root's (page 3's) records were just moved to. "Empty the root into a new page, then split the new page" is right there.

6. The mini-transaction mtr_t — page latches and redo in one bundle

An mtr has followed us through all the code so far. buf_page_get_gen() recorded the latch it took with mtr->memo_push(), search_leaf() released the parent's latch with mtr->rollback_to_savepoint(), and a split modified several pages inside one mtr.

A mini-transaction is "the smallest unit that changes pages consistently". A page split must allocate a new page, move records, add a node pointer to the parent and fix the sibling links before the B-tree is in a correct shape again. No other thread may see the half-done state, and recovery must never restore a state where the server died halfway through. For that, an mtr collects two things.

• m_memo — the list of latches (pages, index trees) this mtr holds. The latches are all released at commit(), so other threads never see a half-modified page.
• m_log — the redo records for the changes this mtr made to pages. At commit() they are appended to the redo log buffer all at once. During recovery, one mtr's records are either all there or not there at all (Part 12).

mtr_t::start() (mtr/mtr0mtr.cc lines 189–219) only empties these two; the work is in commit().

void mtr_t::commit()
// ...
  if (m_modifications && (m_log_mode == MTR_LOG_NO_REDO || !m_log.empty()))
// ...
    std::pair<lsn_t,lsn_t> lsns{do_write()};
    process_freed_pages();

storage/innobase/mtr/mtr0mtr.cc lines 534–554

If there were changes, do_write() appends m_log to the redo log and gets back this mtr's LSN (Part 12 goes into this). Then commit_log() does two things for each modified page.

    while (it != mtr->m_memo.rend())
    {
      const mtr_memo_slot_t &slot= *it++;
      if (slot.type & MTR_MEMO_MODIFY)
      {
// ...
        modified++;
        buf_block_t *b= static_cast<buf_block_t*>(slot.object);
// ...
        mach_write_to_8(b->page.frame + FIL_PAGE_LSN, mtr->m_commit_lsn);
        if (UNIV_LIKELY_NULL(b->page.zip.data))
          memcpy_aligned<8>(FIL_PAGE_LSN + b->page.zip.data,
                            FIL_PAGE_LSN + b->page.frame, 8);
        buf_pool.insert_into_flush_list(prev, b, lsns.first);
      }
    }

storage/innobase/mtr/mtr0mtr.cc lines 431–452

1. It writes this mtr's LSN into the page's FIL header field FIL_PAGE_LSN (mach_write_to_8(b->page.frame + FIL_PAGE_LSN, …)). The LSN we read with od in example 1 was written here.
2. If the mtr dirtied a clean page for the first time (m_made_dirty), it puts the page onto the flush_list (insert_into_flush_list() — a page that is already dirty is left where it is, lines 154–183). Then it checks whether to wake the page cleaner (page_cleaner_wakeup()).

After that, release() releases the latches in m_memo and unpins the blocks. The order matters: first put the redo records into the log, then mark the pages dirty, and only last release the latches. The promise that a page is only ever written to disk after the redo that modified it is in the log (WAL, write-ahead logging) starts with this order. It is also why the page cleaner in section 4 could postpone dirty pages with peace of mind.

Redo goes into the log first, then the page is marked dirty, and the latches are released last. The order comes from mtr0mtr.cc lines 431–452 and 534–554 quoted above.

Easy to confuse: an mtr is not a transaction

Despite "transaction" in its name, mtr_t has no rollback that undoes changes. The similarly named mtr_t::rollback_to_savepoint() only releases latches on pages that were not modified, and it asserts that no modified page is among them (ut_ad(!(slot.type & MTR_MEMO_MODIFY)), mtr/mtr0mtr.cc lines 581–596). An mtr that has started modifying pages must go all the way to commit() — which is also what the split function's comment means by "the operation of this function must always succeed, we cannot reverse it". When a user runs ROLLBACK, InnoDB opens new mtrs and applies the opposite changes according to the undo records (Part 11). Within one user transaction, mtrs are opened and closed many times.

What this post leaves out

• Tablespaces and page allocation (extents, file segments, FSP_HDR, XDES and INODE pages): storage/innobase/fsp/fsp0fsp.cc, btr_page_alloc()
• Files and I/O (fil_space_t, fil_node_t, asynchronous I/O, tpool/): storage/innobase/fil/fil0fil.cc, storage/innobase/os/os0file.cc
• The doublewrite buffer (recovering from torn pages): storage/innobase/buf/buf0dblwr.cc
• Read-ahead: buf_read_ahead_random(), buf_read_ahead_linear()
• Buffer pool dump and load (innodb_buffer_pool_dump_at_shutdown, the feature turned off in example 2): storage/innobase/buf/buf0dump.cc
• Resizing the buffer pool: buf_pool_t::resize()
• The adaptive hash index: storage/innobase/btr/btr0sea.cc
• Compressed tables (ROW_FORMAT=COMPRESSED, unzip_LRU, the buddy allocator): storage/innobase/page/page0zip.cc, buf/buf0buddy.cc
• Page merges and record deletion (btr_compress(), btr_cur_pessimistic_delete()): storage/innobase/btr/btr0btr.cc, btr0cur.cc
• Storing big columns off-page (BLOB pages, dtuple_convert_big_rec()): storage/innobase/btr/btr0cur.cc
• Bulk loading (btr_bulk, the sort-then-load of ALTER TABLE and CREATE INDEX): storage/innobase/btr/btr0bulk.cc
• Spatial R-tree indexes: storage/innobase/gis/
• Page states (NOT_USED, MEMORY, UNFIXED, READ_FIX, WRITE_FIX … of buf_page_t::state()) and the transition rules: the comment at include/buf0buf.h lines 2173–2196

Summary

What's next

This post looked at where a row lives. The hidden columns DB_TRX_ID and DB_ROLL_PTR we passed in example 1 are where the next post starts. Which version InnoDB shows when two sessions read and write the same row at the same time (read views and MVCC), how it rebuilds an old version (undo), and when it makes someone wait (row locks and deadlock detection) are covered in Part 11: InnoDB Part 2 — Transactions, MVCC, Undo and Locks. do_write() and the LSN, which section 6 handed over "to Part 12", and the redo log and crash recovery that let the page cleaner postpone dirty pages, are covered in Part 12: Two Logs — the Redo Log, the Binlog and Crash Recovery.

• Part 2: The Big Picture — the Server Layer, Storage Engines, and the Life of One Query
• Part 8: The Optimizer — JOIN::optimize and Choosing a Plan — the constant-table read in example 4
• Part 9: Execution and the Handler API — How the Nested-Loop Join Calls the Engine — ha_innobase::write_row() and index_read(), which this post picked up