could work with an ordered dictionary

Perhaps you should take a look at cdb and CDB_File. If size is an issue, think about compressing each record separately before stuffing it into cdb.

Also, think about using SQLite (i.e. DBI and DBD::SQLite).

Alexander