MySQL - optimizar consulta

Hola:

Tengo una base de datos de 5 campos, donde un campo es apellido y nombre(30 char), y los otro son enteros o char pero de tamaño menor. En total la base de datos ocupa 21 Mb. Con aproximadamente 246.000 registros. La clave principal es apellido y nombre.

Al hacer consultas por nombres, en la cual debo recuperar todos los datos, demora 3 sg.¿Porque?

Ej. de consultas:

Select * from nombre_Base where apeyno Like 'unNombre%'

La consulta esta bien hecha.
Como puedo hacer para mejorar esto.

Estoy usando "MySQL Control Center" y desde ahi se puede optimizar la base, reparar, etc.., que ya lo hice.

Saludos y muchas gracias.

Para tu consulta, creaste indices ?, en mi opinion deberias haber crado una tabla con
id integer not null primary key autoincrement,
nombre varchar(30) not null,
apellido varchar(30) not null,
key id (id)
type MyISAM;

Gralmente los campos con datos repetidos como apellidos, sexo, etc...no se deberian indexar, pues ralentiza el sistema de respuesta.
Lo otro seria mejorar el script de tu my.ini o my.cnf de MySQL habilitando el cache de consultas...

Comenteme como te va.

espero te sira esta peqña orientacion

Gracias por responder.

Ya solucione el problema.
Debia preparar la consulta, y setear la cantidad de datos a mostrar.-
De esta forma se optimiza la consulta.
Muchas gracias.