Bueno, para empezar, ¿para qué se quiere 4000 registros en la pantalla?, ¿para estar con las teclas arriba y abajo?, si va a buscar uno en particular pues pon un filtro y te traes los que busque únicamente.
Si no queda más remedio que tenerlos todos en la pantalla, entonces usa una tabla en memoria, tipo tkbmemtable, por ejemplo, su sistema de búsqueda con índices es hiperultrasupermegarapidísimo
