MySQL genopbygger normalt hele tabellen, når du tilføjer et indeks, så alle de eksisterende bliver også genopbygget. Dette kan være langsomt.
Den eneste undtagelse er at tilføje et indeks ved hjælp af InnoDB-plugin, hvilket ikke gør.
Så vidt jeg ved, laver den altid en fuld tabelscanning, når den bygger et indeks, men den KUNNE lave en indeksscanning, hvis du tilføjede et indeks, som havde det samme (eller et undersæt) af kolonner som et andet indeks. Sådanne indekser er normalt kun nyttige, hvis kolonnerne er i en anden rækkefølge.
Ved at bruge stock mysql, jo flere indekser du har, jo langsommere vil det være at lave et nyt, da det også genopbygger eksisterende indekser.
Med plugin'et tror jeg, det ikke gør nogen forskel.
Uanset hvad, hvis du planlægger at tilføje flere indekser, bør du gøre dem alle på én gang, ikke ét ad gangen.