Справочное руководство по MySQL версии 4.1.1-alpha
Физическая структура индекса
Все индексы в InnoDB представляют собой B-деревья, в которых записи индексов хранятся в страницах ответвления дерева. По умолчанию размер индексной страницы составляет 16 Кб. При вставке новых записей InnoDB старается оставить 1 / 16 страницы свободной - для будущих вставок и обновлений индексных записей.
Если записи индекса вставлены в последовательном порядке (в порядке возрастания или убывания), то получившиеся индексные страницы будут заполнены примерно на 15/16. Для записей, которые вставляются в случайном порядке, эти значения составят от 1/2 до 15/16. Если коэффициент заполнения индексной страницы уменьшится и станет ниже 1/2, InnoDB попытается объединить записи индексного дерева, чтобы освободить страницу.
