B Tree

Definition

A B Tree is a balanced multiway search tree in which each node can contain multiple keys and multiple children, and all leaf nodes remain at the same level. The tree maintains strict rules about the minimum and maximum number of keys and children in each node so that it stays balanced after insertions and deletions.

In a B Tree of order m:

A node can have at most m children.
A node can have at most m - 1 keys.
Every non-root internal node has at least ceil(m/2) children.
All leaves appear at the same depth.

This balanced structure ensures fast searching, insertion, and deletion with logarithmic time complexity.

Main Content

1. First Concept

Structure of a B Tree

A B Tree node stores multiple sorted keys instead of just one key, and each node can have multiple child pointers.
The keys inside a node divide the data into ranges, so each child subtree contains values within a specific interval.

For example, if a node contains keys 20, 40, then:

left child contains values < 20
middle child contains values between 20 and 40
right child contains values > 40

A simple B Tree node may look like this:

            [20 | 40]
           /    |    \
      (<20)  (20-40)  (>40)

Because each node holds many keys, the tree stays shallow. This is one of the biggest differences from a binary search tree, where each node holds only one key and at most two children.

Key Characteristics of Structure

Nodes are arranged in sorted order.
Internal nodes guide the search path.
Leaf nodes contain actual data or references to data, depending on implementation.
All leaf nodes are at the same depth, which guarantees balance.

This structure makes B Trees extremely efficient for systems where reading from secondary storage is expensive, because fewer levels mean fewer disk reads.

2. Second Concept

Properties and Rules of B Tree

Every node can contain a limited range of keys, depending on the order of the tree.
The number of children is always one more than the number of keys in an internal node.
The root node is allowed to have fewer keys than other nodes, especially when the tree is small.
All leaves remain on the same level, which ensures the tree never becomes skewed.

For a B Tree of order m:

Maximum children = m
Maximum keys = m - 1
Minimum children for non-root internal node = ceil(m/2)
Minimum keys for non-root node = ceil(m/2) - 1

Example of Node Capacity

In a B Tree of order 4:

A node can have at most 4 children.
A node can have at most 3 keys.
A non-root node must have at least 2 children and at least 1 key.

Why These Rules Matter

They keep the tree balanced after updates.
They prevent nodes from becoming too empty or too full.
They reduce the height of the tree, improving performance.

These properties are what distinguish a B Tree from other trees. The balancing is not left to chance; it is maintained by strict structural constraints after every insertion and deletion.

3. Third Concept

Operations in B Tree

Search

: Begin at the root and compare the target key with the keys in the current node to choose the correct child path.

Insertion and deletion

: These operations may cause node overflow or underflow, so the tree may need to split, borrow, or merge nodes.

Searching

Search works similarly to searching in a sorted list inside each node:

Compare the target key with the keys in the node.
If the key matches, the search is successful.
Otherwise, move to the appropriate child subtree.
Repeat until the key is found or a leaf is reached.

Because each node contains many keys, search paths are short.

Insertion

When inserting a key:

Place it in the correct leaf node in sorted order.
If the node overflows, split it into two nodes.
Promote the middle key to the parent.
If the parent overflows, splitting may continue upward.

Deletion

When deleting a key:

Remove the key from the node.
If the node has too few keys afterward, fix it by borrowing a key from a sibling or merging with a sibling.
If the root becomes empty, the height of the tree may decrease.

Example of Split During Insertion

Suppose a node has:

[10 | 20 | 30]

If 25 is inserted, the node becomes too large. It may split into:

[10 | 20]   25   [30]

Then the middle key is moved upward depending on the tree structure.

This split-and-promote behavior is central to B Tree maintenance.

Working / Process

1. Start from the root and follow the correct path

To search or insert, compare the key with node keys from left to right.
Choose the child subtree whose range contains the target key.
Continue until the correct leaf or position is reached.

2. Insert or delete the key in the appropriate node

For insertion, place the key in sorted order in the leaf node.
For deletion, remove the key from its node.
If no rule is violated, the process ends immediately.

3. Restore balance if needed

If a node has too many keys, split it and move a middle key to the parent.
If a node has too few keys after deletion, borrow from a sibling or merge nodes.
If the root is affected, the height of the tree may increase or decrease.

A small insertion example:

Insert 25 into:

        [20 | 40]
       /    |    \
    [10]  [30]  [50]

25 goes to the middle child:

        [20 | 40]
       /    |    \
    [10] [25 | 30] [50]

If a node overflows, the tree performs splitting to preserve balance.

Advantages / Applications

Very fast searching in large datasets

because the tree height is small and each node contains multiple keys.

Excellent for disk-based storage

since each node can hold many keys, reducing the number of disk reads and writes.

Widely used in databases and file systems

where efficient indexing and large-scale data management are required.

B Trees are especially useful when data does not fit entirely in memory. Instead of requiring many pointer hops like binary trees, B Trees reduce access costs by grouping many keys into one node. That is why they are a standard choice for database indexing, record retrieval, directory organization, and storage engines.

Common applications include:

Database indexing
File systems
Storage engines
Large-scale search and retrieval systems

Summary

B Tree is a balanced multiway search tree used for efficient storage and retrieval of large data.
It keeps all leaf nodes at the same level and maintains balance through splitting, borrowing, and merging.
It is mainly used in databases and file systems because it reduces disk access and supports fast operations.
Important terms to remember: root node, leaf node, key, child pointer, order, splitting, merging, borrowing, balance