B Tree in DBMS

            

  B Tree

Handwritten Notes- Click Here

A B-Tree is a self-balancing multi-way search tree used for storing and managing sorted data.

Unlike a binary search tree, a B-Tree can have more than two children for a node.

The main features of a B-Tree are:
  • Keys are stored in sorted order.
  • All leaf nodes are maintained at the same level.
  • A node can contain multiple keys and pointers.
Structure of B-Tree
A B-Tree node mainly contains:
  1. Keys
  2. Pointers to child nodes
Important Rule
******If a node contains K keys, it can have K + 1 children.*****


For example:

             [ 10 | 20 ]                         → 2 keys
            /         |        \
          /            |          \
         [5]    [15]   [25 | 30]         →3 children

  • Keys = 10, 20 → 2 keys
  • Children = ([5],[15],[25|30])→3 children

B-Tree Order

The order of a B-Tree determines the maximum number of children that a node can have.
                                           order = m.

Maximum

Maximum children = m
Maximum keys = m − 1

Minimum

Minimum children = [m/2]
Minimum keys = [m/2] − 1

The root has a special condition:
 The root must contain at least one key.

Also, all leaf nodes must remain at the same level.


Example – B-Tree of Order( m = 3):

Property

Value

Maximum children   = m

3

Maximum keys          = m − 1

2

Minimum children    = [m/2]

2

Minimum keys            = [m/2] – 1

1


B-Tree Insertion
Insertion is performed by following these steps
  1. Find the appropriate leaf node.
  2. Insert the new key in sorted order.
  3. Check whether the node exceeds the maximum number of keys.
  4. If overflow occurs, split the node.
  5. Move the middle key to the parent.
  6. Continue the splitting process upward if required. 

Example of B-Tree Insertion -order 3.

                          Values 10, 20, 5, 6, 12, 30, 7, 17

For order 3:
Maximum keys = 2
Maximum children = 3

Step 1: Insert 10
[10]


Step 2: Insert 20
20 is greater than 10, so it is placed after 10.
[10 | 20]


Step 3: Insert 5
Insert 5 and arrange the keys in sorted order:
[5 | 10 | 20]

There are now 3 keys, but the maximum is 2.
Therefore, overflow occurs.

Split the node and promote the middle key 10.
          [10]
         /    \
      [5]    [20]


Step 4: Insert 6
Since:
6 < 10
6 is inserted into the left child.

          [10]
         /      \
   [5 | 6]    [20]


Step 5: Insert 12
Since:
12 > 10
12 goes to the right child.
          [10]
         /       \
 [5 | 6]    [12 | 20]

Step 6: Insert 30
Since:
30 > 10
30 is inserted into the right node.

              [10]
              /      \
      [5 | 6]      [12 | 20 | 30]

The right node contains 3 keys, causing overflow.
Split the node and promote the middle key 20.

             [10 | 20]
            /       |    \
      [5 | 6]   [12]  [30]

Step 7: Insert 7
Since:
7 < 10
7 is inserted into the leftmost node.

             [10 | 20]
            /       |      \
 [5 | 6 | 7]    [12]   [30]

The node has 3 keys, so overflow occurs.
The middle key 6 is promoted to the parent.

The parent becomes:
     [6 | 10 | 20]
   /          |      \
[5 | 7]  [12]   [30]

This also causes overflow because an order-3 B-Tree allows only 2 keys in a node.
Split the root and promote the middle key 10.

                [10]
               /     \
             [6]    [20]
            /  \        /   \
        [5] [7] [12] [30]

Step 8: Insert 17
Since:
17 > 10
17 < 20
17 is inserted into the node containing 12.
                          [10]
                    /                \
              [6]                   [20]
            /    \                 /            \
         [5]    [7]    [12 | 17]    [30]
The resulting B-Tree is balanced and all leaf nodes are at the same level.


B-Tree Deletion

Deletion is slightly more complex than insertion because deleting a key may cause a node to contain fewer keys than its minimum requirement.

  • Delete the key from the appropriate location.
  • Check whether underflow occurs.
  • If a sibling has an extra key, perform borrowing.
  • If borrowing is not possible, perform merging.
  • If the key belongs to an internal node, replace it with a suitable predecessor or successor and then delete that key from the leaf. 

Cases in B-Tree Deletion

  1. Deletion from a leaf with underflow
  2. Deletion from a leaf without underflow
  3. Deletion from an internal node using predecessor
  4. Deletion from an internal node using successor
  5. Deletion using sibling borrowing 

Case 1: Deletion from Leaf – Underflow

Delete 7.
Now underflow occurs because the leaf from which 7 was deleted becomes empty.
The sibling has only the minimum number of keys, so it cannot borrow.
The nodes/keys are merged

Consider

                [10]                                        [10]                                                
               /     \                                       /       \                                            
          [6]          [20]                         [6]       [20]                        
         /  \            /   \                       /                /   \                                             
    [5]   [7]  [12|17] [30]         [5]        [12|17] [30]                           
        


          [10]
        /         \
 [5 | 6]       [20]
                  /            \       
             [12|17]     [30]

Case 2: Deletion Without Violation
Delete 6.
  • The left node still contains the required minimum number of keys.
  • Therefore, no underflow occurs and no borrowing or merging is required

Consider

         [10]                                                [10]
         /         \                                         /         \   
 [5 | 6]       [20]                             [5 ]         [20]
                  /            \                                     /          \   
              [12|17]     [30]                       [12|17]     [30]  


Case 3: Deletion from Internal Node Using Predecessor(Left max)
Delete 10.
Suppose the key to be deleted is present in an internal node.
  • The predecessor is the largest key in the left subtree.
  • Replace 10 by its predecessor 7.Now delete the original 7 from the leaf node.
  • The leaf node now has no key, causing underflow. Since borrowing is not possible, the required nodes are merged.
Consider

              [10]                                            [7]                                       
          /          \                                       /          \                                 
     [6]            [20]                          [6]            [20]              
     /  \            /       \                         /  \            /       \                           
[5]   [7]  [12|17] [30]             [5]   [ ]  [12|17] [30]                   


           [7] 
      /          \  
 [5 | 6]       [20]
                 /            \  
              [12|17]     [30] 

Case 4: Deletion from Internal Node Using Successor(Smallest key in the right subtree)
Delete 10.
  • For 10, go to the right subtree and find the smallest key.Successor = 12
  • Replace 10 with 12.Delete the Original 12

Consider
                 [10]                                          [12]                        
             /          \                                    /          \
           [6]            [20]                   [6]            [20]
          /  \          /           \                 /  \          /        \
      [5]  [7]  [12|17]   [30]       [5]  [7]  [17]     [30]


Case 5: Deletion Using Sibling Borrowing 
Delete 30
  • After deletion, the rightmost node becomes empty, causing underflow.
  • The sibling contains an extra key, so borrowing is possible.
  • The parent key 20 moves down to the underflowed node, and the sibling's suitable key 17 moves up to the parent.
Consider
                [10]                              [10]                                                       
             /          \                              /          \                                                
           [6]            [20]              [6]            [20]                              
          /  \          /           \           /  \          /           \                      
   [5]  [7]  [12|17]   [30]    [5]  [7]  [12|17]     [ ]             


                    [10]   
                  /          \ 
              [6]            [17] 
              /  \          /        \   
           [5]  [7]   [12]   [ 20]

Video Explanation



Comments

Post a Comment

Popular posts from this blog

Queue ADT

Image
  Queue ADT Handwritten Notes- Click Here A  Queue  is a linear data structure in which elements are inserted at one end and removed from the other end.( Insertion → Rear,  Deletion → Front )                                   ↓ FRONT                                 ↓ REAR A B C D E    A queue follows the FIFO (First In, First Out) principle. This means that the element inserted first is removed first. A  Queue can be implemented using: Array Linked List Basic  Queue  Operations: 1. Enqueue - used to insert  a new element into the queue. 2. Dequeue - used to remove an element from the queue. 3. Peek - used to view the first element without removing it. 4. isEmpty - checks whether the queue contains any elements. 5...
Read more

Entity-Relationship(ER) Model

Image
Entity-Relationship(ER) Model Handwritten Notes - Click Here The Entity-Relationship (ER) Model is a conceptual data model. It helps database designers understand the requirements of a system before creating the actual database tables . It describes the important objects in a system, their properties , and the relationships between them. The three basic concepts of the ER model are Entity Attribute Relationship Entity An entity can be any real-world object, person, place, or class about which we want to store information in a database. In a traditional ER diagram, an entity is represented by a rectangle .                        Example: Employee and Department An employee works for a department. Here, Employee and Department are entities , and Works For is the relationship between them. Weak Entity A weak entity is an entity that depends on another entity for its identification of existence. A weak entity is represen...
Read more

Different types of Data Models in DBMS

Image
             Data Models Handwritten Notes- Click Here A Data Model defines how data is organized, stored, related, and accessed in a database. Types of Data Models in DBMS Hierarchical Data Model Network Data Model Relational Data Model Entity-Relationship (ER) Model Object-Oriented Data Model Object-Relational Data Model 1. Hierarchical Data Model   The Hierarchical Data Model organizes data in the form of a tree structure . Each child record has only one parent record . A parent record can have multiple child records . It mainly represents a one-to-many relationship . Data retrieval is very fast in the hierarchical model.                                   Company                   |            Department             /      ...
Read more