MySQL - BD demasiado grande

Hola, tengo un site con una BD que creo que es demasiado grande. Es una página para buscar mp3, y la bd con las urls de todos los mp3 tiene 620.000. Antes estaba en un servidor compartido, pero debido al alto número de visitas he tenido que migar a un dedicado. Al principio iba bien, pero ahora estoy volviendo a subir el número de visitas y la bd empieza a ir lenta. Una consulta de Fulltext me tarda unos 2 min. Creo que no es normal, pero no se si es por mi servidor, mi tipo de consultas o porque la BD es muy grande.

Actualmente tengo 10.000 visitas al día y unas 80.000 páginas vistas. Mi servidor tiene 512 mb de ram y 1,8ghz. En las horas punta he observado que tira de memoria Swap y tal vez por eso sea por lo que va lento. Mi duda es,¿ cambio de servidor porque es normal que vaya lento debido al alto tráfico y que la BD es muy grande o intento configurar mysql ya que lo normal es que debería de ir bien para esa cantidad de visitas?

Muchas gracias :)