Coincido con hades87 no te será difícil encontrar un hosting barato si usas PHP+Mysql. Te paso un ejemplo de una Guía de teléfonos Celulares
http://www.elbilly.co.cc/directorio_...cuba/busca.php (echa con PHP y Myql, tiene 465.873 registro de celulares de Cuba)