Que hosting necesitaria para una base de datos de 1gb

[llnitoll]

Pues seria un sitio que de entrada ya tendría una tabla con 2,5 millones de entradas, que ocupa casi una giga. (Para MySQL)
La visitas serian pocas al principio, pero seria necesario que moviese la tabla y obtuviese resultados con soltura.

Imagino que un hosting compartido de menos de 10$ ni hablar. Podría usar un buen VPS, o debería irme a un dedicado directamente? La intención es pagar lo mínimo al principio pero que funcione decentemente.