You might want to read perlguts, then. :) If speed comes first, be prepared to burn lots of memory. Speed does not rule out a DB-backed solution, however, as they all do caching and will be rather fast (though probably not as fast as all-memory hashes) once the caches are populated.

Consider using Devel::Size as you try different things to get an accurate (as long as you don't have coderefs in your hashes) reading of memory used by the different structures.