Cómo indexar la base de datos

[mblascog]

Buenas,
Me encuentro que las consultas que hago a la base de datos son muy lentas.
No sé como afrontar el problema y me gustaría saber vuestra opinión.
En primer lugar decir que se trata de una pequeña base de datos para mostrar unos resultados en una web.
Está compuesta por unas 14 tablas. 13 de ellas son muy pequeñas, contienen 3 o 4 campos con un máximo de 600 registros. Y la otra, tiene 30 campos y unos 800 registros.
Creo que por el tamaño de la base de datos el acceso debería de ser más rápido.

Me preguntaba si añadiendo índices a la base de datos podría obtener más velocidad.
Cuál es la vuestra opinión? Gracias