B Tree in Data Structure

Introduction to B Tree in Data Structure

B-Tree is a data structure that stores data and allows operations such as searching, insertion, and deletion systematically. There are certain aspects associated with B-Tree, which deal with the tree in its balanced form. So, for having the balanced tree, there should be n/2 keys in each node, n being the B-Tree order. The other considerations are as follows.

• All leaf nodes must be present at the same level.
• There can be at maximum n – 1 key for all nodes.
• There are at least two children for the root.
• n is the maximum number of children, and k is the number of keys that each node can contain.
• There are at least n/2 children and at most n non-empty children.
• The tree gets divided so that values in the left subtree shall be less than the value in the right subtree.

B-Tree Visual Representation

A sample visual representation of B-Tree is as shown below. It is a balanced tree that follows all the constraints which are associated with the concept.

In the above B-Tree, all the leaf nodes are at the same level. The number of keys in non-leaf nodes is less than that of in the children nodes.

How does B-Tree Data Structure Works?

Let’s understand the working of B-Tree through insertion and deletion operations. There are two cases associated with the insertion of a key in B-Tree. These are, first that node is not full, and secondly, the node is already full. Insertion of a key happens in the node if it’s a leaf node that is not full. In case the node is full, then the node is split at the median into two nodes, the level remaining the same, and a level ups the median element.

1. Insertion Operation

We will see how insertion happens into a B-Tree for a set of 6, 10, 5, 8, 2, 4, 9, 7, 1, and 5.5.

• The first Element Inserted is 6.

• Next Element to be Inserted is 10. It is greater than 6, and so will go to the right of it as shown below.

• 5 is less than 6, so it goes to the left of the tree, as shown below.

• Now, before the next element is inserted, it is checked if the tree is full. As the tree is now full, so a new empty node is allocated. This node is made the root, while the former root is split, with 6 put into the new root. So, when 8 gets inserted into the tree, the arrangement becomes as shown below.

• The next element to be inserted is 2. It will go in the left subtree before 5. The arrangement now looks like as shown below.

• Now, the next element to be inserted is 4. It goes into the left subtree as it is less than 6. It occupies the middle position in the node as shown by the following B- tree arrangement.

• The next step is essential. We now have 9 and 7 as the next two elements to be inserted into the B-Tree. As the node is full in this case, it is split, and the middle child is brought into the root. We get the B-Tree arrangement as can be seen below. Here, 9 went into the root, while 7 joined 8, with 10 going into a separate node.

• The last two elements that we have are 1 and 5.5. 1 will go into the left subtree with 2, 4, and 5. The tree is split, and the middle child is sent up the root. Now, we have 5 and 5.5 in a separate node. The B-Tree arrangement looks like, as shown below.

2. Deletion from B-Tree

While performing the deletion from B-Tree, a traversal through the tree happens. After reaching the concerned node two cases may occur, the first node is the lead node, and the second node is the non-leaf node. We shall see how deletion happens in B-Tree through the following example.

• Let’s consider that we intend to delete 5 from the above B-Tree arrangement 5 is present in the leaf node, so it will be deleted, giving the B-Tree arrangement below.

• Now, what if we delete a non-leaf node. 4 is a non-leaf node. We shall delete it. Once 4 is deleted, we get the arrangement as shown below.

• So, we find 5.5 and 9 going up by one level. 5.5 goes into the node having 1 and 2. 9, on the other hand, goes into the root node along with 6.

Advantages of B-Tree

Below are the advantages of B-Tree:

• B-Tree facilitates ordered sequential access, and so it works effectively as compared to a hash table.
• It allows iterations over items in a much similar way as what is supported by a binary tree. The iterations arrange the items in the proper order (ascending or descending) as required.
• The tree can have millions of items stored in it, and through its flat structure, it facilitates easy and efficient traversal through the data.
• When there are millions of records, then deleting a record from a table can turn out to be expensive, because the table may need to be rewritten. However, if B-Tree is used to handle sequential access to the table, or if the entire data is stored in B-Tree nodes, then deletion operation can be made simpler.

Conclusion

B-Tree is a data structure that efficiently assists in data operations, including insertion, deletion, and traversal. The usefulness of data structure is evident not in small applications but is impactful in real-world situations involving huge datasets.

Recommended Articles

This is a guide to B Tree in Data Structure. Here we discuss data operations including insertion, deletion, and traversal with advantages. You can also go through our other related articles to learn more –

1. What is Data Structure?
2. Types of Trees in Data Structure
3. Data Structure Interview Questions
4. Data Science Applications
5. Working of Stack in Data Structure