Wrapping Up

This chapter opened up a whole new world. When dealing with data too large for main memory, we have to think about our algorithms in a completely different way. Specifically, instead of measuring speed by counting steps, we need to count I/Os.

Similarly, when we want to optimize external-memory algorithms, we need to focus on reducing I/Os. One way to do this is to pack blocks with as much useful information as we can. We also discovered that B-trees do this and are a wonderful data structure for storing data in the filesystem. As such, they’re popular in databases as well as many other applications.

The topic of external-memory algorithms is a broad subject unto itself, and can easily fill its own book. I won’t be doing that here, but I will devote one more chapter to the topic.

So, next up, we’ll be discussing external-memory sorting algorithms. Onward we go!