B-Trees and B+ Trees for External Storage

When managing massive datasets that don't fit in your computer's main memory, like those in databases and file systems, every disk read becomes a costly bottleneck. Standard binary search trees fall short here, as their height grows with the number of keys, leading to many disk accesses. B-trees and their variant, B+ trees, are multi-way search trees specifically engineered to minimize these costly disk reads by storing many keys per node and keeping the tree broad and shallow. Understanding their design is fundamental to grasping how modern database indexing works at a system level.

The Core Motivation: Minimizing Disk I/O

The primary design goal for B-trees and B+ trees is to optimize for systems that use external storage (like hard drives or SSDs). Accessing data on a disk is orders of magnitude slower than accessing data in RAM. Therefore, the key performance metric is the number of disk blocks that must be read or written.

A B-tree achieves this by increasing the branching factor (the number of children a node can have). Each node in a B-tree is designed to hold as many keys and pointers as can fit into a single disk block. By packing hundreds or thousands of keys into a single node, the tree's height remains extremely low even for billions of records. A search, insertion, or deletion then requires traversing only a handful of nodes—each corresponding to one disk access. This contrasts sharply with a binary tree, whose height would be logarithmic to the number of keys, resulting in dozens of disk reads for large datasets.

B-Tree Structure and Properties

A B-tree of order $m$ is defined by a set of structural rules that maintain its efficiency. Think of $m$ as the maximum number of children a node can have. The key properties are:

• Node Capacity: Every node (except the root) must have at least $ceil(m/2)-1$ keys and at most $m-1$ keys.
• Balanced Growth: All leaf nodes must reside at the same depth, guaranteeing that every search path from root to leaf is of identical length.
• Internal Structure: A non-leaf node with $k$ keys has exactly $k+1$ children. The keys serve as separators, guiding searches down the correct subtree.

For example, in an order 5 B-tree ($m=5$), a node can hold between 2 and 4 keys (and thus have 3 to 5 children). The tree remains perfectly balanced because growth happens from the root downward only when necessary. The search algorithm is a natural generalization of a binary search: you examine the keys within a node (often using a linear or binary search) to determine which child pointer to follow next.

The B+ Tree: Optimizing for Range Queries

While B-trees are excellent for point lookups, B+ trees introduce two critical modifications that make them the dominant structure for database indexing.

First, in a B+ tree, all actual data records (or pointers to records) are stored only in the leaf nodes. The internal nodes contain only key values and child pointers. These internal keys act solely as signposts to direct traffic to the correct leaf. This separation means internal nodes can hold more signposts (keys), leading to an even higher branching factor and a shallower tree.

Second, and most importantly, all leaf nodes are linked together in a singly-linked list (or sometimes a doubly-linked list). This simple addition transforms the efficiency of range queries. A query like "find all employees with salaries between $50,000and$80,000" would work as follows: a standard search finds the first key ($50k) in a leaf node, and then the sequential link pointers are followed from leaf to leaf to retrieve all subsequent records without needing to traverse back up the tree. This is dramatically faster than the disjointed access pattern a standard B-tree would require.

Implementing Insertion and Deletion

The algorithms for maintaining a B/B+ tree after insertions and deletions are what keep the tree balanced and efficient. They are designed to work from the leaf upward.

Insertion always occurs in a leaf node. You find the appropriate leaf and insert the new key in sorted order. If the leaf now exceeds its maximum capacity (has $m$ keys), it must be split. Splitting involves taking the median key of the overflowing node, promoting it to the parent, and creating two new sibling nodes with the remaining keys. This split may cascade upward if the parent node also overflows, potentially increasing the tree's height if the root splits.

Deletion also starts at a leaf. After removing the key, if the leaf node falls below the minimum key threshold (fewer than $ceil(m/2)-1$ keys), the tree must be rebalanced. The first strategy is typically redistribution: borrowing a key from an adjacent sibling if that sibling has keys to spare. If redistribution isn't possible, the next step is merging: combining the underflowing node with an adjacent sibling and pulling a separator key down from the parent. This merge may cause the parent to underflow, triggering further merges that can cascade up and potentially decrease the tree's height.

Common Pitfalls

1. Confusing B-Tree Order: A common mistake is misinterpreting the order $m$. Remember, for a B-tree of order $m$, the maximum number of children is $m$. Therefore, the maximum number of keys in a node is $m-1$. Always verify the minimum key rule ($ceil(m/2)-1$) from this definition.
2. Misplacing Data in B+ Trees: When drawing or implementing a B+ tree, it's easy to accidentally place data pointers in internal nodes. Recall that in a pure B+ tree, internal nodes contain only keys for navigation. The actual data resides exclusively in the linked leaf nodes.
3. Overlooking the Leaf Link in Range Queries: When analyzing the performance of a range query, failing to account for the sequential leaf linkage in a B+ tree leads to an incorrect cost analysis. The major advantage is that after the initial search, the rest of the scan requires minimal navigation overhead, as it simply follows the linked list at the leaf level.
4. Incorrect Split/Merge Logic during Deletion: The rebalancing process after deletion has a specific order: check for redistribution (borrowing) first, and only merge if borrowing is impossible. Performing a merge when a redistribution is possible results in a valid but sub-optimal tree with fewer nodes than necessary, reducing the branching factor.

Summary

• B-trees and B+ trees are multi-way search trees designed to minimize expensive disk I/O by storing many keys per node, keeping the tree shallow and broad.
• The core innovation is high branching factor, where a single node corresponds to one disk block, making the number of disk accesses for an operation proportional to the tree's height.
• B+ trees enhance the standard B-tree by storing data only in linked leaf nodes. This allows for extremely efficient range queries via sequential scanning of the leaf level, making them the standard for database indexes.
• The algorithms for insertion (with splitting) and deletion (with redistribution and merging) work from the leaves upward to maintain the tree's balanced properties automatically.
• These structures are not theoretical curiosities; they are the fundamental indexing workhorses in virtually all relational database management systems (like PostgreSQL, MySQL) and many file systems (like NTFS, HFS+, and others), enabling fast data retrieval on massive scales.