B+ Tree
Introduction
A B+ Tree is an advanced self-balancing multi-way search tree in which all actual data records are stored only in the leaf nodes, while internal nodes contain only indexing keys. The leaf nodes are connected using linked pointers, making sequential access extremely fast.
B+ Trees are extensively used in modern database management systems and file systems because they provide efficient searching, insertion, deletion and range queries.
B+ Tree Structure
Figure 1 : Structure of a B+ Tree
Why B+ Tree?
Although B-Trees provide efficient searching, data records may exist in both internal and leaf nodes. In a B+ Tree, all records are stored only in the leaf nodes, which simplifies searching and makes sequential traversal significantly faster.
| B-Tree | B+ Tree |
|---|---|
| Data stored in all nodes. | Data stored only in leaf nodes. |
| Leaf nodes are independent. | Leaf nodes are linked. |
| Range searching is slower. | Range searching is very efficient. |
| Less suitable for sequential access. | Ideal for sequential access. |
Properties of B+ Tree
| Property | Description |
|---|---|
| Balanced Tree | All leaf nodes remain at the same level. |
| Internal Nodes | Contain only index keys. |
| Leaf Nodes | Store all actual records. |
| Linked Leaves | Leaf nodes are connected using pointers. |
| Efficient Range Queries | Sequential traversal becomes very fast. |
Illustration of Leaf Node Linking
Figure 2 : Linked Leaf Nodes
Solved Example
Construct a B+ Tree of Order 4 by inserting the following keys:
Initially, all keys are inserted into the leaf node. Whenever a leaf becomes full, it is split into two leaf nodes and the separating key is copied to the parent node. Unlike a B-Tree, the promoted key remains available in the leaf node because all records are stored only at the leaf level.
Searching Example
Suppose the key 17 is to be searched.
- Start from the root node.
- Compare the key with index values.
- Move to the correct child node.
- Reach the appropriate leaf node.
- Retrieve the required record.
Working Principle
- Internal nodes store only search keys.
- Leaf nodes contain complete records.
- All leaves are connected using pointers.
- Overflow causes node splitting.
- The tree always remains balanced.
- Searching follows index nodes before reaching leaf nodes.
B+ Tree Algorithm
Insert(Key)
Step 1 : Search the appropriate leaf node.
Step 2 : Insert the key into the leaf node in sorted order.
Step 3 : If the leaf node has space,
Stop.
Step 4 : If the leaf node overflows,
Split the leaf node into two nodes.
Step 5 : Copy the middle key to the parent node.
Step 6 : If the parent overflows,
Split the parent node.
Step 7 : Continue until the tree becomes balanced.
Step 8 : If the root splits,
Create a new root.
Searching in a B+ Tree
Searching begins from the root node. Internal nodes contain only index keys, which help in selecting the correct child node. The search continues until the appropriate leaf node is reached, where the actual record is stored.
Range Query Example
Suppose we need to retrieve all records having keys between 12 and 27.
- Locate key 12 in the corresponding leaf node.
- Follow the linked leaf nodes sequentially.
- Retrieve all keys until key 27 is reached.
- No need to traverse the tree again.
This is why B+ Trees are highly efficient for range queries.
Figure 3 : Sequential Range Query using Linked Leaf Nodes
Complexity Analysis
| Operation | Time Complexity | Explanation |
|---|---|---|
| Searching | O(log n) | Tree height remains balanced. |
| Insertion | O(log n) | May require node splitting. |
| Deletion | O(log n) | May require node merging or borrowing. |
| Range Search | O(log n + k) | k is the number of records returned. |
| Space Complexity | O(n) | Stores keys, records and pointers. |
Advantages of B+ Tree
- Very efficient searching for large datasets.
- Excellent performance for range queries.
- Leaf nodes are linked together.
- Reduces disk I/O operations.
- Maintains a balanced tree automatically.
- Widely used in modern database systems.
Limitations of B+ Tree
- Implementation is more complex than Binary Search Tree.
- Requires additional memory for leaf pointers.
- Node splitting and merging increase implementation complexity.
- Not suitable for very small datasets.
Applications of B+ Tree
| Application | Description |
|---|---|
| Database Indexing | Oracle, MySQL, SQL Server and PostgreSQL. |
| File Systems | NTFS, FAT32, ext4 and XFS. |
| Cloud Storage | Efficient storage and retrieval of huge datasets. |
| Search Engines | Indexing millions of web pages. |
| Data Warehousing | Fast range searching on large databases. |
B+ Tree vs B-Tree
| B+ Tree | B-Tree |
|---|---|
| Records stored only in leaf nodes. | Records stored in all nodes. |
| Leaf nodes are linked. | Leaf nodes are not linked. |
| Better range searching. | Moderate range searching. |
| More suitable for databases. | Suitable for indexing. |
| Sequential access is very fast. | Sequential access is comparatively slower. |
Summary
A B+ Tree is a balanced multi-way search tree in which internal nodes contain only index keys while all actual records are stored in linked leaf nodes. This structure enables efficient searching, insertion, deletion and extremely fast range queries. Due to its excellent performance and reduced disk I/O, the B+ Tree is the most widely used indexing structure in modern database management systems and file systems.