That sounds like a typical application for a tied hash to me, the replacement of perl4's dbmopen and related functions.

As for backend, you might want to choose between the various backends as supported by AnyDBM_File; BerkeleyDB, in particular BerkeleyDB::Hash might be a good choice.

The advantage is that no rewriting of your code is necessary: it's just a hash. You will likely lose raw speed, though.

If you don't mind rewriting, you might want to look into DBD::SQLite as a backend for DBI, which gives you a SQL interface to your data.