[Resolvido] Otimizar consulta Mysql

Tenho uma tabela cujo tamanho é de 220kb e 3.500 registros entre 3 colunas.

Vou dar um exemplo:

Nome, Estado, Cidade

Ao fazer uma query ela onde quero apenas os registros de um nome X (cidade). where Cidade = 'x'.

Ela demora muito mesmo para carregar.

Tem algum jeito para eu conseguir otimizar a tabela?

Sou inexperiente em banco de dados Mysql, mas algumas coisas consigo fazer por isso postei aqui sobre otimizar consultas.