non è un dovere, gli indici sono accessori, ma ottimizzano le prestazioni: puoi metterlo, con la ragionevole sicurezza di migliorare le performance di lettura, su
- ogni campo chiave di una join (on...) in entrambe le tabelle
- ogni campo in clausole where
- ogni campo in clausole having
per avere il massimo beneficio, consigliano di avere i campi su cui fai le join, dichiarati dello stesso tipo.
per ottimizzare le prestazioni ha senso usare il campo del tipo più piccolo possibile capace di contenere tutte le informazioni della tua tabella, molto provabilmente BIGINT non è ottimale.
log-slow-queries, EXPLAIN SELECT e Analyze tbl sono molto utili, ti consiglio di provarli.

http://dev.mysql.com/doc/refman/5.0/en/query-speed.html