Search code examples
data-structuresinnodb

How does the leaf node split in the physical space in innodb?


If the keys are inserted in ascending order, according to normal B+-tree characteristics, when the leaf page is full, it will split and there will be a new page introduced to the B+-tree.

For an instance, if there is a leaf page with up to 3 keys.

(page0)|1|2|3|

Then the key 4 is inserted:

              |1|3|*|(page0)
(page1)|1|2|*|       |3|4|*|(page2)

After this, later keys will be inserted into page2 until the next split since they are in ascending order. All previous pages will remain half full.

In my example, I guess this will cause space to be wasted. However, in the database, it seems to be unreasonable. This really confuses me. I've read Jeremy Cole-B+Tree index structures in InnoDB, but I have probably misunderstood something.


Solution

  • Without additional optimizations, you're absolutely correct that as an index page filled it would be split in half and then remain half-filled forever. However, InnoDB optimizes index fill based on its perception of the insertion order. That is, if it detects that insertion is being done in-order (ascending or descending) it will, instead of splitting a page in half, just create a new empty page for an insertion at the "edge" of the page.

    There is some information about this in the MySQL manual section The Physical Structure of an InnoDB Index. Additionally I illustrate an example of this behavior in my post Visualizing the impact of ordered vs. random index insertion in InnoDB.

    In The physical structure of InnoDB index pages I describe the Last Insert Position, Page Direction, and Number of Inserts in Page Direction fields of each index page. This is how the tracking for ascending vs. descending order is done (as left vs. right, though). With each insert, the last inserted record is compared to the currently inserted one, and if the insert is in the same "direction", the counter is incremented. This counter is then checked to determine the page split behavior; whether to split in half or create a new, empty page.

    In practice, this optimization is not perfect, and there's a big difference between insertions being mostly in-order, and exactly in-order. If inserts are only mostly in-order it can mean that the page direction may never get appropriately set, and pages will end up half-filled (as you described).