Chapter 7
To B-Tree or Not to B-Tree: External-Memory Algorithms

Throughout our journey so far, we’ve been operating under the assumption that our algorithms are dealing with data that is contained completely within the computer’s main memory (otherwise known as RAM) or caches. In other words, our computer has all the data loaded in memory and ready to go, and the computer then performs an algorithm on that data.

However, this isn’t always the case. Let’s say we want to calculate the sum of a list of integers that is so long that it takes up 50GB of space. If we’re working with a computer that has only 8GB of main memory, we immediately encounter a problem. How is our computer supposed to process such a list if the list can’t even fit inside the computer’s active memory? It’s not even possible to declare the statement:

While our computer probably wouldn’t explode if we attempted this, the computer would reject the statement, whining that it can’t hold so many numbers.

In this chapter, you’ll learn how to properly analyze the efficiency issues surrounding “big data” problems such as this one and write effective external-memory algorithms to process such data quickly and with minimal space consumption.

Another important problem we’ll deal with in this chapter is how to manage tree data structures when dealing with massive amounts of data. As you’ve seen throughout our discussions of trees, a tree such as a BST (be it a classic one, a red-black tree, or a treap) is important for being able to search for data quickly while also keeping the data sorted. But what if our data is so large that our tree can’t fit inside main memory? To deal with this not-uncommon conundrum, you’ll learn about the important and ubiquitous B-tree, which is a tree specialized for storing lots of information.

In this as well as the next chapter, we’ll embark on a “side quest” in which we explore the fascinating, vast, and important world of external-memory algorithms. This chapter is indeed connected to the previous ones, as here we’ll feature another self-balancing tree as we did in the previous two chapters. However, we won’t return to our main theme of randomization again until Chapter 9. If you so choose, you could skip ahead at this point to Chapter 9 and return to Chapters 7 and 8 at some later time.