DATABASE MANAGEMENT SYSTEM

B+ TREE IN DBMS 

A B+ tree is a type of self-balancing tree data structure that maintains sorted data and allows for efficient insertion, deletion, and search operations. It is widely used in databases and file systems due to its efficiency in handling large amounts of data.

Key Features of B+ Trees

1. Balanced Tree Structure: B+ trees are always balanced, meaning that all leaf nodes are at the same level. This ensures that the path from the root to any leaf is the same length, which provides consistent performance for operations.
2. Nodes:
   • Internal Nodes: Contain keys that act as guides to the leaf nodes. They do not store actual data values.
   • Leaf Nodes: Contain the actual data values or pointers to data records. They are linked together in a linked list to facilitate range queries.
3. Order (m): The order of a B+ tree refers to the maximum number of children a node can have. 
4. Properties:
   • Maximum pointer in an internal node=m
   • Minimum pointer in an internal node(p)=m/2
   • Maximum search keys=m-1[nodes get split when mth element comes]
   • Minimum search keys(q)=p-1[nodes get merged of count goes below q]

Operations on B+ Trees

1. Search:
   • Start at the root node and traverse down the tree.
   • At each internal node, use the keys to determine the correct child pointer to follow.
   • Continue until reaching a leaf node, then search through the leaf node to find the exact record.
2. Insertion:
   • Find the correct leaf node where the new key should be inserted.
   • Insert the key into the leaf node in sorted order.
   • If the leaf node overflows (i.e., it has more than m keys), split the leaf node into two nodes and propagate the split upwards. This may cause a cascade of splits up to the root if necessary.
3. Deletion:
   • Find the key to be deleted and remove it.
   • If the deletion causes a node to underflow (i.e., it has fewer than ⌈m/2⌉ keys), merge nodes or redistribute keys from sibling nodes to maintain the tree properties.
   • Adjust the tree structure upwards if necessary.

Advantages of B+ Trees in DBMS

1. Efficient Disk Access: B+ trees are designed to minimize disk I/O operations, which are the most time-consuming operations in database management. Nodes are designed to fit within a disk block, optimizing read and write operations.
2. Range Queries: The linked list of leaf nodes allows for efficient range queries and sequential access to records. This is particularly useful for database operations that involve scanning a range of values.
3. Balanced Structure: The balanced nature of B+ trees ensures that operations such as search, insertion, and deletion are performed in logarithmic time, making the tree efficient even for large datasets.
4. Concurrency: B+ trees support concurrent access, making them suitable for multi-user environments typical in databases.

 

Example : Insert elements 25,9,4,16,1,20,13,15,10,11,12,18 in B+ tree of Order 4.

 

• Maximum pointer in an internal node=4
• Minimum pointer in an internal node(n)=4/2=2
• Maximum search keys=4-1[nodes get split when 4th element comes]
• Minimum search keys=2-1=1[nodes get merged of count goes below 1]

 

Practice Question:

Example : Insert elements 1,2,3,4,5,6,7,8,9,10 in B+ tree of Order 4.