While we have only seen a sampling of in-memory data structures, we have covered the mindset, tools, and way of thinking about data that is common to all in-memory data structures. Therefore, in the last few days I will talk about data structures for storing data on disk instead of in memory. The ideas are similar but there are a few differences. This is Chapter 14 in the textbook, and I went through that discussion on differences between in-memory and external-memory/disk storage.
It isn't in the book, but I briefly described the FAT Filesystem. This article goes into more detail than I did in class. Essentially, the disk is divided into clusters and then each file becomes a linked list of clusters. The next pointers of the linked list are stored in the file allocation table separate from the main storage area to improve efficiency.
No exercises