Pesquisa Otimizada em Banco de Dados

Olá pessoal.

Estou com uma dúvida em relação a melhor forma de se fazer uma consulta para um sistema de busca em MySQL.

Queria fazer algo que funcionasse como o Like buscando palavras entre os termos (%palavra%), mas que não seja ele pois ele é muito lento para consultas muito volumosas

Andei pesquisando e vi esta técnica de utilizar uma tabela de termos e buscando com id's e indices.

http://www.devmedia.com.br/post-11807-Full-text-search-otimizada-em-SQL-usando-GROUP-BY.html

Estou desenvolvendo um sistema de assessoria política em que a idéia é encontrar facilmente os eleitores na base de dados.

Preciso buscar resultados com campos de: Nome do Eleitor, Cidade, Bairro, Descrição do Usuário, E-mail entre outros.

Isso para mim até é válido em um campo descritivo (TEXT), porque posso simular tags no texto para encontrar usuários que tenham a mesma descrição que estou buscando (ex.: moreno, alto, futebol) porém tem todos estes outros campos que gostaria de fazer esse tipo de consulta mas acredito não ser a melhor opção criar diversas tabelas de termos até porque a tendência é que o banco ficasse enorme com muito mais facilidade.

Alguém conhece alguma forma de fazer uma busca otimizada sem dar voltas com outras tabelas?

Vi algo sobre utilizar o MATCH mas não sei se é realmente vantajoso.

Minha tabela é Innodb, não me interessa utilizar MyiSAM para utilizar o FULL TEXT SEARCH

Justamente pelo lock no Innodb que é por registro e do MyiSAM que é por tabela.

Quem poder dar uma luz agradeço