Todos los índices en InnoDB son árboles binarios (B-trees) donde las entradas de índice se almacenan en páginas que son las hojas del árbol. El tamaño predeterminado de una página de índice es 16KB. Cuando se insertan nuevas entradas, InnoDB intenta reservar 1/16 de la página para futuras inserciones y actualizaciones en el índice.

Si las entradas del índice se insertan en un orden secuencial (sea ascendente o descendente), las páginas de índice se llenarán en aproximadamente 15/16 de su capacidad. Si las entradas se insertan en un orden aleatorio, las páginas se llenarán entre 1/2 y 15/16 de su capacidad. Si la proporción de espacio ocupado de una página de índice cae por debajo de 1/2, InnoDB intentará reducir el árbol de índice para liberar la página.