A B-Tree is a self-balancing, multiway search tree designed to store large amounts of sorted data efficiently. Unlike a binary search tree, where each node can have at most two children, a B-Tree node can contain multiple keys and multiple child references.
The main purpose of a B-Tree is to keep the tree height small while maintaining ordered data. This makes B-Trees particularly useful for systems that work with large datasets stored on secondary storage such as databases and file systems.
What Is a B-Tree?
A B-Tree is a balanced multiway search tree in which each node can contain multiple sorted keys. The keys divide the values stored in the child subtrees into ordered ranges.
For example, a node containing the keys 20 and 50 can
have three children. The first child contains values smaller than 20, the second
contains values between 20 and 50, and the third contains values greater than 50.
All leaf nodes in a B-Tree are located at the same depth. This property keeps the structure balanced and prevents the tree from becoming unnecessarily tall.
Why Were B-Trees Created?
Traditional binary search trees can require many node accesses when a dataset is large. This becomes particularly important when nodes are stored on disk or another form of secondary storage because retrieving data from storage is much more expensive than comparing values already loaded into memory.
B-Trees address this problem by storing multiple keys inside each node. A single storage access can therefore provide several keys and references, allowing the search to move through a large amount of data while visiting relatively few levels.
Structure of a B-Tree
A B-Tree node generally contains two important types of information:
- A collection of sorted keys.
- References to child nodes.
If a node contains k keys, it can have up to k + 1
children. The keys act as separators that determine which range of values belongs
to each child.
Example B-Tree Structure
[20 | 40]
/ | \
/ | \
[5 | 10] [25 | 30] [50 | 60]
In this example, the root contains two keys. The child nodes store values in the ranges determined by those keys. The leaf nodes are all at the same level, preserving the balanced nature of the B-Tree.
Properties of a B-Tree
A valid B-Tree follows several structural rules. The exact minimum and maximum number of keys depends on the chosen order or minimum degree.
- Each node can contain multiple keys.
- Keys within a node are stored in sorted order.
- A node with multiple keys can have multiple children.
- All leaf nodes are at the same depth.
- The tree remains balanced after insertions and deletions.
- Nodes have minimum and maximum capacity requirements.
- The root has special rules regarding its minimum number of keys.
B-Tree Order and Minimum Degree
B-Trees can be described using terms such as order and minimum degree. Different books and implementations sometimes use the word "order" differently, so it is important to check the definition being used.
When a B-Tree is defined using a minimum degree t, a non-root node
normally contains at least t - 1 keys and at most
2t - 1 keys. Such a node can have at most 2t children.
These capacity limits are important because they allow the tree to split full nodes and maintain balance as new values are inserted.
Searching in a B-Tree
B-Tree search is based on the same ordered-search principle used by binary search trees, but each node contains multiple keys. The search compares the target value against the keys in the current node and determines the appropriate child range.
- Start at the root node.
- Compare the target value with the keys in the node.
- If the value matches a key, the search succeeds.
- If the value is smaller or larger, determine the appropriate child range.
- Continue searching in that child.
- Stop when the value is found or the appropriate leaf position is reached.
Example Search
Suppose the root contains [20 | 40] and we search for
30. Because 30 is greater than 20 but smaller than 40, the search
moves into the middle child. The same comparison process continues until the value
is found or determined not to exist.
Inserting Elements into a B-Tree
B-Tree insertion adds a new key while preserving the ordering, capacity, and balance properties of the tree.
One of the most important operations during insertion is node splitting. When a node becomes full, it can be divided into two nodes. A middle key is promoted to the parent node, allowing the B-Tree to continue growing without violating its maximum node capacity.
Node Splitting
Consider a full node containing sorted keys. Instead of allowing the node to grow beyond its capacity, the middle key is promoted to the parent while the remaining keys are divided between two child nodes.
If the root itself becomes full, splitting the root can create a new root. This is one of the mechanisms that allows a B-Tree to increase in height while remaining balanced.
Deleting Elements from a B-Tree
B-Tree deletion is more complex than simple deletion from an ordinary binary search tree because removing a key must not cause a node to fall below its minimum capacity.
Depending on the situation, deletion can involve replacing a key with a value from a neighboring subtree, borrowing a key from a sibling, or merging nodes when the required minimum capacity cannot otherwise be maintained.
B-Tree Time Complexity
Because a B-Tree remains balanced and each node can have multiple children, its height grows logarithmically with the number of stored keys. Search, insertion, and deletion therefore have logarithmic asymptotic complexity under the standard comparison-based model.
| Operation | Typical Time Complexity |
|---|---|
| Search | O(log n) |
| Insertion | O(log n) |
| Deletion | O(log n) |
| Traversal | O(n) |
In practical storage systems, performance also depends on factors such as node size, memory hierarchy, storage latency, and how keys are searched within individual nodes. The major advantage of a B-Tree is its ability to reduce the number of levels and therefore the number of expensive storage accesses.
B-Tree vs Binary Search Tree
Both structures maintain ordered data, but they are designed with different characteristics in mind.
| Feature | B-Tree | Binary Search Tree |
|---|---|---|
| Keys per node | Multiple | Usually one |
| Maximum children | Multiple | Two |
| Balance | Maintained by the B-Tree rules | Depends on the implementation |
| Large storage datasets | Well suited | Usually less suitable |
B-Trees in Databases
B-Tree and B-Tree-family structures are closely associated with database indexing. A database index needs to locate records efficiently without scanning an entire table. A balanced tree structure allows the database engine to navigate through ordered index keys while keeping the number of levels relatively small.
Database systems may use specific variants or implementations of B-Tree-family indexes, so the exact internal representation depends on the database engine. The underlying principle remains the same: maintain ordered keys in a balanced structure that supports efficient lookup and range-oriented access.
B-Trees in File Systems and Storage
B-Tree-based structures are also useful in storage systems and file systems because their wide nodes can represent many keys while keeping the overall tree shallow. This characteristic is valuable when data must be retrieved from blocks or pages rather than directly from CPU memory.
Advantages of B-Trees
- Maintains balanced height.
- Supports efficient searching, insertion, and deletion.
- Stores multiple keys in each node.
- Reduces the number of tree levels.
- Works well with block-based storage systems.
- Supports ordered data and range-oriented access patterns.
Limitations of B-Trees
- Implementation is more complex than a basic binary search tree.
- Insertion requires handling node splits.
- Deletion may require borrowing or merging nodes.
- Maintaining node capacity adds implementation overhead.
- For small in-memory datasets, simpler data structures may be sufficient.
When Should You Use a B-Tree?
B-Trees are a strong choice when data must remain ordered and the application needs efficient access to large datasets, especially when the data structure interacts with secondary storage.
They are particularly relevant to database indexes, storage engines, and systems where reducing the number of page or block accesses is important.
B-Tree Example in JavaScript
The following example demonstrates the basic representation of a B-Tree node and the concept of searching through multiple sorted keys. A complete production implementation would additionally handle insertion, node splitting, deletion, merging, and persistence.
Key Takeaways
- A B-Tree is a balanced multiway search tree.
- Each node can contain multiple sorted keys.
- A node can have multiple children.
- All leaf nodes are maintained at the same depth.
- Node splitting is an important part of B-Tree insertion.
- Deletion can require borrowing or merging nodes.
- Search, insertion, and deletion have logarithmic asymptotic complexity.
- B-Trees are especially useful for large storage-oriented datasets and indexes.