B-Trees
A B-tree is a tree data structure designed especially for external memory, and aims to keep I/Os to a minimum. In a bit, I’ll get into all of the B-tree rules and operations, but let’s begin with an overview of how it works.
The first thing to know about B-trees is that they are not binary trees. A binary tree is, by definition, a tree whose nodes have up to two children at most. Indeed, the trees we’ve dealt with so far in this book were types of binary trees.
A B-tree, on the other hand, contains nodes that can have many children. In fact, in the real world, B-tree nodes often have hundreds of children. Yes, you read that right. As we’ll see shortly, the power of B-trees stems from this idea.
What is clear is that the “B” in the name “B-tree” does not stand for “binary.” As to what it does stand for, well, there’s no definitive answer to that. For whatever reason, the inventors of the B-tree never explained what the “B” represents. While various suggestions abound (including “bushy”!), the most we have to go on is the cryptic statement by one of the B-tree’s inventors, who said, “the more you think about what the B in B-trees means, the better you understand B-trees.” This is truly computer science at its best.
In addition to a B-tree node being able to have numerous children, each node can also hold numerous values. Here’s an example of a small B-tree:
Here we can see that the root node has 3 values and 4 children. The pointers to the children live in between the actual values, and help us find which child we may be looking for. To find values less than 5, for instance, we need to follow the pointer to the left of the 5. To find values between 5 and 20, we need to follow the pointer that lives between the 5 and the 20. And so on.
When creating a B-tree, a decision needs to be made at the outset as to the maximum number of values each node can store. This decision will be applied to all nodes. In this example, each node stores a maximum of 3 values. In real life, it’s not uncommon to have a B-tree whose nodes store a maximum of 500 values each. In this book, I’ll refer to this number as a B-tree’s node maximum capacity. (This is not official jargon. Official jargon uses the term “order.” However, some computer scientists use the term “order” in slightly different ways, causing a fair amount of confusion. As such, I’m going to stay away from that term.)
Note that the maximum number of children that a B-tree node can have is the node’s maximum capacity plus 1. In the example tree, you can see that the node’s maximum capacity is 3, but the maximum number of children each node can have is 4.
B-trees make use of the key technique we’ve been discussing to minimize I/Os, which is to pack as much useful data into a block as it can. When we create a B-tree, we can take advantage of this by doing something clever: we make it so that a B-tree’s node maximum capacity is the same as the computer’s block size. So, if a computer’s block size can hold 500 values (plus the pointers to the children nodes), we would decide that our B-tree’s node maximum capacity should be 500. Let me explain why this is advantageous.
A B-tree’s data is stored in the filesystem. Because each node fits perfectly into a block, we only need one I/O to transfer a node into RAM. To see how this will help us reduce I/Os, let’s take the same 50 values from our example BST and store them in a B-tree. Let’s say that we’re still working with our tiny computer that has a block size of 4. This means that we can store 4 values plus 5 pointers to children.
The B-tree is what it may look like. I compacted the width of the tree so it can fit on the page.
As an example, suppose we are searching for the value 39. (Can you spot it?)
Recall that in our BST, it took 4 I/Os to find our desired value. Let’s see how many I/Os it takes to find the 39 inside our B-tree.
First, our computer needs to access the B-tree’s root node, which takes 1 I/O. The root node contains the values 18, 40, 68, and 87.
Because 39 is between 18 and 40, we follow the pointer that lives between 18 and 40 to find the next node. This is the node containing the values 23, 30, 32, and 38. We spend our second I/O loading this node into memory.
Now, 39 is greater than 38. Therefore, we need to follow the pointer that lies to the right of the 38, which leads to another node.
And so, we spend our third I/O loading this child. And whaddya know? The node contains the 39 we’ve been looking for!
In total, we only had to execute 3 I/Os to find our value. Now, this may only seem like a small savings compared with the 4 I/Os of the BST, but I need to point out several important things.
First, with the BST, we only surmised that it might take 4 I/Os. It’s possible that the data of the BST might be structured in a way that might take more I/Os. With our example B-tree, though, we guarantee that we can find any value in 3 I/Os.
Second, note that we’ve not filled the leaf nodes to capacity. We simply took the same 50 values from the BST and used them to populate a B-tree. This B-tree, though, has the capacity to store up to 124 values. (That’s 4 values at the root level, 20 values at the second level, and 100 values at the bottom level.) And even with 124 values, we still guarantee that we can find any value with 3 I/Os. The BST, on the other hand, could certainly take many additional I/Os if it held 124 values.
Third, I’ve used a B-tree with a node maximum capacity of 4 only because otherwise my diagram would be too large to fit on the page. In practice, B-trees often have a node maximum capacity of 1,000. This means that such a B-tree could fit one billion values on 3 levels. (1,000 * 1,000, * 1,000 = 1 billion.) And that means that we still only need 3 I/Os to find a value in such a tree!
Why B-Trees Work
Recall that the general approach to optimizing external-memory algorithms is to pack a block with useful data. Now, when it comes to B-trees, each block contains a single node. For example, if our B-tree’s nodes each contain 1,000 values, these 1,000 values are all useful because they guarantee that the node’s children values will be divided into 1,001 subsections.
Because we will only select one of those subsections, our search space has now become about one 1,000th of its original size. So, if the entire tree has one billion values, after our first I/O, we now only have one million values to search from. And after we perform our second I/O and load our next node, we use that node’s values to split the remaining search space into 1,001 subsections, each of which has 1,000 values. So, after two I/Os, we’ve reduced our total search space down to 1,000 values.
This is the same general technique we used with Optimized Search. That is, both Optimized Search and B-trees pack a block with values interspersed across the whole data set, and these values split the data set into many small subsections. Each subsection, once accessed, divides the remaining search space into even smaller subsections, and so on.
B-Tree Efficiency
Because searching a B-tree is so similar to Optimized Search, the way we describe the time complexity for both algorithms is the same.
When we search a B-tree that has a node maximum capacity of 1,000, we end up performing log1,001 N I/Os. That is, each I/O divides the search space by 1,001. We keep doing this until we find the one singular value we’re looking for. Similarly, if the node maximum capacity is 4, we perform log5 N I/Os.
Essentially, the logarithm base is determined by the node maximum capacity, which is also equal to the computer’s block size. As with Optimized Search, the logarithm base is the block size plus 1. In other words, we perform logB+1 N I/Os.
This is potentially way faster than searching a BST, where in a worst-case scenario, each I/O only includes one useful value. This means that each I/O moves us one child down the BST, which in turn reduces the remaining search space by half. This would be described as O(log2 N) I/Os.
As to how much faster B-trees are than BSTs depends on the block size. Even if a B-tree has a block size of 2, its speed of log3 N would still be considerably faster than a BST’s speed of log2 N. And as a B-tree’s block size increases, its search speed becomes faster and faster, leaving BSTs in the dust.
Again, I’ll note that in terms of pure Big O Notation, we drop the base of the algorithm, so B-tree search and BST search are technically both O(log N). However, this is another example of where Big O Notation is limited in helping us conceptualize the true difference between two competing algorithms.
B-Trees In Main Memory
We’ve seen how B-trees surpass BST speeds when it comes to external memory. But let’s say that our data is small enough to fit inside main memory. Might we still want to reach for B-trees instead of BSTs? Let’s do a quick analysis. For argument’s sake, let’s assume we’re dealing with trees that are perfectly balanced.
Here are three in-memory data structures that all hold the numbers 1 through 9 in order. We have an ordered array, a BST, and a B-tree:
Say that we’re searching for the value 4. With each data structure, we’d perform some type of binary search. Let’s walk through the steps simultaneously with all three data structures.
Step 1: With the ordered array, we perform classic binary search. This means we access the centermost value, which is the 5.
Likewise, in the BST, we access the root first, which is also the 5.
In the B-tree, we begin with the centermost value of the root node, which—you guessed it—is the 5.
Step 2: Because the 4 we’re looking for is less than 5, we must turn toward the left. With the array, we pick one of the center items in the left half of the array—say, the 3.
In the BST, we access the 5’s left child, which is the 3.
With the B-tree, we perform binary search on the root node, turning toward the left half of the node. In this case, the only item to the 5’s left is the 3.
Step 3: Because 4 is greater than 3, we must now look to the right of the 3 (but still left of the 5). In the ordered array, we find our 4 at this point.
Similarly, in the BST, we turn to the 3’s right child, which is the 4.
And with the B-tree, because there are no more values to choose from in the root node, we follow the pointer between the 3 and the 5. This leads, of course, to the 4.
It turns out that the search took the same number of steps with all three data structures. But let me remind you why we’d choose one data structure over the other, starting by comparing the ordered array with the BST.
While both data structures offer log2 N search, a BST also offers log2 N insertion and deletion. An array, on the other hand, can take as much as O(N) time for insertion. That is, if we insert or delete the left-most value of the array, we have to shift the remaining values of the array to either the right or the left.
If you don’t need fast insertions or deletions, though, an ordered array is simpler and therefore easier to implement. But if you do need insertions and deletions, a BST is faster overall than an ordered array.
Now, a B-tree is kind of a hybrid between the ordered array and the BST. It’s like a BST in that it’s a tree, but like an array in that it can hold multiple values in each node. (With this perspective, we can look at an ordered array as one giant node.)
So, a B-tree isn’t a great choice for in-memory algorithms, because it has drawbacks similar to the ordered array. That is, a B-tree will be slower than a BST when it comes to insertion and deletion. This is because a B-tree node holds multiple values like an array. So, if we insert a new left-most value into a B-tree node, we have to shift the remaining values to the right. Similarly, if we delete the left-most value, we’d have to then shift the remaining values to the left.
At the same time, if we don’t need our data structure to implement insertion and deletion, we may as well use an ordered array instead of a complicated B-tree.
So, when it comes to in-memory data structures, the B-tree usually isn’t your friend. But when it comes to external memory, the B-tree is a reliable pal.
