MySQL - Problemas usando Like

Hola:

Quisiera que me ayuden, tengo problemas al hacer consultas por nombres, en la cual debo recuperar todos los datos, demora 3 sg.¿Porque?

La base de datos tiene 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, NroDoc
La Clave secundaria es Apellido y Nombre.

Ej. de consultas:

Select * from nombre_Base where apeyno Like 'unApellido%'

Si hago:
Select * from nombre_Base where apeyno Like 'a%'
Demora aprox. 10 seg.

La compudora en la que estoy rrealizando la consulta es una Pentium II con 192 MB de Ram.

Saludos y muchas gracias.

Tabla, antes que todo es una tabla que está contenida en una Base de Datos, por tanto la TABLA tiene 5 campos.

Ahora, si tienes 246000 registros introducidos en tu TABLA con justa razón va a durar, estos son los puntos:

- Tienes un ínidce mal definido, un campo nombre no puede estar dentro de un PK, a menos que sea necesario, solo el número de identificación debería ser la llave.
- Los campos varchar podrían ser índices por separado, apeyno debe ser un índice secundario y los campos apellido y nombre un ídice compuesto.
- Tienes 246000 registros los cuales por medio de un Like tarda más que si fueras a buscar un solo registro, pues la comparación es más exaustiva.
- Otro factor es el armado de la información ya que tienes una PC bastante pobre