Splitting and Merging B Tree Nodes

This post is to be read in conjunction with another post Introduction to B Trees. Here we learn that in certain operations the B Tree properties might get disturbed and it will need a fix. Splitting and Merging B Tree Nodes are the only operations which can re-establish the properties of the B Tree.

How does a B Tree get unbalanced?

The tree is not just to read and search data. There are operations which update the tree either by deleting a key, inserting a new key or just updating the values stored against the key.

The Insert and Delete operations tend to modify the structure of the tree. In such an operation, there might be cases as mentioned below :

  • If a node is already full, then a new key insertion will overflow and disturb the B Tree property. It would need re-establishment of the property, which is ideally achieved by splitting the node in question.
  • If a node has the minimum number of keys, then deleting a key from the node will cause an underflow and it would violate the B Tree property. It needs to be merged to another node to fix the B Tree back.

It is important to note that not all insertions and deletions will result into violation of B Tree properties of the tree nodes. All the insertion and deletion operations are listed below:

  • Inserting a key
    • at the leaf node
      • leaf node is full (Violates the B Tree property and hence needs a split of the node)
      • leaf node is not full
    • at internal node
      • internal node is full (Violates the B Tree property and hence needs a split of the node)
      • internal node is not full
  • Deleting a key
    • at leaf node
      • leaf node contains D-1 keys, where D is the degree of the tree. (Violates the B Tree property and hence needs a merging of this node with its neighbor)
      • leaf node contains more than D-1 keys
    • at internal node
      • leaf node contains D-1 keys (Violates the B Tree property and hence needs a merging of this node with its neighbor)
      • leaf node contains more than D-1 keys

Here I explains with diagrams, how to split/merge a node.

Splitting a B Tree Node

Consider the below B Tree (in figure 1) with minimum degree D = 3. Now, let us try to insert a key F into this tree. Clearly F must go into the leaf node which already has keys (A, B, C, D, E).

Splitting and Merging B Tree Nodes

The maximum number of keys a node can have for D=3 is 2D-1, which is equal to 6-1 = 5. As we can see that the node already has 5 keys, adding F into the node will overflow and violate the tree property. Hence, we have to fix this, and when a node over grows, we split it.

Steps involved in splitting a node X (Assumption, the parent of the node X is not full)

  • Find the median of the full node. (here it would be C)
  • Create a new leaf node and copy into it all the keys which appear after the median.
  • Move up the median at an appropriate position in the parent of this node.
  • Add an additional child pointer (after the median) from the parent node to the new node.
  • Add the new key at the right location in the child nodes of the median.

The new tree after splitting would look like the below the one in figure (2).

What happens when we split the root?

As we saw that a split always moves the median one level up. In case we have a root which is full and it demands a split due to some insertion operation, we move the median of the root node, one level up. This precisely means that a new root node is created with just one element (the median) and the height of the tree grows by one.

Worth noting, this is the only way to increase the height of the tree.

Merging two nodes of a B Tree

Consider the B Tree in figure (3). Let us try to delete an element G from the tree.

Splitting and Merging B Tree Nodes

As the minimum number of keys a node must have is D-1 , which is 3-1 = 2. If we just delete G from the node, it would still satisfy the B Tree property.

But the moment we delete G, it will also lose one of the child pointers, hence we need to merge the two nodes containing (D,E) and (J,K).

The tree in figure (4) is represents the structure after merger. You may notice that the merge was pretty straightforward in this case, as the merged node didn’t violate any of the tree properties.

Steps involved in merging two nodes Y and Z with a common parent node X

  • Find the key K in node X which separates the two nodes Y and Z
  • Shift all the keys of Z to Y (maintain the existing order) and free Z
  • Move down the key K from node X to node Y

 

What is the purpose of a merge?

Of course the motive behind merge is to re establish the B Tree properties, which got violated due to Deletes. So, there needs to be a fourth bullet point above, which says Delete the key K from node Y.  There are many cases we need to take care while handling deletes and we will talk about it in a post specific to B Tree operations.

How does the structure get impacted upon Merge?

We noticed that the key K is pushed to another node at a lower level and hence, it might recursively gets pushed down to the leaves in certain case, It may end up in overflows at some nodes and also demand a split. Let us reserve this discussion for the post on Deletion in a B Tree.

Conclusion

This post helped us understand the two techniques used in most of the balancing operations of the B Tree. It will make more sense when we discuss B Tree Insert and Delete in the next post.

Stay connected and Stay subscribed.