B-Tree Operations in Details | Traversal, Search, Insertion, Deletion

A B-Tree is a self-balancing, multi-way search tree designed to store data in sorted order while supporting fast search, insertion, and deletion operations. Unlike a traditional Binary Search Tree (BST), where each node holds only one key and two children, a B-Tree node can contain multiple keys and multiple child pointers.

This structure reduces the tree’s height and minimizes the number of disk accesses, making B-Trees ideal for large datasets, databases, and file systems where efficient data retrieval is critical.

Basic operations in B-Tree are

1. Search
2. Insertion
3. Deletion
4. Traversal
5. Splitting and Merging

1. Searching in a B-Tree

Searching in a B-Tree works like searching in a Binary Search Tree (BST), but instead of checking one key per node, we compare the target value with multiple keys within a single node. This makes searching faster and more efficient in large datasets because it reduces the number of levels in the tree.

Step-by-Step Process for Searching in a B-Tree

1. Start at the Root Node:
   The search always begins at the root of the B-Tree.
2. Compare the Target Key with the Node’s Keys:
   Each node in a B-Tree contains several keys (arranged in sorted order).
   • If the key matches one of them → the search is successful.
   • If the key is smaller than a key → move to the left child of that key.
   • If the key is larger than all keys in the node → move to the rightmost child.
3. Move Down the Tree:
   Repeat the same comparison process in the next node until:
   • The key is found, or
   • You reach a leaf node (which means the key does not exist).

Example

Consider a B-Tree of order 3:

        [10 | 20]
        /    |     \
   [5]  [12 | 15]  [25 | 30]

Let’s search for key = 15

1. Start at root [10 | 20]
   • 15 is between 10 and 20, so we go to the middle child.
2. Visit the middle node [12 | 15]
   • We find 15 in this node.
   • Key found successfully.

Time Complexity of Searching in a B-Tree

2. Insertion in a B-Tree

Insertion in a B-Tree is a structured process that ensures the tree remains balanced and sorted after each insertion. Unlike a Binary Search Tree (BST), where each node stores only one key, a B-Tree node can hold multiple keys, so inserting requires handling cases where a node becomes full and needs to be split.

Step-by-Step Process of B-Tree Insertion

1. Locate the Correct Leaf Node:
   First, perform a search to find the leaf node where the new key should go.
   • The key must be placed in the correct sorted position within the node.
   • This is similar to searching in a BST, but here you compare the key with multiple keys in each node.
2. Insert the Key in Sorted Order:
   • Insert the new key into the leaf node in such a way that all keys remain in increasing order.
   • If the node still has space (less than m–1 keys, where m is the tree’s order), the process ends here.
3. Check for Overflow (Full Node):
   • If the node now contains more than (m – 1) keys, it becomes overfull.
   • This means the node cannot hold any more keys and needs to be split.
4. Split the Node:
   • Find the middle key of the full node.
   • Move this middle key up to the parent node.
   • The remaining keys are split into two new nodes — left and right children.
5. Handle Parent Overflow:
   • If the parent node also becomes full after receiving the new key, repeat the split process.
   • This splitting may continue all the way up to the root.
   • If the root splits, a new root is created, and the tree height increases by one — keeping the B-Tree balanced.

Example of B Tree Insertion

B-Tree of Order = 3

Order (m) = 3
Maximum keys per node = m – 1 = 2
Maximum children per node = m = 3

Step 1: Start with [10]

[10]

Step 2: Insert 20

[10 | 20]

Step 3: Insert 5

[5 | 10 | 20]

Now the node has 3 keys (more than 2) → overflow!

Step 4: Split the Node

• Middle key = 10
• 10 moves up and becomes the new root.
• Left node: [5]
• Right node: [20]

Result:

       [10]
       /   \
   [5]     [20]

Step 5: Insert 6

• 6 < 10 → goes to left child [5].
• Insert in sorted order → [5 | 6].

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

Step 6: Insert 12

• 12 > 10 → goes to right child [20].
• Insert in sorted order → [12 | 20].

Final B-Tree Structure:

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

Why Splitting Is Important

Splitting is one of the most important steps in maintaining the structure and efficiency of a B-Tree. When a node becomes full (i.e., it contains the maximum number of allowed keys), inserting one more key would violate the B-Tree rules. To prevent this, the node is split into two smaller nodes, and the middle key is moved up to the parent node.

This splitting process ensures that:

• The tree never grows too tall or too unbalanced.
  Instead of forming long chains like in an unbalanced BST, the B-Tree grows wider, keeping all paths from the root to leaves roughly equal in length.
• All nodes stay within the allowed key limit.
  Each node always has between ⌈m/2⌉–1 and m–1 keys, which keeps the storage efficient.
• Searching, insertion, and deletion remain fast.
  Because the height of the tree stays logarithmic (O(log n)), even large datasets can be processed quickly.
• Balance is automatically maintained.
  Each split redistributes keys evenly between nodes, so no part of the tree becomes heavier or deeper than another.

Time Complexity of Insertion in a B-Tree:

3. Deletion in a B-Tree

Deletion in a B-Tree is more complicated than in a Binary Search Tree (BST) because every node can contain multiple keys, and removing a key may violate the minimum key requirement in a node. To maintain balance, the tree uses special operations like borrowing and merging after deletion.

Step-by-Step Process of Deletion in a B-Tree

Find the key to delete : Start from the root and locate the key using the normal B-Tree search method.

There are three primary cases for deletion in a B Tree

1. Case 1: Deleting from a Leaf Node:
   • If the leaf node contains more than the minimum keys, simply remove the key.
   • If it has the minimum number of keys, you must rebalance by borrowing from siblings or merging nodes.
2. Case 2: Deleting from an Internal Node:
   • Replace the key with its inorder predecessor (if the left child has enough keys) or inorder successor (if the right child has enough keys).
   • Recursively delete the predecessor or successor key.
   • If neither child has enough keys, merge the children and recursively delete the key.
3. Case 3: Handling Underflow:
   • If a child node has fewer than the minimum keys, try to borrow a key from an immediate left or right sibling through the parent.
   • If borrowing is not possible (siblings also have minimum keys), merge the child node with a sibling and move a key down from the parent.
   • If merging causes the parent to have fewer than minimum keys, apply the same process recursively upward.
   • If the root ends up with no keys, make the merged child the new root effectively decreasing the tree height.

Example of B-Tree Deletion

Initial Tree:

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

Delete key 6:

• 6 is found in the left child [5 | 6].
• Remove 6 → node becomes [5].
• The node still has the minimum required keys (1), so no borrowing or merging is needed.

Final Tree:

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

Time Complexity of Deletion in a B-Tree

4. Traversal in a B-Tree

Traversal in a B-Tree means visiting every key in the tree in a specific order. Since B-Trees store multiple keys in each node and can have many children, traversal is slightly more complex than in a simple Binary Search Tree.

The most common type of traversal used is Inorder Traversal, because it prints all the keys in sorted (increasing) order.

Steps for Inorder Traversal

For a node containing keys [K1, K2, ..., Kn] and children [C0, C1, ..., Cn], the inorder traversal works like this:

1. Traverse the first child (C0) — which contains all keys less than K1.
2. Visit K1 (the first key).
3. Traverse the second child (C1) — which contains keys between K1 and K2.
4. Visit K2, then traverse the next child (C2), and so on.
5. Continue this process recursively until all keys and children are visited.

This ensures that all keys are printed in ascending order.

Example:

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

Step-by-step Inorder traversal:

1. Start with the root [10].
2. Go to the left child [5] → print 5.
3. Come back to root and print 10.
4. Go to the right child [12 | 20] →
   • Visit first key 12,
   • Then visit next key 20.

Inorder Traversal Output:

5, 10, 12, 20

Time Complexity for Traversal in a B-Tree:

5. Splitting and Merging (Balancing Operations)

Splitting and merging are balancing operations that keep the B-Tree structured and efficient during insertion and deletion. They ensure that no node becomes too full or too empty and that the tree remains balanced at all times.

Splitting (During Insertion)

When it happens:
Splitting occurs when we try to insert a new key into a node that already contains the maximum number of keys (m – 1) for a B-Tree of order m.

How it works

1. Identify the middle key of the full node.
2. Create a new node to the right of the middle key.
3. Move the middle key up to the parent node.
4. Distribute the remaining keys — keys smaller than the middle stay in the left node, and keys larger go to the new right node.
5. If the parent node also becomes full due to the new key, repeat the splitting process up the tree.
6. If the root splits, a new root is created, increasing the height of the tree by one.

Example

Insert 15 into this B-Tree of order 3 (each node can hold max 2 keys):

[10 | 20]

Insert 15 → Node becomes [10 | 15 | 20] (overflow).

• Middle key = 15
• Split into [10] and [20], promote 15

Result:

     [15]
     /  \
 [10]   [20]

Effect: The tree remains balanced, and search/insertion operations still take O(log n) time.

Merging (During Deletion)

When it happens:
Merging occurs during deletion when a node ends up with fewer keys than the minimum required (⌈m/2⌉ – 1 keys).

How it works:

1. Check if the left or right sibling has extra keys (more than minimum).
2. If yes, borrow a key from the sibling — the parent key moves down, and the sibling’s key moves up.
3. If borrowing is not possible (both siblings have minimum keys), merge the node with one of its siblings.
4. The parent key between them moves down into the merged node.
5. If the parent now has too few keys, merging may continue upward.
6. If the root becomes empty, its only child becomes the new root, reducing the height by one.

Example:

Delete key 6 from:

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

After deleting 6 → [5] (still valid).
If instead we deleted 5 and 6, the left node becomes empty, so merging happens:

Result:

     [12 | 20]

Effect: Merging restores balance and keeps all leaves at the same level.

Why Splitting and Merging Are Important

• Maintain Balance:
  These operations ensure that the B-Tree remains balanced after every insertion or deletion, preventing uneven growth.
• Uniform Leaf Level:
  All leaf nodes stay at the same depth, which guarantees consistent and predictable search times.
• Efficient Performance:
  By keeping the tree balanced, they prevent it from becoming skewed or tall, ensuring that all operations — search, insertion, and deletion — continue to work in O(log n) time.

Time Complexity of Splitting and Merging

Conclusion

B-Trees are powerful and efficient data structures designed to store large amounts of sorted data while staying balanced. The main operations — search, insert, delete, and traversal, all work in O(log n) time because the tree maintains equal height across all leaves. Splitting and merging help the tree stay balanced automatically during insertion and deletion. This makes B-Trees ideal for databases, file systems, and indexing, where quick access to large data is needed with minimal disk reads.