Memory mapped - partially disk based algorithms

Question

Are there any good resources or books for spillable data structures, that is, say, a queue?

When storing large objects it could fill up all of memory, but if you can keep, say, the most used items of that queue structure in memory and the rest on disk (sort of like paging).

Similarly, this question applies to other structures such as linked lists, arrays, hashtables and so on.

Answer 1

There is the Buffer Tree (PDF, 0.6 MB):

"... developed an efficient external priority queue and batched dynamic versions of the (one-dimensional) range tree and the segment tree."

and

"... allow us to design efficient external-memory algorithms from known internal algorithms in a straightforward way, such that all the I/O specific parts of the algorithms are hidden in the data structures."

It is the mentioned as part of a broader treatment of the subject in the freely available online book "Algorithms and Data Structures for External Memory" by Jeffrey Scott Vitter (PDF, 1 MB).

Answer 2

What you are looking for might be the topic of I/O efficient algorithms. A Google search didn't turn up any books for me, but this course page contains a list of articles which may or may not be relevant for you.

You should also take a look at the WikiPedia page for B-trees, especially the section on B-trees in filesystems.