MySQL bygger vanligtvis om hela tabellen när du lägger till ett index, så alla befintliga byggs om också. Det här kan vara långsamt.
Det enda undantaget är att lägga till ett index med InnoDB-plugin, vilket inte gör det.
Så vitt jag vet gör den alltid en fullständig tabellsökning när man bygger ett index, men den KAN göra en indexskanning om du lägger till ett index som hade samma (eller en delmängd) kolumner som ett annat index. Sådana index är normalt bara användbara om kolumnerna är i en annan ordning.
Med stock mysql, ju fler index du har, desto långsammare blir det att göra ett nytt, eftersom det också bygger om befintliga index.
Med pluginet tror jag att det inte spelar någon roll.
Hur som helst, om du planerar att lägga till flera index bör du göra dem alla på en gång, inte ett i taget.