A B-tree is a sort of self-balancing search tree whereby each node could have more than two children and hold multiple keys. It’s a broader version of the binary search tree. It is also usually called a height-balanced m-way tree.
In this article, we will dive deeper into B Tree according to the GATE Syllabus for (Computer Science Engineering) CSE. Keep reading ahead to learn more.
Table of Contents
- What is B Tree in Data Structure?
- Need of a B Tree in a Data Structure
- Properties of B Tree in DBMS
- Operations
- B Tree Application
- Practice Problems on B Tree
What is B Tree in Data Structure?
The B Tree is a particular m-way tree which can be used to access discs in a variety of ways. At most m children and m-1 keys can be found in a B-Tree of order m. One of the main advantages of the B tree is its capacity to store a large number of keys inside a single node and huge key values while keeping the tree’s height low.
Need of a B Tree in a Data Structure
The need for B-tree emerged as the demand for faster access to physical storage media such as a hard disk grew. With a bigger capacity, backup storage devices were slower. There was a demand for data structures that reduced the number of disc accesses.
A binary search tree, an AVL tree, a red-black tree, and other data structures can only store one key in each node. When you need to store a significant number of keys, the height of such trees grows quite vast, and the time it takes to access them grows.
B-tree, on the other hand, can store multiple keys inside a single node and has several child nodes. It considerably reduces the height, allowing for speedier disk access.
B Tree Example
Properties of B Tree in DBMS
All of the features of a M way tree are present in a B tree of order m. Additionally, it has the following features:
- In a B-Tree, each node has a maximum of m children.
- Except for the root and leaf nodes, each node in a B-Tree has at least m/2 children.
- There must be at least two root nodes.
- The level of all the leaf nodes should be the same.
It is not required that all nodes have the same number of children, but each node must include m/2 nodes.
The following graphic depicts a B tree of order 4:
Any attribute of B Tree may be violated while performing some operations on it, such as the number of minimum children each node can have. The tree may split or unite in order to keep the features of the B Tree.
Operations
Search Operation
B Trees are comparable to Binary Search Trees in terms of searching. For example, let’s look for item 49 in the B Tree below. The procedure will go somewhat like this:
- Compare item 49 to node 78, which is the root node. Move to the left sub-tree since 49 < 78.
- Since 40 < 49 < 56, move to the right subtree of 40. If 49>45, move to the right, and then compare and contrast 49.
- Return if a match is found.
The height of the tree affects the search in a B tree. To search an element in a B tree, the search technique requires O(log n) time.
Insertion Operation
At the leaf node level, insertions are made. In order to place an item into B Tree, the following algorithm must be followed:
- Navigate the B Tree until you find the suitable leaf node to insert the node at.
- If there are fewer than m-1 keys in the leaf node, insert the elements in ascending order.
Otherwise, if the leaf node comprises m-1 keys, proceed to the next step.
- In the rising sequence of elements, add the new element.
- In the middle, divide the node into two nodes.
- The median element should be pushed up to its parent node.
- If the parent node has the same m-1 number of keys as the child node, split it as well using the very same steps.
Example
In the B Tree of order 5, insert node 8 as indicated in the diagram.
Because 8 will be put to the right of 5, enter 8.
There are now 5 keys in the node, which is more than (5 -1 = 4) keys. As a result, divide the node from the median, which is number 8, and push it up to its parent node, as illustrated below.
Deletion Operation
At the leaf nodes, deletion is also conducted. It can be a leaf node or an inside node that needs to be destroyed. In order to delete a node from a B tree, use the following algorithm:
1. Determine the location of the leaf node.
2. If the leaf node has more than m/2 keys, delete the required key from the node.
3. If the leaf node lacks m/2 keys, fill in the gaps with the element from the eighth or left sibling.
- If the left sibling has more than m/2 elements, shift the intervening element downwards to the node wherever the key is deleted and push the largest element back to its parent.
- If the right sibling has more than m/2 items, shift the intervening element downwards to the node wherever the key is deleted, then push the smallest element up to the parent.
4. Create a new leaf node by merging two leaf nodes and the parent node’s intervening element if neither sibling has more than m/2 elements.
5. If the parent has less than m/2 nodes, repeat the operation on the parent as well.
If the node to be destroyed is an internal node, its in-order successor or predecessor should be used instead. The process will be the same as the node is deleted from the leaf node because the successor/predecessor would always be on the leaf node.
Example 1
Remove node 53 from B Tree of the order 5, as indicated in the diagram below:
Element 49’s right child contains the number 53. Remove it.
Now that 57 is the only element left in the node, the minimal number of elements required in a B tree of rank 5 is 2. Because the elements in its left and right subtrees are similarly insufficient, combine it with the left sibling of the intervening element of the parent, i.e. 49.
The following is the final B tree:
B Tree Application
Because accessing values held in a huge database, saved on a disc, is a very time-consuming activity, the B tree is used to index the data and enable quick access to the actual information stored on the discs.
In the worst situation, searching an unindexed and unsorted database with n key values takes O(n) time. Also, if we use B Tree for indexing this DB, it will be searched in about O(log n) time.
Practice Problems on B Tree
1. The B-trees of the order 4 and height 3 would have a maximum of ________ keys.
a. 188
b. 127
c. 63
d. 255
Answer- (d) 255
2. If five node splitting operations occur when some entry is inserted in a B-tree, how many nodes would be written?
a. 5
b. 11
c. 7
d. 14
Answer- (b) 11
3. AVL tree and B-tree consist of a similar worst case time complexity for deletion and insertion.
a. True
b. False
Answer- (a) True
4. 2-3-4 trees refer to the B-trees of order 4. These are an isometric of the _______ trees.
a. AA
b. AVL
c. Red-Black
d. 2-3
Answer- (c) Red-Black
Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus, GATE Previous Year Question Paper, and more.
Also Explore,
Comments