Antes de começar a escrever suas buscas pelos dados , recomendo você a primeiro ter uma ideia do que é mais importante para seus usuários.
Quais valores e o tamanho de seus subconjunto vão conduzir a escolha do(s) índice(s) . O índice nada mais é que uma forma de acessar
mais rapidamente uma informação específica. Aqui é muito importante perceber que “informação específica” não é “todas as informações”.
E apesar de contribuirem para o acesso a determinados dados, eles vêm com um custo, tanto em armazenamento quanto em processamento. Por isso
a estratégia adotada na criação de um indice deve considerar, por exemplo, que o volume de armazenamento de um indice pode ser muito maior
que o volume de armazenamento do dado que está sendo indexado. Considere os índices em suas estratégias de backup/restore.
E quanto ao processamento? Toda ação de insert/delete/update no banco, …

Original post: http://anothermysqldba.blogspot.com/2014/01/use-your-index-even-with-varchar-char.html

Eu observei recentemente um post sobre o forums.mysql.com site: Como a jejuar em 3 milhões registro de pesquisa? 
O exemplo dado utilizado um LIKE '% eed' 

Isso não será aproveitado de um …