In this lesson, you will learn how MySQL’s InnoDB engine physically organizes data on disk using B+ tree pages to ensure efficient retrieval and updates.
The Anatomy of a Page
In InnoDB, data is not read or written row-by-row; instead, the engine operates on a fixed-size unit called a page, typically 16KB. Whether you are searching for a single record or updating a hundred, the storage engine must load the entire page containing that data into memory (the Buffer Pool).
Think of a page as a structured container. Each page is divided into three primary segments:
- File Header/Trailer: Contains metadata like the page ID, checksums, and the pointers to the previous and next pages in the linked list.
- Page Directory: A specialized index within the page that stores "slots." These slots point to specific records, allowing the engine to perform binary searches within the page to find your data quickly.
- User Records: This is where your actual table rows reside.
Leaf vs. Internal Nodes
The B+ tree structure relies on two distinct types of pages:
- Internal (Branch) Pages: These do not contain your actual data rows. Instead, they store a collection of key values and child page pointers. Their only job is to guide the engine down the tree to the correct location.
- Leaf Pages: These are the bottom-most nodes of the B+ tree. They contain the actual rows of your table. In InnoDB, these pages are linked together in a doubly-linked list. This structure is brilliant for performance because it allows the engine to perform a lightning-fast range scan—once it finds the starting point in the leaf level, it simply follows the "next page" pointers to traverse the data sequentially.
Manipulation: Splits and Merges
Because pages have a fixed size, they eventually get full. When you insert a row into a page that is already at capacity, InnoDB triggers a page split. The engine creates a new page, moves approximately half of the records to the new page, and updates the parent node pointers. Conversely, if you delete enough data to make a page mostly empty, InnoDB may perform a page merge to reclaim space and keep the tree balanced.
Key Takeaway: InnoDB manages data in 16KB pages that use a structured directory for internal binary searching and linked-list pointers to enable efficient sequential range scans.