Hola VerderoL
Cuando un campo esta indexado es mucho rápido y eficiente la busqueda, es muy recomedable usar indices, pero no es bueno abusar de ellos.
Si vas hacer busquedas mas complejas es recomedable que uses los índices de texto completo "FULLTEXT" esto es aun mas eficiente.
aqui puedes encontra informacion
http://www.mysql-hispano.org/page.php?id=15&pag=1
saludos!