Datastructures for external memorySomething I recently became interested in is map data structures for external memory — i.e. ways of storing indexed data that are optimized for storage on disk. In a typical analysis of algorithm time complexity, you assume it takes constant time to access memory or perform a basic CPU operation such as addition. This is of course not wholly accurate: in particular, cache effects mean that memory
