B-Tree Insertion

Like red-black trees and randomized treaps, B-trees are self-balancing. However, B-trees perform a different kind of self-balancing, as you’ll now see.

In the following example, we’re going to work with a B-tree whose nodes hold a maximum of 4 values. We’ll assume that our B-tree is currently empty, so we’ll start by inserting integers into the tree.

Step 1: Let’s insert a 20:

Step 2: Next, we’ll insert a 5. Because B-trees always hold their values in order, we’ll need to move the 20 one slot to the right to make room for the 5. Here’s what this looks like when we complete this:

Steps 3 and 4: We’ll add the values 68 and 103 to the tree:

Now the party begins. Say that we want to insert a 150. It turns out that our node is already full, so here’s what we’ll do. I’ll describe the algorithm first, and then show it visually so you can understand what I’m talking about.

A. Add the 150 to the current node temporarily, despite the fact that there will be too many values for the node to hold. (A node can hold just 4 values, and now there are 5.)

B. Grab the median value and remove it from the current node. The median value is the one in the center. For our example of 5, 20, 68, 103, and 150, the median value is 68.

C. Split the current node into two nodes, each of which contains half of the remaining elements.

D. Move the median value into the parent node. If no parent node exists, create a brand-new node to house the median value. This new node will now be set as the parent to the two “split” nodes we created in the previous step.

Let’s see now how this all plays out.

Step 5: Add the 150:

Step 6: Our node is now overstuffed, so we remove the median value (68) from the node, and split the current node into two:

Finally, we create a new node to house the median element and set it as the parent of the split nodes:

Note that the node with the 68 is the new root of our tree.

It can be said that a B-tree grows upward, as our original node was split into two and created a brand-new parent. This will become even more apparent as we continue with our walkthrough, so let’s move on.

Now that we have a parent with children, it’s time to introduce an important rule about B-tree insertion: we always begin insertion by inserting the new value into a leaf node. The new value may at some point work its way up the tree, but it always begins its life in a leaf node. Let’s see how this plays out in the next steps.

Steps 7 and 8: Let’s insert a 171 and 200. In theory, we could place them into the root node. But as you’ve just learned, we only insert into leaf nodes. So, we have to search the tree to find in which leaf node they belong. In our case, they belong in the right child:

Step 9: Next, we’d like to insert 258, which is a fine number indeed. However, there’s no room for it in the right child, as shown in the . This means it’s time to split!

We split the right child into two nodes while grabbing the median value, the 171. In our previous split, we created a brand-new node for the median value. Now, however, because the 171 can fit nicely into the root node, we place it there.

Let’s keep going. Until I say when, the following steps will repeat the same algorithm we’ve followed until now.

Steps 10 and 11: We’ll insert the integers 46 and 52. Remember that we always insert into a leaf node:

Step 12: Next, we’ll insert a 1. It belongs in the left-most child, but it doesn’t fit. That means we need to split:

As you can see, the median value of 20 moves up to the root node, shoving the 68 and 171 over to the right to make room.

Steps 13 and 14: Insert a 155 and 161:

Step 15: We insert a 90, causing a split:

Steps 16 and 17: Insert a 300 and 323:

Okay, my friends, it’s time. We’re up to the grand finale. (I recommend listening to the climax of Tchaikovsky’s 1812 Overture while reading the next steps.)

Step 18: We ever so innocently insert a 350, unwittingly setting off a chain reaction.

The 350 belongs in the right-most child, but there’s no room. So, we split the child, and grab the median, 300. Now, we try to insert the 300 into the root node:

But there’s no room! Can you guess what happens next?

Well, I’ll tell you. We split the root node in two, and grab its median, the 150. Because the root node has no parent, we create a brand-new root node that houses the 150 as shown in the .

In other words, whenever we split a node, we do so recursively. That is, we keep splitting nodes up the tree until we have no more nodes that are overstuffed.

I mentioned earlier that a B-tree grows upward, and this last insertion gives you a sense of that.

Well, we did it.

The B-Tree Insertion Algorithm

Let’s recap the B-Tree insertion algorithm:

1. If the tree is empty, we create a node to house the inserted value.

2. We search the tree for the correct leaf node to insert the new value, and attempt to insert the value there.

3. If, after inserting the new value, the leaf node has too many values, we recursively both split the nodes and move the median up the tree. The specific details of this are outlined in Steps 4–6.

4. Remove the median value and split the leaf node into two nodes.

5. If the leaf node doesn’t have a parent, we create a new node to house the median value. If the leaf node does have a parent, we insert the median value into the proper place within the parent.

6. If the parent now has too many values, this is where the recursion kicks in, and repeats Steps 4–6 on overstuffed nodes until there are no more nodes that have too many values.

Code Implementation: B-Tree Insertion

I’ll admit that the code for B-Tree insertion isn’t short. Don’t feel guilty if you want to skip it. It’s there for those who are interested in the nitty-gritty details.

If you’re still here, I now present to you the insertion code in all its glory, after which I’ll break it down:

Let’s take it from the top, starting with the insert method. It accepts a value parameter, which is the value we’re going to insert into our tree:

First, if the tree is entirely empty and doesn’t have any nodes yet, we create a root that will house the value we’re inserting. To accomplish this, we rely on the helper method create_root, which you can find at the end of the code listing.

Here’s the remainder of the insert method:

We call the search method from earlier in this chapter to find the value in the tree. Whether the value is in the tree or not, we get back an array with some important pieces of information. We store this array in a variable called search_result.

If we find that the first item in the search_result array is truthy, this means that the value we’re trying to insert is already in the tree. If this is the case, we simply return without doing anything else since there’s nothing else we need to do. B-trees generally do not accept duplicate values.

However, if the value is not in the tree, the first item within search_result will be None. If this is the case, the second item of search_result will be the filename of the leaf node where the value should be inserted.

At this point, we call another method, insert_into_node, that places the value into this leaf node. This other method is essentially a continuation of the insert method, but I’ve moved the remaining logic into this separate method since we’ll need to call on that same logic again in another context.

Let’s dive into that insert_into_node method now. Here’s the first chunk:

The insert_into_node method accepts the arguments node_file and value for the purpose of inserting the value into the node_file.

First, we call the helper method read_node_file, which reads the node_file and pulls out the node’s values, children, and parent.

The code continues with:

Here, we insert the value into the array of values that we pulled from the node. We then sort the values array to make sure that the new value ends up in the right spot.

At this point, our values array contains the modified node data, which now includes our inserted value. But we haven’t yet modified the node_file itself. Before doing so, though, we need to first see if the current node is overstuffed. Hence, the next bit of code:

This conditional statement checks whether the current node has too many values. Let’s first skip to the else clause, which occurs when we do not have too many values. In this simpler case, we call the write_to_node_file helper method, which overwrites the node_file’s values with the data from our new list of values.

If you take a quick glance at the write_to_node_file method, you’ll see that it accepts all the details of a node, including its parent and children pointers. Here, though, we’re passing in the parent and children that the node already has. The only thing we’re overwriting in this context is the new list of values.

Now, let’s go back to the first clause of the previous conditional statement. It handles a case where the node is now overstuffed. In this case, we call the split_node method, which we’ll explore next.

I’ll admit that the split_node method is a doozy, but I’ll walk through it gently.

The split_node method signature goes like this:

The method accepts a node_file representing the node we’ll be splitting. Additionally, the method accepts the parent, values, and children of the node we’ll be splitting.

In theory, once we are passing in the node_file, we shouldn’t have to also pass in the parent, values, and children because that data can be read from the node_file itself. However, since at the time of calling split_node we already have that data handy, we may as well pass that data along and thereby avoid performing an extra I/O.

The split_node method kicks things off with the following line:

Let me explain. Our approach to splitting a node will be to create two brand-new node files and then delete the original node file. And so, this line uses Python’s operating system module, called os, to delete the original node_file.

The next snippet creates filenames for the two new node files we’ll be creating:

We split our node by creating a new “left” node and a new “right” node, each of which will contain half the contents of the original node. When choosing filenames for these new nodes, though, we need to be sure that we aren’t using a filename that already exists, since otherwise we’ll accidentally overwrite an existing node.

There are several ways we can go about this, but because this B-tree is designed to hold integers, I’ve decided to name the files after one of the integers within the node. Since we can be sure that a particular value will not exist more than once within the tree, we can also be sure that we’re not creating a filename for one node that already belongs to another node.

To do all this, the previous snippet first finds the median_index, which represents the index in values that begins the second half of the array. The left_node_filename is named after the first integer in values, while the right_node_filename is named after the item at median_index. Again, this is the first item in the second half of the array.

Next, we decide what node file will serve as the parent for our left and right nodes:

That is, if the node we’re splitting doesn’t already have a parent, this means we have to create a brand-new node file to be the parent. (This will also become the new root of the tree.) We name the parent node file after the median value, which is going to live inside this node. If the node we’re splitting does have a parent, that existing parent will be the parent for our new left and right nodes.

In the snippet that follows, we deal with taking all the children pointers of the node we’re splitting and divvying them up between the new left and right nodes. This is necessary only for nonleaf nodes, which are otherwise known as internal nodes. Internal nodes, by definition, contain children, so we need to split them up:

If the node is an internal node, we split up the children equally, using the median_index as the halfway point. If the node doesn’t have children, which is the case for leaf nodes, there are no children to split up.

The following code creates the left and right node files and fills them with the appropriate parent, values, and children pointers:

Okay, we’re making progress! We split up most of the current node’s values into a left and right node, but there’s still a median value that needs to be moved further up the tree.

The next snippet begins to deal with this:

In this code, we state that if the split nodes don’t have a parent, then we have to create a brand-new node. This new node will house the median value and become the parent of the split nodes. Additionally, this new node becomes the root of the tree.

However, if the split nodes do have a parent, we insert the median value into that parent. The next snippet handles this. But because the upcoming snippet is somewhat involved, let me first describe the high-level strategy here.

Wait—are you still here? You’re awesome!

As I’ve said, we will insert the median value into the parent node. However, we also need to tell the parent node that it has two new children, namely, the recently created left and right nodes. On top of that, another thing we need to do to the parent is remove the pointer to the child node we deleted.

This is a somewhat delicate surgery. For example, say we have the following B-tree:

Note how the middle child pointer points to 63.txt. If we now insert a 134, that 63.txt node will split:

We insert the median value (92) into the parent, but also need to create two new child pointers. Now, just as the 63.txt child pointer was in between 3.txt and 160.txt, we have to make sure that the new children pointers are also in between 3.txt and 160.txt.

The following code executes this strategy:

We begin by reading the data from the parent node file. Then, we look at the parent node file’s children and locate the precise index where it references the node we just split. Since we are deleting that node and replacing it with a left and right node, we need to update the parent node file accordingly to reflect this. That is, in the precise spot in the file where it references the split node’s file, we remove the split node’s filename and insert the filenames of the left and right nodes.

We accomplish this by setting an updated_children array. Here’s what we do to create this variable:

1. We first include all the parent’s children filenames up until, but not including, the filename of the current node.

2. We then add the filenames of the left and right nodes we’ve recently created.

3. Finally, we add all the remaining children filenames. These are the filenames that were to the right of the filename of the current node.

At the end of the day, the updated_children array holds the parent’s original children pointers, except that we replace the pointer to the node we’ve split with pointers to the left and right nodes. Afterwards, we call the write_to_node_file method to overwrite the parent’s file.

At this point, the parent node now holds pointers to the correct children. However, we have not yet inserted the median value into the parent. We do this next:

This recursively calls the insert_into_node method (that we walked through previously) to insert the median value into the parent. It’s recursive because our current split_node method was itself called by the insert_into_node method.

Okay, we’re nearing the end of the split_node method. There’s one last major step, and that’s to deal with splitting an internal node. Whenever we split an internal node, it’s because we’ve previously split a leaf node, and we’re trying to insert the leaf node’s median value into an internal node that’s already full.

Now, here’s the problem. When we first split the leaf node into two new nodes, we couldn’t tell these two nodes who their parent is. It might be tempting to simply tell them that their parent is the deleted node’s parent, but here’s the catch: we’re about to split and delete the parent!

Because of this, we can only tell the children who their parents are after we’ve done all the splitting and have created nodes that are here to stay. We do this with the following code:

That is, we tell the children of the left node that their parent is the left_node_filename, and we tell the right node’s children that their parent is the right_node_filename.

AND. THAT’S. A. WRAP. Whew! We’re done with B-tree insertion.