Implementing B-Trees

There are numerous ways to implement a B-tree. Here, I’ve chosen a simple approach that will allow us to focus on the big picture of how B-trees work while avoiding getting into the weeds of optimizations and other hacks.

Let’s begin by implementing a B-tree node. To mimic real life, I’ll create nodes that will force the computer to perform an I/O to access the node. Specifically, I’m going to store each node in a separate file.

Our example node file is called root.csv. On the right side, you’ll see a visual of the node we’re representing with this file. On the left side, you’ll see the file itself:

There are many ways I could have chosen to store the data in the file, but this was my arbitrary choice.

Each file stores a node’s data using comma-separated values plus newlines. Accordingly, I’ve called the file extension .csv, which is a common convention for such files.

On the first line of the file, we store the filename of the node’s parent. In this example, the file represents the root node, so it doesn’t have a parent, and that’s why the word None appears in the first line. The second line stores the node’s values, and the third line stores the filenames of the node’s children.

Here is a complete set of files representing an entire B-tree. To make the visual clearer, in the root.csv file, I added spacing around the values 5, 20, and 42, but in reality, those extra spaces will not exist:

Because each node is stored in a file, I’m not going to bother writing code to represent a node. All the information we need is already stored in the file itself!

Code Implementation: B-Tree Search

Let’s continue our B-tree implementation by creating the search functionality. There’s a fair bit of code here, but I’ll break it down:

Note that at the top of the file, we import the os Python module. We won’t be using it for our search method, but we’ll need it when we implement B-tree insertion later.

We kick off our BTree class like this:

The only class variable we keep track of is the file representing the root of the tree. When we create a brand-new empty tree, this will be None since we won’t create the file until we begin adding actual data to the tree. But let’s assume that when we call the search method, our tree already consists of multiple files.

Our search method begins as follows:

The search method expects a search_value and a node, which will be a string representing the filename of one of the tree’s nodes. The search will begin from that node.

The method begins by creating a variable called node_file which, at the beginning of a search, will point to the tree’s root. Later, we’ll recursively call the search method on children nodes, in which case the node_file will point to whichever child node we’re searching next.

We then call a helper method called read_node_file, which reads the node_file and retrieves all of its data and stores it in the node_data variable. The data is stored as a hash table and contains the keys values and children. (It also contains parent, but we’re not going to use that right now.) We’ll analyze the read_node_file method soon, but for now, let’s continue to plow forward.

The next section is a loop that compares our search_value to each of the values in the node:

We create an index variable which starts at 0, and use this variable to retrieve each value of the node using values[index]. As we iterate, each subsequent value of the node becomes the current_value.

If current_value == search_value, meaning that we found our search_value in the node, we happily return the information regarding our find. I’ve chosen to return an array containing three values. The first contains True to indicate that the search_value is contained in the tree. (We return False if the search_value is not there.) Additionally, we return the node_file where the search_value can be found and the index pointing to the exact spot within the node where the search_value is located. Depending on what you’re using a B-tree for, you may want to return other information.

If the current node does not contain the search_value, we continue our loop:

As we compare the search_value to each value in the node (the current_value), we check to see if the search_value is less than the current_value. If it is, and the current node has children, we want to follow the child pointer that is found immediately to the “left” of the current_value. This ends up being children[index]. That is, if we’re up to, for example, the third value in the node, the third child in the node will be that value’s “left” child. We store the child’s filename in a variable called child_to_follow. (At the end of our method, we’ll recursively call the search method on that child.) We also terminate the loop early at this point since we’ve already found the child we’re looking for.

If, however, this node does not contain children, which is the case for leaf nodes, it must mean that the search_value is not present in the tree. Accordingly, we return an array whose first value is False to indicate this. Additionally, we return the node_file and index to represent the spot where the search_value should go if it were to exist. This information will be useful when we insert a new value into the B-tree.

Finally, we increment index and start the next round of the loop, which will continue until the index moves beyond all the values we have in the current node.

The next bit of code occurs when we reach the end of the current node without finding the search_value:

We check whether the search_value is greater than the current_value. Because this code occurs after the loop has been terminated, the search_value being greater than the current_value can only happen if the search_value is greater than all the values in the array.

Because the search_value is greater than all the values in the current node, we now have two possible paths. If the current node has no children, this means that the search_value is simply not present in the tree, so we include False in the array that we return.

But if the final value in the current node has a “right” child pointer, the corresponding child is the node we need to traverse next, so we assign that node to the child_to_follow variable. Again, the right-most child of the current node will contain values that are greater than the current node’s right-most value. So, if the current node’s final value is 56, and we’re searching for a 73, we need to move on to the current node’s right-most child.

Finally, our method concludes with the following line:

That is, we recursively call this search method on whichever child node we have chosen to follow next.

You may notice that I’ve chosen to perform a linear search on each node. That is, we use the while loop to sequentially compare the search_value with each value of the current node. We could, alternatively, have performed a binary search on each node, which would be a faster approach. I chose the linear search approach to keep our code simpler. In any case, don’t forget the main idea I’ve been emphasizing throughout this chapter: when dealing with external memory, our primary focus should be on the number of I/Os that occur and not on the in-memory steps. Although performing binary search on the current node will reduce in-memory steps, it will not reduce the number of I/Os. I’ve aimed for simplicity instead.