Como pensé que los datos eran pocos te recomendé Pickle pero como veo que no son pocos ahora si te recomiendo una base de datos, preferente una robusta.
Python desde la version 2.5 trae
sqlite3. Eso si no lo he probado a ver si es eficiente con muchos datos. Lo que probado para pocos datos y funciona muy bien. Pruebalo y nos dices que tal esta. Si no te llega a "dar el kilo" entonces usa una base de datos mas robusta.