14.6.2.2 The Physical Structure of an InnoDB Index (original) (raw)

14.6.2.2 The Physical Structure of an InnoDB Index

With the exception of spatial indexes, InnoDB indexes are B-tree data structures. Spatial indexes useR-trees, which are specialized data structures for indexing multi-dimensional data. Index records are stored in the leaf pages of their B-tree or R-tree data structure. The default size of an index page is 16KB. The page size is determined by theinnodb_page_size setting when the MySQL instance is initialized. SeeSection 14.8.1, “InnoDB Startup Configuration”.

When new records are inserted into an InnoDB clustered index,InnoDB tries to leave 1/16 of the page free for future insertions and updates of the index records. If index records are inserted in a sequential order (ascending or descending), the resulting index pages are about 15/16 full. If records are inserted in a random order, the pages are from 1/2 to 15/16 full.

InnoDB performs a bulk load when creating or rebuilding B-tree indexes. This method of index creation is known as a sorted index build. Theinnodb_fill_factor variable defines the percentage of space on each B-tree page that is filled during a sorted index build, with the remaining space reserved for future index growth. Sorted index builds are not supported for spatial indexes. For more information, seeSection 14.6.2.3, “Sorted Index Builds”. Aninnodb_fill_factor setting of 100 leaves 1/16 of the space in clustered index pages free for future index growth.

If the fill factor of an InnoDB index page drops below the MERGE_THRESHOLD, which is 50% by default if not specified, InnoDB tries to contract the index tree to free the page. TheMERGE_THRESHOLD setting applies to both B-tree and R-tree indexes. For more information, seeSection 14.8.12, “Configuring the Merge Threshold for Index Pages”.