Binary Search Trees in External Memory

Before revealing this exciting new data structure, let’s first talk about binary search trees (BSTs) and how they might work with external memory. All of our discussions about BSTs until this point assumed that the entire tree would fit into RAM. But what would it look like if the BST was too large for RAM? This could happen if our BST was absolutely huge or if our computer had a tiny main memory, or both.

Say, for example, that we have a microcomputer that has a main memory that could only hold up to 4 nodes of a BST. Let’s also say that the block size was 4 nodes as well. How could our computer perform a search on the following BST, which contains 50 values?

Well, first, this BST would need to be stored in the filesystem since that’s the only place where we could even fit all this data. Let’s assume, then, that we have a file that stores all of these nodes. How might the computer perform a search on this BST?

Let’s apply our newfound knowledge about external-memory algorithms and walk through the steps the computer would perform if it were to search for the value 93 in the BST.

We begin our search at the root. Because the tree is currently in the filesystem, the computer needs to perform an I/O to transfer data to RAM. Because the computer’s block size is 4, we can transfer a block of up to 4 nodes.

Now, it’s hard to know exactly which nodes the computer might grab unless we can see exactly how the data is organized in the file. Let’s make the optimistic assumption that the computer will grab nodes that are in close proximity to each other. Accordingly, the computer might transfer this block of 4 nodes when it grabs the root as shown in the .

This is our first I/O.

With the first block now in memory, the computer begins its search. We’re searching for 93, which is greater than the root of 50, so we move to the root’s right child.

Luckily, the right child, which is the 75, is already in main memory. Now, 93 is greater than 75, so we need to move to the 75’s right child. However, we don’t have that child in memory yet, so we need to perform our second I/O to transfer the next block of nodes:

Again, we don’t know for sure if this is the exact block the computer will transfer; it’s just an example.

We now have the 75’s right child in memory, which is the 87. 93 is greater than 87, so we move to the 87’s right child, the 90. Our search value of 93 is greater than 90, so we need to move to the 90’s right child. However, it’s not in memory, so we need to perform our third I/O as shown in the .

With this third block in memory, we now have access to the 90’s right child, which is 95. Our search value of 93 is less than 95, so we move to the 95’s left child, 92.

Because 93 is greater than 92, we need to move to the 92’s right child. It’s not in memory, so we perform our fourth I/O:

Finally, we find the 93 we’ve been looking for. All in all, it took us 4 I/Os. Naturally, a much larger tree might require many more I/Os.

Optimizing External-Memory Trees

How might we optimize our tree to allow for faster search? Again, let’s review the key to optimizing external-memory algorithms: we should aim to pack as much useful information as we can inside each block. With that in mind, let’s ask ourselves whether the blocks from the previous BST example contained useful information.

Looking at the particular blocks the computer transferred, each block ended up containing two useful values. The first block, for example, contained the root and the 75. We needed both of those values since that’s the beginning of the path down to the 93. However, the block also contained information that we did not need, since the 25 and 12 were completely useless to us.

Similarly, the second block contained the 87 and 90 that we needed, but a 62 and 81 that we didn’t. The same is true for the third and fourth blocks, as at least half of each block contained useless data.

To optimize external-memory tree search, we need to try to pack blocks with more useful information. In a perfect world, all of a block’s data should be useful to us.

In the BST shown earlier, it would have been nice if the first block contained the 50, 75, 87, and 90. And if the second block contained the 95, 92, and 93, we could have found the 93 in two I/Os:

But again, there’s no way we can ensure that the computer will choose these blocks. We could, theoretically, structure the file’s data in such a way that the 50, 75, 87, and 90 are all adjacent to each other so they end up in the same block. However, this only optimizes for values descended from the 90, and would end up making other values even slower to find. Imagine that we were searching for the 12, for example. If the root’s block also contained 75, 87, and 90, we wouldn’t even have transferred the root’s left child of 25 into memory, which is what we need to find the 12.

Our goal is to create a different kind of tree that somehow reduces I/Os by packing each block with useful data. Well, it turns out that computer scientists have already figured that out.

Enter the B-tree.