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 in a systematic manner. 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 order of the B-Tree. 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 in such a way 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 the median element is upped by a level.
1. Insertion Operation
We will see how insertion happens into a B-Tree for a set of numbers which is 6, 10, 5, 8, 2, 4, 9, 7, 1, and 5.5 as follows.
- 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 and 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 very important. 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.
4.7 (3,220 ratings)
View Course
- Let’s consider that we intend to delete 5 from the above B-Tree. 5 is present in the leaf node, so it will get deleted giving the B-Tree arrangement as 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 the nodes of B-Tree, then deletion operation can be made simpler.
Conclusion
B-Tree is one of those data structures that efficiently assist in data operations including insertion, deletion, and traversal. The usefulness of data structure as this is evident not in small applications but is impactful in real-world situations that involve very large 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 –
