A B+ Tree is a more advanced self-balancing tree. In this, all the values are present at the leaf level. B+ Tree in the data structure is a B Tree enhancement that enables faster insertion, deletion, and search operations.
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 DBMS?
- B+ Tree Properties
- Pros of B+ Tree
- B+ Tree Structure
- Searching Records in B+ Tree
- Insertion in B+ Tree
- Deletion in B+ Tree
- Practice Problems on B+ Tree
What is B+ Tree in DBMS?
A balanced binary search tree is the B+ Tree. It uses a multilevel indexing system. Leaf nodes in the B plus tree represent actual data references. The B plus tree keeps all of the leaf nodes at the same height. A link list is used to connect the leaf nodes in the B+ Tree. As a result, a B+ Tree can allow both random and sequential access.
Multilevel indexing is a crucial topic to grasp before understanding B+ Tree in the data structure. The index of indices is formed in multilevel indexing, as shown in the diagram below. It facilitates and accelerates data access.
B+ Tree Properties
- The leaves are all at the same height.
- There are at least two children in the root.
- Except for root, each node can have a max of m children and a min of m/2 children.
- A max of m – 1 keys and a min of m/2 – 1 keys can be stored in each node.
Both keys and records can be placed in the internal and leaf nodes of a B Tree. In a B+ Tree, records or data can only be kept on the leaf nodes, whereas key values can only be placed on the internal nodes.
To make search queries more efficient, the leaf nodes of the B plus tree in the data structure are connected together in the form of singly-linked lists.
B+ Trees are used to store vast amounts of data that are too large to fit in the main memory. The internal nodes of the B+ Tree (the keys to access records) are securely stored memory, whereas leaf nodes are placed in the secondary memory due to the restricted amount of main memory.
B plus tree internal nodes are often referred to as index nodes. The following diagram depicts a B+ Tree of order 3.
Pros of B+ Tree
- In an equal number of disc accesses, records can be retrieved.
- In comparison to the B tree, the B+ Tree’s height stays balanced and is lower.
- The stored data in a B+ Tree can be accessed both sequentially and directly.
- Indexing is done via keys.
- Because the data is only stored on the leaf nodes, search queries are faster.
B+ Tree Structure
- Every leaf node in the B+ Tree is at the same distance from the root node. The B+ Tree has an order of n, with n being the same for all B plus trees.
- It has a leaf node and an internal node.
Internal Node
- Except for the root node, an internal node present in the B+ Tree can at least have n/2 record pointers.
- The internal node of the tree can only have n pointers.
Leaf Node
- At least n/2 key values and n/2 record pointers can be found in the B plus tree’s leaf node.
- A leaf node can only have n record pointers and n key values.
- Every B+ Tree leaf node has a block pointer P that points to the next leaf node.
Searching Records in B+ Tree
Suppose that we need to find 55 in the B+ Tree structure below. We’ll start by fetching for the intermediary node, which will lead to the leaf node, which may have a record of 55.
So we’ll identify a branch between 50 to 75 nodes in the intermediary node. Then we’ll be redirected to the 3rd leaf node at the conclusion. In this case, the DBMS will use a sequential search to locate 55.
Insertion in B+ Tree
Suppose that we wish to add a record 60 to the structure below. After 55, it will reach the third leaf node. It’s a balanced tree, and one of its leaf nodes is already full; thus, we can’t put 60 in there.
We must split the leaf node in this scenario so that it may be added to the tree without impacting the fill factor, balance or order.
The values of the 3rd leaf node are (50, 55, 60, 65, 70), and the current root node is 50. To keep the tree’s equilibrium, we’ll divide the leaf node in half in the middle. As a result, (50, 55) & (60, 65, 70) can be grouped into two leaf nodes.
The intermediate node can’t branch from 50 if these two must be leaf nodes. It must have 60 added to it, and thereafter links to a new leaf node will be available.
When there is an overflow, we can enter an entry in this manner. In a typical scenario, finding the node in which it fits and then placing it in that leaf node is extremely simple.
Deletion in B+ Tree
Imagine that we want to remove 60 from the previous example. In this scenario, we must subtract 60 from both the intermediate node and the fourth leaf node. The tree will not satisfy the B plus tree rule if it is removed from the intermediate node. As a result, we must alter it in order to achieve a balanced tree.
It will look like the following after eliminating node 60 from the B+ Tree and rearranging the nodes:
Practice Problems on B+ Tree in Data Structure
1. What’s the max number of keys in a B+ Tree of height 3 and order 3?
a. 27
b. 3
c. 26
d. 80
Answer- (c) 26
2. Which of these data structures would be preferred in DB-system implementation?
a. B Tree
b. AVL Tree
c. Splay Tree
d. B+ Tree
Answer- (d) B+ Tree
3. In the case of a B+ Tree, both the leaves and the internal nodes consist of keys.
a. False
b. True
Answer- (a) False
4. What would be the min number of keys in the leaves in case any B+ Tree would contain a max of 7 pointers in the node?
a. 7
b. 3
c. 6
d. 4
Answer- (b) 3
Keep learning and stay tuned to get the latest updates on the GATE Exam along with Eligibility Criteria, GATE Syllabus for CSE (Computer Science Engineering), GATE CSE Notes, GATE CSE Question Paper, and more.
Also Explore,
Comments