B+ TREE: Search, Insert and Delete Operations

What is a B+ Tree?

A B+ Tree is primarily utilized for implementing dynamic indexing on multiple levels. Compared to a B- Tree, the B+ Tree stores the data pointers only at the leaf nodes of the Tree, which makes the search process more accurate and faster.

Rules for B+ Tree

Here are essential rules for a B+ Tree.

• Leaves are used to store data records.
• Records are stored in the internal nodes of the Tree.
• If a target key value is less than the internal node, then the pointer just to its left side is followed.
• If a target key value is greater than or equal to the internal node, then the pointer just to its right side is followed.
• The root has a minimum of two children.

Why use B+ Tree

Here are reasons for using a B+ Tree:

• Keys are primarily utilized to aid the search by directing to the proper leaf.
• A B+ Tree uses a “fill factor” to manage the increase and decrease in a tree.
• In B+ trees, numerous keys can easily be placed on the page of memory because they do not have the data associated with the interior nodes. Therefore, it will quickly access tree data that is on the leaf node.
• A comprehensive full scan of all the elements needs just one linear pass because all the leaf nodes of a B+ tree are linked with each other.

B+ Tree vs. B Tree

Here are the main differences between a B+ Tree and a B Tree.

Search Operation

In a B+ Tree, a search is one of the easiest procedures to execute and gives fast and accurate results.

The following search algorithm is applicable:

• To find the required record, you need to execute the binary search on the available records in the Tree.
• In case of an exact match with the search key, the corresponding record is returned to the user.
• In case the exact key is not located by the search in the parent, current, or leaf node, then a “not found message” is displayed to the user.
• The search process can be re-run for better and more accurate results.

Search Operation Algorithm

1. Call the binary search method on the records in the B+ Tree.
2. If the search parameters match the exact key
       The accurate result is returned and displayed to the user
   Else, if the node being searched is the current and the exact key is not found by the algorithm
       Display the statement "Recordset cannot be found."

Output: The matched record set against the exact key is displayed to the user; otherwise, a failed attempt is shown to the user.

Insert Operation

The following algorithm is applicable for the insert operation:

• 50 percent of the elements in the nodes are moved to a new leaf for storage.
• The parent of the new leaf is linked accurately with the minimum key value and a new location in the Tree.
• Split the parent node into more locations in case it gets fully utilized.
• Now, for better results, the center key is associated with the top-level node of that leaf.
• Until the top-level node is not found, keep on iterating the process explained in the above steps.

Insert Operation Algorithm

1. If inserting at least 1 entry into the leaf container does not make it full, then add the record.
2. Else, divide the node into more locations to fit more records.
   a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the tree.
   b. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.
   c. Divide the top-level node if it gets full of keys and addresses.
      i. Similarly, insert a key in the center of the top-level node in the hierarchy of the Tree.
   d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore.
3. Build a new top-level root node of 1 key and 2 indicators.

Output: The algorithm will determine the element and successfully insert it in the required leaf node.

The above B+ Tree sample example is explained in the steps below:

• Firstly, we have 3 nodes, and the first 3 elements, which are 1, 4, and 6, are added in appropriate locations in the nodes.
• The next value in the series of data is 12, which needs to be made part of the Tree.
• To achieve this, divide the node and add 6 as a pointer element.
• Now, a right-hierarchy of a tree is created, and the remaining data values are adjusted accordingly by keeping in mind the applicable rules of equal to or greater than values against the key-value nodes on the right.

Delete Operation

The complexity of the delete procedure in the B+ Tree surpasses that of the insert and search functionality.

The following algorithm is applicable while deleting an element from the B+ Tree:

• Firstly, we need to locate a leaf entry in the Tree that is holding the key and pointer, then delete the leaf entry from the Tree if the leaf fulfills the exact conditions of record deletion.
• In case the leaf node only meets the satisfactory factor of being half full, then the operation is completed; otherwise, the leaf node has minimum entries and cannot be deleted.
• The other linked nodes on the right and left can vacate any entries and then move them to the leaf. If these criteria are not fulfilled, then they should combine the leaf node and its linked node in the tree hierarchy.
• Upon merging of a leaf node with its neighbors on the right or left, entries of values in the leaf node or linked neighbor pointing to the top-level node are deleted.

The example above illustrates the procedure to remove an element from a B+ Tree of a specific order.

• Firstly, the exact locations of the element to be deleted are identified in the Tree.
• Here, the element to be deleted can only be accurately identified at the leaf level and not at the index placement. Hence, the element can be deleted without affecting the rules of deletion, which is the value of the bare-minimum key.

• In the above example, we have to delete 31 from the Tree.
• We need to locate the instances of 31 in the Index and Leaf.
• We can see that 31 is available at both the Index and Leaf node level. Hence, we delete it from both instances.
• But we have to fill the index pointing to 42. We will now look at the right child under 25 and take the minimum value and place it as an index. So, 42 being the only value present, it will become the index.

Delete Operation Algorithm

1) Start at the root and go up to the leaf node containing the key K.
2) Find the node n on the path from the root to the leaf node containing K.
   A. If n is root, remove K
      a. if root has more than one key, done
      b. if root has only K
         i)  if any of its child nodes can lend a node
             Borrow key from the child and adjust child links
         ii) Otherwise merge the children nodes. It will be a new root
      c. If n is an internal node, remove K
         i)  If n has at least ceil(m/2) keys, done!
         ii) If n has less than ceil(m/2) keys,
             If a sibling can lend a key,
                Borrow key from the sibling and adjust keys in n and the parent node
                Adjust child links
             Else
                Merge n with its sibling
                Adjust child links
      d. If n is a leaf node, remove K
         i)  If n has at least ceil(M/2) elements, done!
             In case the smallest key is deleted, push up the next key
         ii) If n has less than ceil(m/2) elements
             If the sibling can lend a key
                Borrow key from a sibling and adjust keys in n and its parent node
             Else
                Merge n and its sibling
                Adjust keys in the parent node

Output: The key “K” is deleted, and keys are borrowed from siblings for adjusting values in n and its parent nodes if needed.

FAQs