sefiroxx,
para eso, para el filtrado de textos, también sirven los índices, es decir, es una de sus funciones principales. Son los campos que aparecen tras el WHERE en búsquedas frecuentes los mejores candidatos para ese tipo de índices. Sin embargo, existen algunos tipos de índices, dependiendo en algún caso del tipo de motor que uses (por ej. el FULL-TEXT en las tablas MyISAM). También la sintaxis de consulta es distinta si buscas un término tal cual en un campo o parte del contenido del campo, puedes hacer un índice compuesto, o aplicarlo solo a un determinado número de caracteres, etc. Luego está la sintaxis a la hora de crearlo, sea al crear la tabla o después de tenerla creada.
Echa primero un vistazo aquí sobre todo lo que tiene que ver con los índices y recorre sus enlaces.
http://dev.mysql.com/doc/refman/5.0/...ate-index.html
Tú, por lo que veo y si se trata de un autocompletado, para la consulta usarás un índice normal BE-TREE y en la consulta usas
SELECT campo FROM tutabla WHERE campo LIKE 'cadena%'
Eso aplicado sobre la columna llamada campo irá lo suficientemente rápido.