With the exception of spatial indexes,InnoDBindexes areB-treedata 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_sizesetting when when the MySQL instance is initialized. SeeSection 15.8.1, “InnoDB Startup Configuration”.

When new records are inserted into anInnoDBclustered index,InnoDBtries 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.

InnoDBperforms a bulk load when creating or rebuilding B-tree indexes. This method of index creation is known as a sorted index build. Theinnodb_fill_factorvariable 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 15.6.2.3, “Sorted Index Builds”. Aninnodb_fill_factorsetting of 100 leaves 1/16 of the space in clustered index pages free for future index growth.

If the fill factor of anInnoDBindex page drops below theMERGE_THRESHOLD, which is 50% by default if not specified,InnoDBtries to contract the index tree to free the page. TheMERGE_THRESHOLDsetting applies to both B-tree and R-tree indexes. For more information, seeSection 15.8.11, “Configuring the Merge Threshold for Index Pages”.