B-Trees vs. B+ Trees: Why One Indexing Structure Minimizes Disk I/O for Database Queries

When the PostgreSQL Global Development Group released version 13 in September 2020, the database engine fundamentally altered how it handles duplicate index entries by introducing B-Tree deduplication. Rather than storing identical keys multiple times, the system began merging them into a single posting list. That optimization reduced the storage footprint of indexes, but it was built on top of a foundational data structure that dictates the performance of virtually every modern relational database: the B+ Tree.[3]

While modern database marketing often hypes "AI-driven query optimization" or "schema-less scalability," the actual capability minimizing disk input/output (I/O) in production systems like MySQL InnoDB, Oracle, and SQLite remains the B+ Tree. The distinction between the standard B-Tree and its B+ variant is not merely academic. It represents a specific engineering trade-off designed to solve the physical latency of reading data from a storage disk.[1]

To understand why the B+ Tree dominates, one must first look at the physical constraints of database storage. A naive approach to a database would simply pack records sequentially into a file. "However, there's no way to insert or update rows in the middle of the file without shifting and rewriting all the bytes after the new row," notes the engineering team at Fly.io.[4]

Instead, databases group rows together into fixed-size chunks called pages. A standard page size is 4KB, which aligns with the block size typically used by operating systems and file systems. Keeping everything aligned to this 4KB boundary reduces the number of page fetches required from the disk. Because disk I/O is the slowest operation in a database architecture, limiting page fetches yields a massive performance win.[4]

The standard B-Tree, invented by Rudolf Bayer and Edward McCreight in 1970, was designed to navigate these pages efficiently. "In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time," according to its encyclopedic definition.[2]

In a standard B-Tree, every node in the tree can store both the routing keys and the actual data records (or pointers to the data). If a query searches for a specific user ID, the database traverses the tree from the root node down through the internal nodes. If the target record happens to be stored in an internal node, the search terminates early, saving a disk read.[1]

However, storing data inside internal nodes creates a severe structural penalty. Because a 4KB page has limited space, filling it with bulky data records means fewer routing keys can fit into that same page. Fewer keys per node reduces the "branching factor" of the tree, forcing the tree to grow taller. A taller tree requires more vertical hops to reach the bottom, and every hop represents a separate disk I/O operation.

The B+ Tree solves this geometric bottleneck by strictly separating navigation from storage. In a B+ Tree, the internal nodes store only routing keys, while all the actual data records are pushed down to the leaf nodes at the very bottom of the structure.

By evicting data from the internal nodes, a B+ Tree can pack hundreds of routing keys into a single 4KB page. For example, if an interior page entry takes about 8 bytes to store a child primary key and its page number, a single 4KB interior page can hold roughly 500 entries.[4]

This high branching factor mathematically flattens the tree. A B+ Tree with a branching factor of 500 can index 125 million records in just three levels (500 x 500 x 500). Consequently, any record in a 125-million-row table can be retrieved with a maximum of three disk reads. In practice, the root and first-level internal nodes are often cached in RAM, meaning a lookup might require only a single physical disk read.[5]

The second major advantage of the B+ Tree is its handling of range queries. In a standard B-Tree, the data is scattered across multiple levels of the hierarchy. If a query requests all records between ID 100 and ID 500, the database must perform an in-order traversal, repeatedly climbing up and down the tree branches to find the sequential records.[1]

A B+ Tree eliminates this vertical traversal. Because all data resides at the leaf level, the leaf nodes are linked together in a doubly-linked list. Once the database navigates down to the leaf node containing ID 100, it simply walks horizontally across the linked list to read the subsequent records until it hits ID 500.

This horizontal scanning is highly optimized for sequential disk reads. The database can pre-fetch contiguous pages from the disk, dramatically accelerating operations like `SELECT * FROM users WHERE age > 21` or `ORDER BY timestamp DESC`.[1]

The architecture of PostgreSQL provides a clear example of this implementation. "PostgreSQL B-Tree indexes are multi-level tree structures, where each level of the tree can be used as a doubly-linked list of pages," the official documentation states. "Typically, over 99% of all pages are leaf pages."[3]

This structure allows PostgreSQL to handle complex queries efficiently. When a user executes a query with a `BETWEEN` or `IN` operator, the query planner relies on the B-Tree index to locate the starting boundary and then scans horizontally.[3]

PostgreSQL also enforces strict size limits to maintain the tree's efficiency. The database dictates that an index entry cannot exceed approximately one-third of a page. This ensures that even in the worst-case scenario, every internal node maintains a minimum branching factor of three, preventing the tree from degenerating into a linked list.[3]

The trade-off for the B+ Tree's read efficiency is a slight overhead during write operations. Because all data must reside in the leaf nodes, inserting a new record can cause a leaf page to overflow. When a page exceeds its 4KB capacity, the database must perform a "page split," dividing the records between two new pages and updating the parent node with the new routing key.

If the parent node is also full, the split cascades upwards recursively. In rare cases, this cascade reaches the root, forcing the root to split and adding a new level to the entire tree. Despite this write penalty, the overwhelming majority of database workloads are read-heavy, making the B+ Tree's read optimization the correct engineering compromise.

Modern database vendors frequently announce revolutionary new storage engines, but they rarely ship a complete replacement for this structure. The deduplication feature introduced in PostgreSQL 13, for example, was marketed as a major performance leap, but it specifically targets the leaf pages of the existing B+ Tree, merging duplicate keys to delay page splits rather than reinventing the wheel.[3]

The ubiquity of the B+ Tree underscores a fundamental reality of systems engineering: hardware constraints dictate software design. As long as reading from a storage disk remains orders of magnitude slower than reading from silicon memory, flattening the search space will remain the primary objective of database architecture. The next frontier for indexing engines is adapting these structures for Non-Volatile Memory Express (NVMe) drives, where the latency gap between RAM and storage is shrinking, potentially shifting the mathematical balance of the B+ Tree once again.[1]