Le chiavi esterne devono essere Index in MySQL?

Risposta breve:Sì, MySQL ti obbliga a indicizzare la chiave esterna.

Puoi leggere ulteriori informazioni sulle chiavi esterne nelle pagine della documentazione di MySQL:http://dev.mysql.com/doc/refman/5.5/en/innodb-foreign-key-constraints.html