Why B+ Trees Beat B Trees for High‑Performance Database Indexing

Row Storage and Column Storage

Row storage treats a table as a sequence of records, each stored consecutively on disk blocks. Updates are fast because a whole row often resides in a single block, but queries that scan many rows can be slow. Column storage groups values of the same column together, which greatly speeds up queries and aggregation because related data is stored contiguously.

Indexes

Indexes are auxiliary data structures that map a key (e.g., order ID) to a record location, enabling fast look‑ups such as select * from order where id=1000000. They are built by sorting the key column and storing pairs, without altering the original table data.

Binary Search Tree

A binary search tree (BST) stores keys in a hierarchical structure where the left subtree contains smaller keys and the right subtree larger keys. While BSTs reduce search complexity to O(log n), inserting a new key requires rebalancing and can be costly on disk because nodes are not stored contiguously.

B‑Tree

A B‑Tree generalizes the BST by allowing each node to contain multiple keys and child pointers, reducing tree height and the number of disk I/O operations. For example, a 3‑4 B‑Tree permits up to three keys and four children per node, making it suitable for large on‑disk indexes.

B+‑Tree

B+‑Tree refines the B‑Tree by storing actual data only in leaf nodes; internal nodes contain only keys for navigation. This design adds redundant index entries in internal nodes, which speeds up insertions, deletions, and range queries because leaf nodes are linked together in a sequential list.

Insertion Example

The article demonstrates inserting the sequence 3, 6, 9, 12, 19, 15, 26, 8, 30 into a 2‑3 B+‑Tree. Overflows cause node splits and promotion of middle keys to parent nodes, eventually resulting in a balanced tree where all leaves reside at the same depth.

Insertion and Deletion Efficiency

B+‑Trees have redundant internal nodes, allowing deletions to be performed directly on leaf nodes without touching the internal structure, resulting in faster delete operations. Insertions only affect a single path from root to leaf, and the tree remains balanced automatically.

Search and Range Queries

Both B‑Tree and B+‑Tree locate the appropriate leaf by traversing internal keys. B+‑Tree leaves are linked via a doubly‑linked list, enabling efficient range scans without additional tree traversal.

Conclusion

The article demonstrates how databases use file‑system‑like structures to build indexes. While B‑Trees work, B+‑Trees provide higher insert/delete performance, automatic balancing, and faster range queries, making them the preferred index structure for large‑scale relational databases.