2026-01-048 min read

Deletion on B-tree (Data Structures & Algorithms)

Learn Deletion on B-tree (Data Structures & Algorithms) step by step with clear examples and exercises.

Why This Matters

B-trees are essential data structures for managing large amounts of data efficiently, particularly in databases and file systems. They offer fast search, insert, and delete operations with a minimum number of disk accesses, which is crucial when dealing with data on disk. Understanding deletion from a B-tree can help you optimize database queries or improve file system performance.

Prerequisites

To follow this lesson, you should have a good understanding of:

Basic Python programming concepts (variables, functions, loops, etc.)
Data structures and algorithms (arrays, linked lists, stacks, queues, trees)
Binary search trees (BSTs) and their properties
Recursion in Python
Understanding of key-value pairs and how they are stored in a tree structure

Core Concept

A B-tree is a multiway tree data structure that allows for efficient search, insert, and delete operations with a minimum number of disk accesses. It's particularly useful in managing large amounts of data on disk because it reduces the number of disk reads and writes required to perform these operations.

B-trees have the following properties:

Each node can have up to m keys and m+1 pointers (children).
The root node must have at least t_min keys, where t_min is a minimum tree order.
All internal nodes (except the root) have t_min-1 keys, and all leaves have the same depth.
Each key in a node points to its corresponding subtree's lowest key.
If a node has fewer than t_min-1 keys, it is called underflow, and if it has more than 2*t_min-1 keys, it is called overflow.

In this lesson, we'll focus on deleting a key from a B-tree with the following properties:

m = 7 (maximum number of keys per node)
t_min = 3 (minimum tree order)

Insertion in a B-tree

Before we dive into deletion, let's briefly review how to insert a key into a B-tree. When inserting a new key, follow these steps:

Find the correct node for the new key using binary search.
If the node is not full (has fewer than m keys), insert the new key and exit.
If the node is full, split it into two nodes by moving the middle key to the parent node and creating a new child node with the remaining keys from the original node.
Repeat steps 1-3 for the parent node if necessary until reaching the root or finding an empty space.

Overflow Handling in B-tree

When a node becomes full during insertion, it splits into two nodes, and one key moves up to the parent node. This can cause overflow in the parent node if it already has 2*t_min-1 keys. To handle this, we can:

Split the parent node if necessary, moving the middle key to the grandparent node and creating a new child node with the remaining keys from the original parent node.
Continue splitting nodes up the tree until reaching an empty space or the root.
If the root becomes full during this process, create a new root node containing the middle keys from the original root and its children.

Deletion in a B-tree

Now let's focus on deleting a key from a B-tree:

Find the node containing the key to be deleted using binary search.
If the node is a leaf, remove the key and exit if the node has at least t_min-1 keys. If not, merge it with its sibling if possible (if both nodes have fewer than m/2 keys).
If the node is an internal node with fewer than t_min-1 keys, merge it with its sibling if possible (if both nodes have more than m/2 keys left after removing the key).
If merging is not possible, find the next available slot in the parent node and move a key down to fill it. If the parent node becomes underflow (has fewer than t_min-1 keys), merge it with one of its children if possible.
Continue moving keys up the tree until reaching the root or finding an empty space.
If the root becomes underflow during this process, create a new root node containing the middle keys from the original root and its children.

Underflow Handling in B-tree

When a node becomes underflow during deletion, it may need to be merged with one of its siblings or its parent's child. To handle this:

Merge the underflow node with its sibling if both nodes have more than m/2 keys (if possible).
If merging is not possible, borrow a key from the parent node if it has more than t_min-1 keys.
If the parent node becomes full during this process, split it as described in the overflow handling section.
Continue moving keys down the tree until reaching the leaves or finding an empty space.

Worked Example

Let's delete the key 25 from a B-tree with the following structure:

Find the node containing the key to be deleted (25):

def find_node(root, key):
current = root
while current:
if key == current.key:
return current
elif key < current.key:
current = current.left
else:
current = current.right
return None

The node containing the key is found:

node_to_delete = find_node(root, 25)
if not node_to_delete:
print("Key not found.")
else:

... (continue with deletion)


3. Delete the key from the leaf node:

def delete_from_leaf(node, key):

if node.key == key:

if node.right:

node.key = min(node.right.key)

delete_from_right(node.right, node.key)

else:

node.key = None

elif key < node.key:

if not node.left:

print("Key not found.")

else:

node.key = min(node.left.key)

delete_from_left(node.left, node.key)

else:

if not node.right:

print("Key not found.")

else:

node.key = max(node.right.key)

delete_from_right(node.right, node.key)


4. Merge the leaf node with its sibling (if possible):

def merge_leaves(left, right):

merged = Node(min(left.key, right.key))

merged.left = left if len(left.keys) > len(right.keys) else right

merged.right = left if len(left.keys) < len(right.keys) else right

for key in left.keys + right.keys:

if key != merged.key:

merged.add_key(key)

return merged


5. Continue moving keys up the tree and handling underflow/overflow as necessary.

Common Mistakes

Forgetting to handle overflow and underflow during insertion and deletion.
Failing to split or merge nodes correctly when necessary.
Not maintaining the B-tree properties (number of keys per node, minimum tree order) throughout the operations.
Using an inefficient implementation for binary search or recursive functions.
Forgetting to update parent pointers during node splits and merges.
Implementing incorrect logic for finding the next available slot in a parent node when merging nodes.
Failing to check if a node can be merged with its sibling before attempting to merge with a child of the parent.
Not properly handling the case where the root becomes underflow during deletion and creating a new root node.
Implementing an inefficient algorithm for finding the minimum or maximum key in a node.

Practice Questions

Implement the B-tree insertion function.
Implement the B-tree deletion function, including handling overflow and underflow.
Write a function to find the height of a B-tree.
Implement a B-tree search function.
Given a list of keys, create a B-tree with those keys using the given tree order.
Given a B-tree, write a function to print its contents in sorted order.
Write a function to find the number of disk accesses required for searching in a B-tree with a given number of keys and tree order.
Implement a function to split a node when it becomes full during insertion.
Implement a function to merge two nodes when one becomes underflow during deletion.
Write a function to find the next available slot in a parent node for merging leaves or handling underflow.

FAQ

What is the minimum number of disk accesses required for searching in a B-tree?

O(log n)

How does a B-tree reduce the number of disk accesses during search, insert, and delete operations compared to a binary search tree (BST)?

By storing multiple keys in each node, B-trees can reduce the number of disk accesses required for traversing deeper levels of the tree.

What is the minimum number of keys a B-tree node must have?

The root node must have at least t_min keys, and all other internal nodes must have at least t_min-1 keys. Leaf nodes do not have a minimum key count.

Can a B-tree have an odd number of keys per node?

Yes, a B-tree can have an odd number of keys per node as long as it maintains the other properties (e.g., t_min and maximum number of keys).

How does a B-tree handle deletion when the key to be deleted is not found in the tree?

If the key to be deleted is not found, no action is taken, and the function returns an error or message indicating that the key was not found.

What are some common applications of B-trees?

B-trees are used extensively in databases, file systems, and other data management systems to efficiently store large amounts of data on disk. They are also used in various software libraries for implementing efficient search, insert, and delete operations.