Indice no mysql em uma tabela ja criada e com registros

Tenho uma tabela com mias de 65.000 pacientes cadastros. A pesquisa por nome esta demorando muito. Como faco para criar um indice para acelerar a pesquisa por nome ?

TABELA
pacientes
CAMPO
Nome

Executo a consulta pelo php assim:
sql = "select Nome,Dt_nasc from paciente where Nome like '$nome'";
Os usuarios entram o nome assim: JOAO CAR%


Gostaria de saber como faco para criar um indice no campo nome e usa-lo na consulta acima.


Obs: Preciso fazer isto no modo texto dentro do servidor mysql.

Desde ja agradeço.!

Bom, lá vai a má notícia...
Quando você usa funções do tipo LIKE, SUBSTR, etc, você praticamente inutiliza o índice...
Quanto a criação do índice :
CREATE [UNIQUE|FULLTEXT|SPATIAL] INDEX index_name
[USING index_type]
ON tbl_name (index_col_name,...)

Veja sempre a documentação oficial :
http://dev.mysql.com/doc/refman/5.1/en/index.html