Qual o melhor meio de efetuar uma busca por palavra chave

Salve salve galera do iMasters...

Gostaria de abrir uma discusão sobre o assunto de buscas...

A situação seria a seguinte:

Supondo que tenho uma base de dados com 500.000 registros.

(Digamos que cadastrei tudo o que existe na lista telefônica de SP, Informações de endereço, telefone, etc.)

Em meu sistema de busca quero encontrar por exemplo "Auto-Elétricas".

Usualmente criamos um campo de texto onde colocamos "Palavras-chave" e neste campo colocaríamos palavras que posuem alguma ligação com auto-elétrica.

Ex.: "Alto-elátrica, eletricista, farol, lanternas, carro, concerto"

Mas creio que isso torna-se um pouco lento para uma tabela como essa com 500.000 registros.

O que poderia ser feito para que este processo fique mais rápido?

Estive penssando em criar uma outra tabela na base de dados com a seguinte estrutura:

id - int | palavras - varchar(500)

Acredito que a busca seria mais rápida pois esta tabela contém um número muito menor de registros, já a tabela dos cadastros ficaria mais rápida pois poderia utilizar um campo menor para referenciar o código das categorias na qual aquele registro se encaixa.

Caso essa seja a melhor solução existe a possibilidade de executar em uma única query a busca na tabela de palavras-chave e localizar registros que encaixam na determinada categoria.

pois atualmente faria da seguinte maneira:

efetuo a busca pela palavra-chave o que me retornaria a id da categoria

com posse da id efetuo outra busca nos cadastros que possuem essa id no campo de categorias.