[plt-scheme] (Bit Off) External Memory Paging etc.

From: Erich Rast (erich at snafu.de)
Date: Thu Apr 16 11:17:43 EDT 2009


I want to implement an external randomized skip list in pure Scheme and
think I grasp the concept well enough to give it a try (just for fun).
However, I can't find any useful information on how to deal with
insertion and deletion on disks and how to prevent excessive skipping
back and forth in a file. The books and texts on algorithms I've seen
tend to describe structures as if they were in internal memory and leave
it quite open how to manage pages, do smart caching, re-use space marked
as unused, etc.

Does anyone know good tutorials or a good book on *external* data
structures and algorithms? To give you some background information, I
haven't studied CS and while I'm able read and understand some discrete
mathematics, I personally prefer prose + pictures + pseudo code. 

Best regards,


Posted on the users mailing list.