Quisiera intentar con Ajax, pero necesito sugerencias!!

[memoo]

Qué tal amigos expertos en el web!

Bueno tengo una gran consulta que hacerles...
La cuestión es la siguiente:

Tengo mi aplicación web, hecha en php y con bd en MySQL. Todo bien, la cuestión está al momento de mostrar información de la base de datos.

Es decir, técnicamente todo funciona, y funciona bien, el problema es que los datos que cargo en los diferentes controles como por ejemplo select (listbox), son demasiados registros:

-Tengo 4 listas que muestran datos, y cada una de ellas tiene muchos datos para mostrar, por ejemplo solo la primera muestra 45,089 registros.

-La segunda muestra arriba de 300 registros.

y así sucesivamente, la cosa es que hay ocaciones en las que el tiempo de ejecución no basta y me truena la aplicación, esto se lo atribuyo a que son miles de registros lo que se van a mostrar.
No sé que opciones creen que pueda usar para minimizar el tiempo o si tengo que implementar Ajax.

He leído que es muy útil para este tipo de cuestiones (de hacer muchas y constantes peticiones al servidor), solamente que no se casi nada de Ajax, así que les agredecería que me echaran una mano para decirme por dónde empezar, o alguna otra solución, les agredezco de antemano.

Saludos.