Where the information exceeds what can be stored in memory, the most usual solution is some kind of DBMS. Relational databases are only semi-infeasible for this kind of data structure in the sense you could store say 100000 lines in a BLOB and index those - an approach talked about but I have never seen tried.

The most common custom DBMS structure is indeed flat-file-based as has been mentioned.

But the most useful Perl implementations of non-relational database architecture are probably going to be the DBM family of modules. In particular, DBM::Deep (which has an underlying flat-file storage) looks perfect for your requirement.