do all keys have the same importance? You may want to use a cache solution holding only the most frequently used keys. If another key is requested retrieve it from disk and add it to the cache.

(Again, if you can linearize your data in an array disk look up can be very fast because you can calculate the offset and set it with the help of seek, )

Realizing this with Tie::Hash would keep the interface to your data structure stable and spare you from any refactorings.