MySQL ne "reconstruit" pas l'index à chaque insertion.
La taille de page par défaut de MySQL est de 16 Ko. Il alloue ces pages par incréments de 1 Mo (appelés extensions).
Lorsqu'une table est créée pour la première fois (les index sont reconstruits), les pages sont remplies au 15/16e, laissant de la place pour quelques insertions aléatoires (1k de place). Si vos entrées d'index font 500 octets chacune (taille de la clé primaire + données de ligne pour un index clusterisé), cela laisse de la place pour insérer 2 nouvelles lignes avant de devoir diviser la page.
MySQL conserve la valeur de l'enregistrement le plus élevé et le plus bas dans l'en-tête de la page, de sorte que les enregistrements d'une certaine plage vont sur la même page.
Lorsque MySQL doit insérer une ligne sur une page entière, la page doit être divisée. MySQL ajoutera une nouvelle page et déplacera la moitié des données de la page vers la nouvelle page.
Dans une page, les enregistrements peuvent ne pas être dans l'ordre physique. Ils seront dans l'ordre où ils ont été insérés. Ils sont liés dans l'ordre via une forme de liste liée. Ainsi, même une insertion aléatoire, en dehors de la nécessité de diviser la page, n'entraîne pas le déplacement physique des données.
Après de nombreuses insertions aléatoires, vos pages seront de 1/2 pleines à pleines. Un index avec de nombreuses pages à moitié pleines affectera négativement les performances de lecture (vous devez lire deux pages à moitié pleines pour lire le même nombre d'enregistrements qu'une 15/16e pleine page).
Maintenant, si vous insérez des lignes dans l'ordre de l'index, MySQL continue simplement d'ajouter à la fin des pages, de les remplir 15/16 et d'ajouter une extension à la fois des pages. Beaucoup moins de perte de performances car il n'y a pas de fractionnement de pages, donc aucun déplacement de données n'est impliqué, sans parler de l'avantage des performances de lecture de pages presque pleines.
Les insertions aléatoires augmentent également la fragmentation des pages, ce qui peut affecter les performances de lecture si vous lisez souvent un grand nombre d'enregistrements séquentiels (rare).
Aussi, modifier la mise en mémoire tampon peut vous affecter.
