b-trees – Software Online Review

Open almost any relational database’s query planner output and “index” almost always means a B-tree or, more precisely, a B+-tree. That’s not naming coincidence — a structure invented in 1972 for IBM mainframe disks still outperforms most alternatives at the specific job a database index does: keeping billions of sorted keys on block-based storage while answering point lookups and range scans in a handful of I/O operations. This piece is a mechanical deep dive into how B-trees and B+-trees work — node layout, splits, merges, and a worked insertion example — not a storage-engine comparison. For the engine-level trade-off against log-structured merge trees, see our separate LSM Trees vs B-Trees article; this one stays inside the B-tree itself.

At a Glance

Aspect	Detail
What it solves	Keeping sorted keys balanced and searchable on block storage, minimizing I/O per lookup
Core idea	A self-balancing n-ary search tree whose node size matches the storage page size
Search / insert / delete	O(log_b n), b in the hundreds — 3-4 reads even for billions of rows
Range scans	O(log n) to find the start, then O(k) across linked leaf nodes
Where it’s used	MySQL InnoDB clustered/secondary indexes, PostgreSQL’s default index type, SQLite, SQL Server, most filesystems
Dominant variant	B+-tree — records live only in linked leaf nodes; internal nodes hold routing keys only

Verdict: the B+-tree is the default on-disk index because it bounds tree height to a handful of levels regardless of table size, handles point and range queries from one structure, and keeps actual data in leaves where sequential access is cheap. It isn’t the best fit for extremely write-heavy workloads, where LSM-trees take over, but for read-heavy and mixed workloads it remains the default for good reason.

The Problem: Searching Sorted Data on Slow Storage

A balanced binary search tree gives O(log₂ n) search, but on disk each pointer hop can mean a separate I/O. A binary tree over a billion rows is roughly 30 levels deep — 30 potential random reads for one lookup. B-trees, proposed by Rudolf Bayer and Edward McCreight in 1972, optimize for I/O instead of comparisons: a node holds as many keys and children as fit in one storage page (4-16KB), so each level descended costs exactly one page read, and a branching factor in the hundreds reaches a billion rows in about four levels.

Node Structure and Branching Factor

A B-tree of order m keeps a small set of invariants: every node holds up to m-1 sorted keys; an internal node with k keys has k+1 children; every node except the root stays at least half full (⌈m/2⌉-1 keys), preventing the tree from going sparse and tall; and all leaves sit at the same depth — balance enforced structurally, not by a rebalancing pass like AVL trees use. The order is chosen so one full node fits one page: at 16KB per page and ~20 bytes per key-pointer pair, a node holds 500-800 entries. That choice — size the node to the page — is why B-trees beat binary trees here: tree depth becomes disk reads, and page-sized nodes keep that number tiny.

Insertion and Splitting: A Worked Example

Insertion descends from the root, comparing the new key at each node to pick a child, until it reaches a leaf, then inserts the key in sorted order. If the leaf has room, nothing else changes. If it’s full, it splits, and the split can propagate upward.

Take a one-node, order-4 tree (max 3 keys) that is currently just a full root:

root: [10, 20, 30]   (full)

Insert 25. The root overflows to [10, 20, 25, 30]. The split procedure: find the median (25), send everything left of it to a new left node ([10, 20]) and everything right to a new right node ([30]), then move the median key up into a parent — creating a brand-new root, since none existed:

        root: [25]
       /         \
 [10, 20]        [30]

The key mechanical insight: a B-tree never grows taller directly. It splits a full node, promotes one key, and only adds a new level when the root itself overflows. Growth happens uniformly from the root down, which is why every leaf always ends up at the same depth. A non-root overflow triggers the identical split one level up, and the promoted key can itself overflow its parent, cascading — rarely — all the way to a new root, but never leaving the tree unbalanced partway through.

Deletion and Merging

Deletion mirrors insertion. Removing a leaf key is trivial if the leaf stays at least half full. If a deletion drops a node below the minimum, the tree first tries to borrow from a sibling that has a key to spare, moving it over through the parent. If no sibling can spare one, it merges the underflowing node with a sibling and pulls the parent’s separating key down into the merge — removing a key from the parent, which can itself underflow and propagate upward, the mirror of a split cascading during insertion. If a merge empties the root, the merged child becomes the new root and the tree shrinks by a level. This symmetry is why B-trees never need an explicit rebalance pass.

Why B+-Trees, Not Plain B-Trees, Run Your Database

A classic B-tree lets any node — internal or leaf — hold a key paired with record data. Databases almost universally use the B+-tree variant instead, with two changes:

Data lives only in leaves. Internal nodes store routing keys only, no record data, so more keys fit per page (shallower tree) and every search walks all the way to a leaf — uniform-cost lookups instead of sometimes stopping early.
Leaves are linked via sibling pointers, so once a range scan finds its starting leaf it just walks sideways instead of re-traversing the tree. That’s an O(log n) descent plus an O(k) linear walk for k results — the mechanism behind cheap BETWEEN and ORDER BY scans.

Both changes target disk-backed indexes specifically: data scattered through internal nodes makes range scans awkward and bloats node size without improving fan-out, while a B+-tree trades a theoretical early-stop for simpler correctness, smaller internal nodes, and cheap ordered iteration — the single most common database access pattern.

How Real Databases Build On This

MySQL InnoDB uses B-tree structures for every index, with one twist for the primary key: InnoDB designates one index as the clustered index (the primary key, or the first NOT NULL UNIQUE index, or a hidden auto-generated row ID), and that index’s leaf pages store the complete row, not a pointer to it. Every other index is a secondary index whose leaf entries hold the indexed column(s) plus a copy of the primary key, so a secondary-index lookup typically costs a second traversal into the clustered index. InnoDB’s default page size is 16KB; ordinary inserts deliberately leave about 1/16 of each page free to absorb future writes (bulk index builds use innodb_fill_factor instead), and InnoDB attempts to merge an underfilled page once its fill drops below MERGE_THRESHOLD (50% by default).

PostgreSQL clusters differently: its B-tree is the default index type, but — unlike InnoDB — the index normally isn’t where row data lives. A leaf page holds pointers (TIDs) into a separate heap table; Postgres doesn’t keep the table physically reordered by the index the way InnoDB does (an explicit, one-time CLUSTER command exists, but writes don’t maintain that order automatically afterward). Per its own source documentation, PostgreSQL’s B-tree access method is “a correct implementation of Lehman and Yao’s high-concurrency B-tree management algorithm,” letting searches and inserts proceed without tree-wide locks; more than 99% of a typical index’s pages are leaves, and since PostgreSQL 13 the engine deduplicates repeated keys by default to shrink indexes on low-cardinality columns.

B+-Tree vs. the Naive Alternatives

Structure	Point lookup	Range scan	Insert/delete	Disk-friendliness
Unsorted heap file	O(n)	O(n)	O(1) append / O(n) delete	Great for writes, terrible for reads
Sorted array	O(log n) compares, O(n) to shift	O(log n + k)	O(n) per insert/delete	Poor — inserts rewrite large regions
Balanced BST (AVL/red-black)	O(log₂ n)	O(log₂ n + k)	O(log₂ n)	Poor — tens of levels, each a potential page fetch
B+-tree	O(log_b n), b in the hundreds	O(log_b n + k) via linked leaves	O(log_b n)	Excellent — node size matches page size

Trade-offs

Pros: shallow, predictable depth at any scale; native support for both point and ordered range queries; self-balancing with no separate rebalance step; decades of production hardening.
Cons: random-order inserts cause splits and leave pages partially empty, bloating the index (why fill-factor/merge-threshold tuning exists); in-place page updates make writes costlier than an LSM-tree’s sequential, buffered writes; internal nodes in a B+-tree duplicate keys that also live in leaves.

When to Use This

Use a B+-tree index — in practice, just your database’s default index type — whenever a workload needs ordered range queries, equality lookups, or sorted iteration, and reads are at least as frequent as writes: primary keys, foreign keys, anything in a frequent WHERE, ORDER BY, or BETWEEN clause. If writes dominate at very high volume (time-series ingestion, event logging), an LSM-tree engine usually fits better — see the LSM Trees vs B-Trees comparison. For in-memory ordered structures with simpler concurrent insert/delete logic, compare against skip lists.

Bottom Line

The B+-tree earns its place as the default relational index because one design decision — sizing nodes to match storage pages — directly minimizes I/O, the actually expensive resource. Keeping data in linked leaf nodes turns both point lookups and range scans into a handful of predictable reads no matter how large the table grows. That mix of guaranteed shallow depth, self-balancing writes, and cheap ordered iteration is why its core mechanics have barely changed in over fifty years.

FAQ

Is a B+-tree the same as a B-tree?
No. A B+-tree keeps all record data (or row pointers) in linked leaf nodes and routing-only keys in internal nodes; a plain B-tree can store data in internal nodes and has no leaf-linking requirement. Almost every index you’ll encounter is technically a B+-tree, even when documentation just says “B-tree.”

Why does InnoDB’s clustered index matter for performance?
The primary-key tree’s leaves contain the full row, so a primary-key lookup resolves in one traversal. A secondary-index lookup resolves the indexed columns first, then needs a second traversal into the clustered index via the stored primary-key value — why a short primary key keeps secondary indexes smaller and cheaper.

Do B+-trees ever need maintenance?
They self-balance on every write, but random-order writes can leave pages partially full. InnoDB (fill factor, merge threshold) and PostgreSQL (fillfactor parameter, REINDEX) both expose tuning to reclaim that wasted space.

Why not just use a hash index for equality lookups?
A hash index can beat a B+-tree on pure equality lookups, but hashing destroys key order, so it can’t support range scans or prefix matching — a large share of real queries. That’s why B+-tree is the default and hash indexes are a specialized option (PostgreSQL offers a native hash index type; InnoDB uses hashing only internally, as an adaptive cache in front of its B-trees).

Tag: b-trees

B-Trees and B+ Trees Explained: The Index Structure Behind Every Relational Database