B+ trees an interesting name isn't it? So in this article, we will closely analyze the time & space complexities for different operations in different cases of B+ Tree Data Structure.

Table Of Contents

• B+ Tree Briefed
• Analysis Of Search Operation
  • Best Case
  • Average Case
  • Worst Case
• Analysis Of Insertion Operation
  • Best Case
  • Average Case
  • Worst Case
• Analysis Of Deletion Operation
  • Best Case
  • Average Case
  • Worst Case
• In Short

B+ Tree Briefed

B+ tree can be defined as a self-balancing tree data structure which can store data in a sorted order. B+ tree is a variant of the B-Tree, which itself is a generalization of a binary tree.

Each node in a B+ tree contains a number of keys, which are used to identify the data stored in the tree. The data stored in these keys are always in sorted order. Pointers are used to navigate to the child nodes, these child nodes contain the actual data in a B+ tree and these nodes are linked to each other using pointers. In short we can say that the these nodes form a linked list of leaf nodes. With these properties B+ tree provides fastest insertion, deletion and search operations while still maintaining a relatively small tree size.

Lets analyze each of these operations

Analysis Of Searching Operation

To search for a particular value in a B+ tree, you can start at the root of the tree and compare the value you are searching for, to the values stored in the internal nodes of the tree. If the value you are searching for is less than the value stored in the current node, you can follow the pointer to the left child node and continue the search. If the value you are searching for is greater than the value stored in the current node, you can follow the pointer to the right child node and continue the search.

This process continues until you reach a leaf node, at which point you can perform a linear search through the values stored in the leaf node to see if the value you are searching for is present. At this stage if you encounter a value greater than the searching value then, you can conclude that it is not present in the tree.

Best Case

In a B+ tree, the best-case search time occurs when the value you are searching for is present in the root node of the tree, or when the root node has only one child and the value you are searching for is present in the leaf node of that child. In either of these cases, the search will take only a single step, as you will not need to follow any pointers to other nodes in the tree.
Hence the time complexity would be O(1), which means that it is constant and does not depend on the size of the tree. This is because the root node of the tree is always immediately accessible, and if the value you are searching for is present in the root node, you can find it without having to follow any pointers to other nodes in the tree.
The space complexity of a B+ tree search in the best case is also O(1), as it does not depend on the size of the tree. This is because the search process only involves comparing the value you are searching for to the values stored in the internal nodes of the tree, and does not require any additional storage space.

Average Case

In average case the time complexity is O(log n) where n is the number of values stored. This means that the time required to search for a particular value is proportional to the logarithm of the number of values in the tree. The reason for this is that in a B+ tree, the root node has a fixed number of nodes and each node has fixed number of children. Hence the height of the tree will be logarithmic in number of values it contains, and the search time will be proportional to the height of the tree.
The space complexity of a B+ tree search in the average case is also O(log n), as it has to keep a track on the entire process.

Worst Case

The worst-case scenario for a B+ tree search occurs when the tree is completely unbalanced, with all of the values stored in a single long chain of leaf nodes. In this case, the search process will involve following a path through the tree that is linear in the number of values stored in the tree, resulting in a worst-case time complexity of O(n).

The space complexity of a B+ tree search in the worst case is also O(n), as it involves following a path through the tree that is linear in the number of values stored in the tree.

Analysis Of Insertion Operation

Before we analyze it, lets understand how it works.

1. First we start at the root node of the tree and then we will navigate down the tree using pointers and keys at each node until we reach the leaf node.
   Note: As we discussed earlier these leaf nodes will have almost all the data in the tree, stored in a sorted order with a pointer linking each of the node with the each other.
2. If the leaf node has space for a new key then insert the data into the node in the correct position to maintain the sorted order of the keys. If the leaf node is full then split the node into two, with half of the keys going to each nodes.
3. Add the new key into the parent node, in case the parent node is full repeat the same process again until you reach the root node.
4. If the root node splits and creates a new root node, update the root of the tree to point to the new node.

Best Case

The best case for inserting a new element into a B+ tree is when the value being inserted is the only value in the tree, or when the value being inserted is the first value in an empty leaf node.
In this case all we have to do is to just insert the new key. Hence we can say that the time complexity would be O(1).

In the case of space complexity, its O(1), this is because we would not need to create any new nodes to accommodate the new key.

Average Case

Average case keeps on changing as it depends on the specific distribution of the keys in the tree and the size of nodes. But we can say the following.

• When you think of time complexity it would be O(log n) where n is the total number of keys present in the tree. This is because we need to traverse the tree from the root to the leaf node in order to find the correct place to insert the new key, and the height of the tree is logarithmic in the number of keys.
• In the case of space complexity, the average case will depend on the distribution of keys in the tree.
  • If the tree is well-balanced and the nodes are not full then the average case for inserting new key would be O(1) space complexity, as we may not need to create any new nodes to accommodate it.
  • If the tree is poorly balanced and the nodes are too full then we may need to split multiple nodes in the tree, which could increase the space complexity of the operation.

Worst case

The worst case scenario will occur if the tree is poorly balanced or the nodes are too full, and the new key needs to be inserted at the leaf nodes of the tree. If this case occurs we might need to split every node in the path from the root to the leaf node, creating a new node at each level of the tree.

Hence we can say that it will take O(n) time, where n is the total number of nodes in the tree.
We would also need to create n new nodes to accommodate the new key, hence the space complexity would be O(n).

Analysis Of Deletion Operation

In a B+ tree deletion is a bit more complex than insertion. During this operation we need to make sure that we maintain the balance and search properties of the tree.
Normal Procedure for deleting a key from a B+ tree.

• First locate the key using the searching procedure.
• If the key found is in leaf node with more than one element, just delete it.
• If the key found is in an internal node, then:
  • If the child node containing the key to be deleted has at least the minimum number of keys required then simply delete the key from the internal node and the child node.
  • If the child node does not have the minimum number of keys required, it must be merged with one of its siblings or have a key borrowed from one of its siblings. In either case, the internal node must also be updated to reflect the change.
• If the root node is left with only one child after the deletion, make the child the new root of the tree.

Now lets analyze the cases and complexities.

Best case

The best case occurs when the root node is to be deleted, or when the there are very few leaf nodes and keys. In this case all we have to do is to reach the correct position and delete it. The time complexity for this would be O(1).
The space complexity would be O(1) too, as no node will be created.

Average Case

The average case occurs when the tree is a balanced B+ tree. In this case the search procedure for finding the key to be deleted involves traversing down a well-balanced B+ tree, the height of the tree is logarithmic with respect to the number of days.

Hence the time complexity is O(log n) where n is the number of keys in the tree.

The space complexity to delete a key in best case will be O(log n), this is because during the search operation it requires you to store a stack of nodes to keep track of the path through the tree.

Worst Case

The worst case occurs when the tree is highly unbalanced, and the key to be deleted is located at the leaf level at the bottom of the tree. So here the search operation requires you to traverse through every node which would take O(n) time.
The space complexity on the other hand would be O(n) where n is the number of keys in the tree. This is because it may be necessary to store the entire tree in memory in order to perform the deletion.

In Short

• Searching
  • Best Case
    • Time Complexity: O(1)
    • Space Complexity: O(1)
  • Average Case
    • Time Complexity: O(log n)
    • Space Complexity: O(log n)
  • Worst Case
    • Time Complexity: O(n)
    • Space Complexity: O(n)
• Insertion
  • Best Case
    • Time Complexity: O(1)
    • Space Complexity: O(1)
  • Average Case
    • Time Complexity: O(log n)
    • Space Complexity: O(1), will increase to O(log n) if tree is unbalanced
  • Worst Case
    • Time Complexity: O(n)
    • Space Complexity: O(n)
• Deletion
  • Best Case
    • Time Complexity: O(1)
    • Space Complexity: O(1)
  • Average Case
    • Time Complexity: O(log n)
    • Space Complexity: O(log n)
  • Worst Case
    • Time Complexity: O(n)
    • Space Complexity: O(n)

With this article at OpenGenus, you must have the complete idea of Time and Space Complexity of B+ Tree.