Agilizar busquedas en mysql y php

[crash_master25]

Hola a todos!!

Miren, yo estoy trabajando con php y base de datos mysql, utilizo las funciones de adodb para manejo de la db. El problema que tengo es que ya a los 2 mil registros se empieza a alentar un poco, 5 o 6 segundos en respuesta, como utilizo ajax pues entonces si destantea un poco, entonces necesito ver la forma de agilizar la busqueda, o hacer que la respuesta de servidor sea mas rápida... Pense en usar StoreProcedures, pero mi servidor en el que estoy hospedado maneja phpmyadmin, y este no maneja sp, descarge una aplicacion phpmyide pero necesita el mysqli instalado y como es un hospedaje comercial no puedo instalarlo. por lo tanto estoy donde empeze.

¿A caso existira algun metodo de realizar las busquedas?

Las bd al final pueden tener un promedio de 100 mil registros...

Saludos y gracias por su tiempo
Crash_master25