🚀 go-pugleaf

I have been asked at work to write a filter program. Unlike most filter
programs this one must load and sort as much data as possible into memory,
and write it out back to disk as another (completely different) file format.

My problem is: 
   
   What algorithms (& data strucures) make good use of the hard disk 
as extra 'memory' when RAM is full.

   I would like one that involves some sort of cache system to minimise
disk access. I would also want one that could be easly fitted into any
data structure that you are using in memory. ie linked lists, trees.
The algorithm must make the accessing of elements of the data structure
in either RAM or disk look indentical (at the function call level).

 
   I have chosen to use dynamically allocated arrays (lots of calls to
realloc()) and to use the array indicies as a general form of 'pointer'
that could be easily used as an index to the records that get 
stored in the file when memory is full.

   This problem MUST hit everyone sometime or another on the IBM. Its
a real shame Uni's don't teach ways of implementing data structures on
low memory systems.. In the _real_ world not everyone has 
virtual memory. B-(. {.. UNIX, I miss you !!!... } 

   Also, I have not seen any books for the IBM that deal with this situation,
could someone please point me to a good book (if any).

Thanks.
--
.---------------.------------------------------.-------------------------.
| Richard Frost | USENET: rfrost@spam.ua.oz.au | FIDONET:  3:680/805     |
.-------.-------^------------------------------^-------------------------|
| O F F | A NEW life awaits you in the OFF WORLD colony, the chance to   |
| WORLD | begin again in a golden land of opportunity and adventure !    |
`-------' New climates, recreational facilities ...                      |
| The custom tailored genetically engineered humanoid replicant designed |
| especially for YOUR needs !!                          .... BLADERUNNER |
`------------------------------------------------------------------------'