A RDBMS is your best option, but barring that, let me pimp CGI::Search for a moment. Although it's in the CGI namespace, it doesn't have to be used in a CGI (it just does things in ways that are a bit more convieant for CGI programmers, but won't get in the way of more general-purpose programmers). The latest version supports compressed flat-files, which my basic benchmarking shows to give a 12-fold increase in speed.

Still, you are better off with an RDBMS. In fact, one of the goals for CGI::Search was to make upgrading to an RDBMS easier (once you're programs are running it, you only need to change the module internals to search on an RDBMS).

----
I wanted to explore how Perl's closures can be manipulated, and ended up creating an object system by accident.
-- Schemer

Note: All code is untested, unless otherwise stated