B+ Tree in DBMS | B+ Tree in Data Structure

 

 B+ Tree

A B+ Tree is a self-balancing multi-way search tree 

  • All leaf nodes are present at the same level.
  • Actual data records are stored only in the leaf nodes.
  • Internal nodes contain only search keys.

It is mainly used for efficient searching and sequential access. B+ Tree supports efficient range queries.


Structure of B+ Tree
Consider a B+ Tree node containing keys and children:

Number of Keys

Number of Children

1

2

2

3

3

4
In general,
Number of children = Number of keys + 1

The leaf nodes are connected sequentially using links(Linked List).


Rules of B+ Tree
For a B+ Tree of order m:

At most:
  • A node can have at most m children.
  • A node can contain at most m − 1 keys.
At least:
  • An internal node must have at least [m/2] children.
  • An internal node must contain at least [m/2] − 1 keys.

Insertion in B+ Tree
The basic steps involved in insertion are:

  1. Find the appropriate leaf node for the new key.
  2. Insert the key in sorted order.
  3. If the leaf node does not overflow, insertion is complete.
  4. If overflow occurs, split the leaf node.
  5. Copy the middle key to the parent node.
  6. If the parent also overflows, split the internal node.
  7. Continue splitting towards the root if necessary.
Example– Insertion 
B+ Tree of Order 3 

Keys to be inserted: 10, 20, 5, 6, 12, 30, 7

For order 3:
  • Maximum children = 3
  • Maximum keys = 2
Step 1: Insert 10
[10]


Step 2: Insert 20
[10 | 20]


Step 3: Insert 5
The leaf becomes:
[5|10|20]
Since the node exceeds the maximum number of keys, it is split.
        [10]  (**Parent store-first value of right child**)
       /       \
   [5]      [10|20]


Step 4: Insert 6
       [10]
       /      \
[5|6]     [10|20]



Step 5: Insert 12
The right leaf becomes:[10|12|20]
        [10]
       /      \
[5|6]     [10|12|20]

Overflow occurs, so the leaf is split                                  
        [10 |12]
        /      |         \
 [5|6]   [10]   [12|20]



Step 6: Insert 30
          [10 |12]                          [10 |12|20](**overflow**)
        /     |       \                         /     |       \
 [5|6]  [10]   [12|20|30]      [5|6] [10]   [12|30]


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


Step 7: Insert 7
The left leaf becomes:[5|6|7] 
             [12]
        /             \
    [10]              [20]
     /    \              /      \ 
[5|6|7]  [10]   [12]    [20|30]
Overflow occurs(max=2), so the leaf is split.
                   [12]
              /             \
      [6|10]              [20]
     /    |    \              /      \ 
[5]  [6|7]  [10]   [12]    [20|30]


Step 7: Insert 17

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


Handwritten Notes- Download PDF
Video Explanation- Watch on YouTube

Comments

Post a Comment

Popular posts from this blog

Normalization in DBMS,(1NF,2NF,3NF,BCNF,4NF,5NF)

                      Normalization in DBMS Normalization divides a large table into smaller , logically related tables and connects them using appropriate keys. The main purpose of normalization is to reduce unnecessary duplication of data and prevent problems that may occur when data is inserted, updated, or deleted. 1. First Normal Form (1NF) A relation is said to be in First Normal Form (1NF) when every attribute contains a single, indivisible value . Conditions of   1 NF Each cell must contain only one value. Multiple values should not be stored in the same field. ·         Example Customer Items Purchased Gowsi Rice, Dal Tamil Soap ·   Here, the Items Purchased column contains more than one value for Gowsi . ·   Therefore, the table is not in 1 NF . Converting it into 1NF. ...
Read more

Hashing in Data Structure | Collision Resolution Techniques | Hashing in DBMS

  Hashing in DBMS Hashing is a technique used to map data elements (keys) to specific locations in a hash table using a hash function. It allows insertion and retrieval of data efficiently     Hash Function A hash function converts a key into a hash code (index) , which is used to store and retrieve the data from a hash table.                                 h(k)=k mod m Where: k → Key m → Hash table size h(k) → Hash index  Hash Table A hash table is a data structure that stores data in an array format . Each position in the table is called a bucket , and the position is accessed using the hash function. Example Consider Keys                   (k) = 11, 18, 20, 25, 29, 33 Hash table size (m) = 7 Hash function:    h(k)=k mod m                     ...
Read more