Actually, a much more efficient method for adding new records to the file would be an additional overflow file, which would take up to maybe 100 records and then get merged with the main file. This saves you having to move (on average) half of a 1,000,000 record file every time you want to insert something.

And I'd personally just convert the files to some standard database format and work with them through the Perl database handling modules. Why make life more difficult for yourself? mySQL handles 1,000,000-record tables with ease, especially if you use indexes.