Hola greisy, cómo vas??
Pues antes que nada no uses en tus consultas el comodín "*"(asterisco), consume mas recursos del motor.
Luego, si ya usas índices, ejecuta explain
http://www.mysql-hispano.org/page.php?id=29&pag=8
Un link para optimizar consultas, no sé que tan "oficial" sea, pero me parece acertado:
http://aurea.es/2007/08/30/optimizar...ltas-en-mysql/
Y otro mas para lo mismo:
http://www.programacion.com/php/tutorial/mysql_indices/
Saludos, espero te sirva