External Binary Search

Ah, binary search—one of the classic algorithms of computer science lore. (I covered it way back in Volume 1, Chapter 2.) It’s a super-fast algorithm, clocking in at a blazing O(log N).

The typical binary search deals with data that is small enough to fit inside main memory. But what would binary search look like when applied to external memory? That is, say we had an ordered list stored in the filesystem, but the list is too large for RAM. How might we perform binary search?

Perhaps the most straightforward approach would be to perform binary search on blocks of data. Let’s visualize this.

Say that we have an ordered file that contains 20 values, and our computer’s block size is 4. This means that we have 5 distinct blocks, each containing 4 values:

In the previous diagram, I am not yet revealing the identity of these integers. I’ll reveal them when we load them into main memory.

Now, suppose we want to find the integer 11 within our data. With binary search, we always start by inspecting the value that’s at the center of our list. To do this, we’ll have to load the center block into main memory:

Once we have this block in main memory, we can now search the current block. We can do this, naturally, with binary search on the elements of the current block.

(A nice little trick, though, is to initially inspect the first and last values of the block. For example, if we’re looking for 11, and the first and last values of the block are 15 and 33, respectively, we know right off the bat that the 11 could only lie in a block that is earlier than the current block. However, this trick may only serve to reduce the number of main memory steps, and doesn’t reduce the number of I/Os we have to perform. So let’s move on.)

In any case, the 11 we’re seeking is less than any of the elements in the current block. As such, we know that the value must live inside a block earlier in the list, and we can eliminate all other blocks:

We repeat this process by choosing the center block of what remains. In this case, where we have an even number of remaining blocks, we can just arbitrarily choose either of them.

With this process, we end up performing log N/B I/Os. That is, we start with N/B blocks, and with each I/O we perform, we reduce the number of remaining blocks by half. So, since in-memory binary search takes log N steps, external-memory binary search takes log N/B I/Os. In Big O notation, we’d call this O(log N/B).

In the end, external binary search isn’t much different than good ol’ regular binary search. It’s practically the same algorithm, and has the same logarithmic kind of performance. However, we’re going to look at how we can optimize this external memory algorithm and make it much faster. I’m going to start with a theoretical approach and then move on to practical techniques we can take to the bank.