Není potřeba „přestavovat“ index. Jsou vždy aktuální. Možná měl na mysli přestavbu stolu. V závislosti na vašich vzorech použití a schématu můžete získat fragmentované stránky v InnoDB a myslím, že také v MyISAM. Přebudování tabulky může zlepšit výkon odstraněním fragmentace dat na disku. Tabulky MyISAM nepoužívám pravidelně, ale věřím, že se doporučuje spouštět 'OPTIMIZE TABLE' s určitými způsoby použití. Podívejte se na dokumenty MySQL na OPTIMIZE TABLE pro dobré informace o MyISAM i InnoDB.
Nejsem tak obeznámen se složitostmi MyISAM, ale s InnoDB je pravda, že statistiky mohou být zastaralé. Databáze uchovává odhadované statistiky o tom, jak jsou vaše data distribuována pro daný index, a je možné, že tyto údaje budou zastaralé, ale MySQL/InnoDB má některé vestavěné funkce, které se snaží udržet statistiky aktuální. Obvykle si s tím nemusíte dělat starosti.
Pokud tedy používáte InnoDB, odpověď je ne, obvykle nemusíte aktivně nic dělat, aby vaše indexy fungovaly dobře. S MyISAM si nejsem tak jistý, myslím, že je běžnější potřeba tyto tabulky pravidelně optimalizovat.