Problemas con DB muy grande

[mamonga]

Hola amigos,

Tengo un problema que no se como solucionar, tengo una base de datos (que a mi parecer) es muy grande. unos 500.000 registros tiene una determinada tabla, y en un futuro no muy lejano puede llegar al millon.
Y claro cuando quiero hacer una busqueda de un nombre en particular usando algo parecido a :
.....AND Tags LIKE '%$tag%'....
Pues claro, tarda la vida o no llega a dar el resultado.

¿Alguna idea de cómo puedo reducir el tiempo de busqueda? he pensado en reducir el número de registros donde buscar pero eso reduce el fuerte de tener una gran base de datos.... no se que hacer :(

Un saludo y gracias !