Eficiencia indices?¿? Como sacar lo mejor?

[CHiCoLiTa]

Buenas

estoy con SQL Server 2005 y me planteo una duda sobre los indices

Supongamos la base de datos de un callejero, en la que el usuario pueda buscar por lo que quiera
Tenemos, Via, Numero, Poblacion, Provincia, CP y asi hasta 13 campos diferentes por el que se puede hacer busquedas

Bien, ahora yo puedo buscar por cualquiera de estos terminos, de manera simple o compuesta, es decir, por CP y Via o por Provincia y Poblacion, o Via, Numero, Pblacion, CP o la combinacion que se me ocurra

Entonces pienso, si creo un indice sencillo por cada campo, el gestor de base de datos va a tardar en procesar cual es el indice que debe usar. Tambien me planteo la eficacia real de hacer eso (olvidandonos de inserciones y demas, solo buscamos eficacia de busqueda). Es realmente eficar hacerlo asi?

Tambien pienso que hacer un indice compuesto, con el primer campo Provincia, puesto que de una manera u otra voy a buscar por ese dato

Generando este ultimo indice compuesto, segun como sea la busqueda y que campos se quieran incluir me tarda apenas 1 segundo o se me alarga a mas de 1 minuto

Cual es la mejor manera de generar indices sobre un abanico de 13 campos que no se realmente cuales son los que va a entrar en la busqueda?
Cual es la forma optima de tratar esto?
O quizas mi planteamiento esta totalmente equivocado
Por que la primera busqueda tarda en realizarse y la segunda es mas rapida? Porque ya ha decidido el gestor que indice usar? porque lo tiene activo?

Se abre el debate

Ahh se me olvidaba. Dentro de la tabla hay tablas relacionadas como por ejemplo el ID_Provincia. Debo crear claves foraneas? Debo indexar a parte esas tablas? o con le multiple basta?