Utilizaçao de índices

Olá,

Fiz alguns testes executando o comando abaixo em uma tabela com 50.000 registros:
SELECT * FROM Clientes WHERE Nome LIKE "Maria%" ORDER BY Nome;

Depois criei um índice com o campo "nome" (o qual é consultado) e o tempo para execução do comando acima parece não ter dimunuido, então parece que o índice não ajudou em nada!
O que posso fazer para agilizar esse tipo de consulta?
Obrigado!

OBS.: Estou usando a versão 5.0 do MySQL

André



[As partes desta mensagem que não continham texto foram removidas]