Have you considered trying to use data structures which are backed by files, like BerkeleyDB or in a relational database like MySQL? Of course they will have to go to disk for data sometimes, but they should be able to make intelligent caching choices so that most of the time you can access data without going to disk...

Yes, it is slower than having it all in RAM if you have the memory for that, but it is likely to make better file access choices than will be made by your OS paging randomly accessed RAM back and forth into virtual memory...