No hay necesidad de 'reconstruir' un índice. Siempre se mantienen actualizados. Tal vez se refería a reconstruir la mesa. Dependiendo de sus patrones de uso y esquema, puede obtener páginas fragmentadas en InnoDB, y creo que también en MyISAM. Reconstruir la tabla puede mejorar el rendimiento al deshacerse de la fragmentación de sus datos en el disco. No uso las tablas MyISAM regularmente, pero creo que se recomienda ejecutar 'OPTIMIZE TABLE' con ciertos patrones de uso. Consulte los documentos de MySQL en OPTIMIZE TABLE para obtener buena información sobre MyISAM e InnoDB.
No estoy tan familiarizado con las complejidades de MyISAM, pero con InnoDB es cierto que las estadísticas pueden quedar desactualizadas. La base de datos mantiene estadísticas estimadas sobre cómo se distribuyen sus datos para un índice determinado, y es posible que se desactualicen, pero MySQL/InnoDB tiene algunas funciones integradas para tratar de mantener las estadísticas actualizadas. Por lo general, no tienes que preocuparte por eso.
Entonces, si está utilizando InnoDB, la respuesta es no, normalmente no necesita hacer nada activamente para mantener el buen rendimiento de sus índices. No estoy tan seguro con MyISAM, creo que es más común necesitar optimizar esas tablas regularmente.