Ask HN: Books on designing disk-optimized data structures?

Are there canonical books, resources, or readings for how to design data structures that will be primarily read and written to a disk rather than memory? Most of what I learned in school about big-O assumes that, for example, random access is O(1). However, random disk reads are really slow due to spacial locality.

People who write databases obviously have solutions to this problem - for example, DuckDB is based on a number of papers that have come out over the years on this topic.

If I wanted to design, ie, a tree structure which was intended to be read/written from a disk, are there general principles or patterns the have been developed to take advantage of locality of reference, minimize random reads, or decrease the overhead of writes, that I could familiarize myself with?

What is the CLRS for disk?

You might like to visit the code of your favorite DB/Storage engine and see how it works? A couple of years during COVID lockdown I started exploring Golang, I produced two libs: GoCache and Fehrist to understand what algo is used by Memcache and Elasticsearch respectively. Blog posts about them are given below:

- http://blog.adnansiddiqi.me/gocache-lru-cache-implementation...

- http://blog.adnansiddiqi.me/fehrist-document-indexing-librar...

These days, most people need the opposite. They're probably using systems optimized for spinning disks but they're running it on flash, and all the layers of complexity added over the years to optimize disk latency are just slowing things down.

Like, this is the kind of bullshit people used to do research on: https://tlb.org/docs/usenixw95.pdf (I'm an author). This paper (and 100s of others) exist only because sequential reads & writes on disks were much faster than random access, because you had to (a) move the head, and (b) wait for the sector you're interested in to come around. At 7200 RPM, this is up to 4.2 milliseconds, so it was worth burning 10000s of CPU instructions to try to sort read requests in some order that might avoid waiting for another rotation. Many popular disk controllers couldn't read sequential sectors, so it was better to sort write requests so that it hit every second sector or something. Madness.

Anyway, today there are only 3 kinds of secondary storage worth caring about: flash (sector granularity, but no seeks), cloud (like S3), and archive (like Glacier).

But if you're working with some old-timey environment and really need to know about optimizing for spinning disks, most of the ideas were published in the late 80s and 90s. This book https://www.amazon.co.uk/Design-Implementation-Operating-Add... (McKusick et al) is excellent, and describes a filesystem that works well on a wide variety of workloads. Or see the references in the Blackwell paper above.

Anything that describes external sort algorithms perhaps?

Had not seen that, thank you!