Deep Dive into MySQL InnoDB Record Lookup and Deletion Process

We start by stating the prerequisite for deleting a row: the record must be located first. In InnoDB this involves navigating a complex buffer‑pool structure, fetching the appropriate B+‑tree page, and then finding the exact record within that page.

The article continues the series "MySQL source code – delete statement implementation" and outlines four main steps, illustrated by a diagram.

First, a test table t_delete is created with six columns (id, c, d, e, name, country) and populated with sample data:

CREATE TABLE `t_delete` (
  `id` int(11) NOT NULL,
  `c` int(11) DEFAULT NULL,
  `d` int(11) DEFAULT NULL,
  `name` VARCHAR(100),
  `country` varchar(100),
  `e` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `c` (`c`)
) ENGINE=InnoDB CHARSET=utf8;

insert into `t_delete` values
(2,2,2,'','c',2),
(5,5,5,'c','cc',5),
(10,10,10,'cc','ccc',10),
(15,15,15,'ccc','cccc',15),
(20,20,20,'cccc','ccccc',20),
(25,25,25,'c','',25);

The execution flow is illustrated with a diagram of the record‑search process. When the statement delete from t_delete where id=2 reaches Sql_cmd_delete::delete_from_single_table , MySQL selects an iterator (typically IndexRangeScanIterator ) that eventually calls row_search_mvcc .

btr_cur_search_to_nth_level is the core routine that locates a record. It performs three steps:

Obtain the root page number and tablespace ID from the chosen index.

Repeatedly call buf_page_get_gen (which may invoke Buf_fetch_normal::lookup for memory or Buf_fetch::read_page for disk) until the desired page level is reached.

Within the page, use page_cur_search_with_match_bytes to find the matching row.

Inside a page, InnoDB stores a page directory that holds slot offsets. A binary search on this directory quickly narrows the candidate slot, after which a linear scan checks each record against the search tuple ( dtuple_t ).

The physical layout of an InnoDB data page is shown (file header, page header, infimum/supremum records, user records, free space, page directory, file trailer). The article explains how the slot address is computed: slot = ((page_dir_slot_t *)page + UNIV_PAGE_SIZE - PAGE_DIR - (n + 1) * PAGE_DIR_SLOT_SIZE) Once the slot is found, page_dir_slot_get_rec(slot) returns the record pointer, and the record is compared field‑by‑field using cmp_dtuple_rec_with_match_bytes . The compact row format is described, covering variable‑length field list, NULL‑value bitmap, row header, primary key, transaction ID, rollback pointer, and user fields. An interesting observation is that the first byte of a signed integer field is 0x80 . This results from InnoDB storing integers in big‑endian order and XOR‑ing the lowest byte with 0x80 to simplify sign handling, as shown in the function row_mysql_store_col_in_innobase_format . The article also details how the next_record offset is stored. Instead of an absolute address, InnoDB stores a 16‑bit relative offset calculated as (rec_address + next_record) & 0x3FFF , allowing the offset to be resolved by adding it to the page base address. Finally, using GDB commands the author demonstrates how to start from a known record address (e.g., the record for id=2 ) and iteratively follow next_record offsets to enumerate all rows in the table. The article concludes with a summary of key take‑aways about btr_cur_search_to_nth_level , InnoDB B+‑tree search, slot‑based binary search, linear record scanning, and practical GDB techniques for inspecting InnoDB internals.