Indices compuestos???

[Vice]

Eso dependerá de como montes tus consultas. Ten en cuenta que cada consulta utilizará sólo un índice de todos los que tengas definidos en tu tabla según el analizador de consultas del gestor.
¿La localidad tiene un código único o depende del país y la privincia?. Porque si no es único no te vale de mucho usar el índice sólo con el campo localidad porque al buscar por código te devolvería más de un resultado y siempre tendrías que condicionar al país y la provincia para buscarlas. Si esto es así, lo mejor es el índice compuesto.
Un saludo.