MySQL обикновено възстановява цялата таблица, когато добавите индекс, така че всички съществуващи също се преизграждат. Това може да е бавно.
Единственото изключение е добавянето на индекс с помощта на плъгина InnoDB, който не го прави.
Доколкото знам, винаги прави пълно сканиране на таблица, когато създава индекс, но МОЖЕ да направи сканиране на индекс, ако добавяте индекс, който има същото (или подмножество) от колони като друг индекс. Такива индекси обикновено са полезни само ако колоните са в различен ред.
Използвайки stock mysql, колкото повече индекси имате, толкова по-бавно ще бъде създаването на нов, тъй като той възстановява и съществуващите индекси.
С плъгина мисля, че няма разлика.
Така или иначе, ако планирате да добавите няколко индекса, трябва да ги направите всички наведнъж, а не един по един.