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.
in reply to Help performing "random" access on very very large file
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.
^M Free your mind!