Listas enlazadas provincia-localidades España

[OssoH]

Hola :
Estoy montando dos combobox en php. Una donde seleccionaré la provincia y automáticamente se me rellenará el combobox de localidades.
Me gustaría que me aconsejaran de la forma más óptima posible ya qué es muy importante que lo haga lo más rápido posible porque el número de visitas va a ser elevado.

He visto que tengo varias opciones :
1.- Recargar el combobox con jquery haciendo una llamada a la BD. Tendría en la BD todas las provincias y localidades de España.
Mi opinión : demasiado llamadas a la BD la cuál ralentizaría conforme el número de visitantes aumenta.

2.- Poner en un XML las provincias y localidades. Tal y cómo lo hacen en esta web:
http://www.hellogoogle.com/selector_combo_ajax_provincias_localidades/
Mi opinión : Creo que es la más óptima porque los XML se leen rápidos.

3.- Poner en un javascript las provincias y localidades.
Mi opinión : Al tener que descargarse este js en local para ejecutarse creo que podría ralentizar el proceso. Este .js podría llegar a pesar más de 1 Mb.

¿Que opináis?
Gracias