The Universal Blueprint:
Why Everything in Your Database is a B-Tree

It is a question every developer eventually asks, usually late at night, staring at a query plan they don’t fully understand.

You’ve just added an index to a table with 200 million rows. The query that took 8 seconds now returns in 3 milliseconds. You know that it works. But you’ve never been forced to ask why.

The honest answer goes deeper than most tutorials will take you. It begins not with code, but with physics: with the brutal, unavoidable gap between how fast your CPU thinks and how slowly your disk responds. And it ends with a single data structure, invented in 1970, that has proven so perfectly matched to the laws of hardware that no competitor has displaced it in over fifty years.

That structure is the B-tree. Understanding it (really understanding it) changes how you read query plans, how you choose indexes, and how you reason about why some queries are fast and others are slow regardless of how much hardware you throw at them.

The Latency Chasm Your Database Was Built to Cross

Before examining any data structure, you need to internalize one uncomfortable truth about the hardware your database runs on. Modern computing exists in a state of permanent, violent tension between two tiers of memory that operate at incompatible speeds.

Your CPU can reference its L1 cache in roughly 0.5 nanoseconds. Main RAM takes about 100 nanoseconds, already 200× slower, but still fast enough to feel instantaneous. Then the floor drops out entirely.

A random read from an SSD takes approximately 100,000 to 150,000 nanoseconds, a 1,000× penalty compared to RAM. And a traditional spinning hard disk, where a mechanical arm must physically seek to the right track and wait for the platter to rotate into position, can cost 10,000,000 nanoseconds, a full 10 milliseconds per access.

There is a second, equally important constraint: storage hardware doesn’t let you read one byte. It forces you to read an entire block, typically 4 KB or 8 KB at a time. This is true of both HDDs and SSDs. They differ in why (mechanical geometry vs. flash cell organization), but not in what. PostgreSQL and Oracle use 8 KB pages. InnoDB defaults to 16 KB pages (this is configurable; some workloads tune it up to 64 KB).

This constraint, at first glance a limitation, is actually the key insight that makes the B-tree work.

The Data Structures That Couldn’t Cross It

Before understanding why the B-tree won, it helps to understand what lost, and precisely why each alternative fails. Central to that understanding is a single concept called fan-out.

With fan-out defined, the failures of the alternatives become precise rather than vague.

In a naively stored BST, each node is likely to occupy a different page. Finding any single row on 1 billion rows could therefore require 30 separate page reads. On an HDD at 10 ms per seek, that is 300 milliseconds per lookup. No database engineer would accept this.

The root problem is fan-out: a BST has a fan-out of exactly 2. This forces the tree tall and thin, maximizing the number of page reads required per traversal. The B-tree’s entire design is a direct assault on this number.

Hash maps fail databases for three structural reasons. First, they provide no ordering. A hash map cannot answer WHERE price BETWEEN 10 AND 50 without scanning every bucket. Second, when the map grows beyond its allocated space, resizing requires rehashing and physically rewriting enormous amounts of data, a catastrophic I/O event. Third, they cannot support prefix queries like LIKE 'abc%' because the hash of 'abc' has no relationship to the hash of 'abcd'.

The contrast becomes stark when you lay the structures side by side:

What Makes a B-Tree a B-Tree

Rudolf Bayer and Edward McCreight invented the B-tree in 1970 at Boeing Research Labs. (What the “B” stands for has never been officially settled; balanced, broad, Boeing, and Bayer are all plausible candidates. Bayer himself declined to clarify.) The structure was designed from first principles around the constraints of disk-based storage. Its core insight was elegant: if the bottleneck is the number of page reads, build a tree so wide and so shallow that traversal requires only a handful of them.

The way it achieves this is by dramatically increasing fan-out. A BST node holds one key and two child pointers. A B-tree node, sized to fit a database page (8-16 KB), can hold hundreds or thousands of keys, giving it a fan-out in the hundreds or thousands. This is the single property that makes everything else work.

The structure of a B-tree node is straightforward. Each internal node stores up to m - 1 routing keys (where m is the node’s maximum number of children, called its order) and up to m child pointers. Leaf nodes store the actual data pointers (or the rows themselves, in a clustered index). The tree remains balanced at all times: every path from root to leaf is the same length.

The mathematical consequence of high fan-out is dramatic:

Where h is the tree height, f is the fan-out, and n is the number of rows. With a fan-out of 1,000:

• Height 1 → up to 1,000 rows
• Height 2 → up to 1,000,000 rows
• Height 3 → up to 1,000,000,000 rows

A B-tree on one billion rows requires at most 3-4 page reads to find any single row. Even if every page read hits cold storage on an SSD, the entire lookup completes in under a millisecond.

This is why the B-tree doesn’t just beat the BST. It renders the BST’s disk-based performance so catastrophically worse that the comparison is almost unfair. The BST requires 30 page reads for 1 billion rows. The B-tree requires 3.

The B+ Tree: The Variant That Actually Runs Your Database

The structure described above is the classic B-tree. What PostgreSQL, InnoDB, Oracle, and SQL Server actually implement is a refinement called the B+ tree, and the differences matter in practice.

In a pure B-tree, internal nodes can hold data pointers alongside routing keys. In a B+ tree, this is prohibited: internal nodes hold routing keys only, and all actual data lives exclusively in the leaf nodes. The leaf nodes are then linked together in a doubly-linked list.

This separation produces two meaningful benefits. First, internal nodes become denser: without data pointers consuming space, each node fits more routing keys, which increases fan-out and further reduces tree height. Second, and more importantly, range queries become simple sequential scans.

Two Flavors of Index: Where the Row Actually Lives

Now that we understand the tree’s shape, it’s worth asking what exactly lives in its leaf nodes. That choice has significant consequences for query performance.

Not all B-tree indexes are equal. The distinction between clustered and secondary indexes is one of the most consequential architectural differences in relational databases, and it is still confused by many developers.

The escape hatch is a covering index: an index that includes all the columns the query needs in its leaf nodes, eliminating the second lookup entirely.

-- Secondary index on (email) can find the row's PK fast,
-- but SELECT * forces a second lookup into the clustered index
SELECT * FROM users WHERE email = 'alice@example.com';

-- With INDEX (email) INCLUDE (name, role), the leaf node
-- contains everything the query needs
SELECT email, name, role FROM users WHERE email = 'alice@example.com';

What Happens Inside the Tree on Every Write

Understanding how a B-tree responds to writes clarifies both its performance characteristics and its operational costs.

Insertion follows a straightforward path: descend to the correct leaf, write the key. If the leaf has room, the operation is done.

When a leaf is full, it splits: the median key is promoted up to the parent, the node divides into two, and both are written. If the parent is also full, it splits too, and the cascade propagates upward, potentially all the way to the root. When the root splits, a new root is created and the tree grows one level taller. In practice, this is rare: production trees have enough fan-out that root splits are infrequent.

Deletion is more nuanced. The mathematically correct behavior (merging under-full nodes after deletion) is often deliberately deferred or approximated in production engines. This is because merge-on-delete creates oscillation: a table near a merge threshold that alternates between inserts and deletes would trigger constant page merges and splits. Most engines instead allow pages to fall slightly below their theoretical minimum occupancy, accepting mild storage inefficiency in exchange for write stability.

The UUID problem deserves a dedicated note. When you use random UUIDs as primary keys, each new insert lands at a random position in the key space, forcing the engine to load a different leaf page from disk for nearly every write. This also means pages are constantly being split rather than filled sequentially. The practical consequence: UUID primary keys can measurably degrade write throughput on large InnoDB tables compared to sequential integer keys. Teams that need globally unique identifiers but care about write performance often reach for UUIDv7 (which embeds a timestamp prefix, making new IDs sort chronologically and therefore append to the rightmost leaf rather than scattering across the tree) or a surrogate integer key instead.

Page splits also have a longer-term consequence for reads. Over time, after many splits, the logical ordering of leaf pages in the linked list may no longer match their physical ordering on disk. What was designed to be sequential I/O for a range scan can degrade into random I/O as the physical layout diverges from the logical one. This fragmentation is real and accumulates silently. It is precisely why database maintenance operations like PostgreSQL’s VACUUM, MySQL’s OPTIMIZE TABLE, and manual index rebuilds exist: they restore physical page order, turning degraded random I/O back into the sequential I/O the B-tree was designed to produce.

What This Means for the SQL You Write Every Day

The B-tree’s geometry has direct, practical consequences for query performance, consequences you can exploit once you understand the structure. And you can observe these consequences directly in your database’s query planner output.

When PostgreSQL or MySQL evaluates a query, it chooses between execution strategies like Seq Scan (read every page in the table; MySQL: type: ALL), Index Scan (descend the B-tree, fetch full rows; MySQL: type: ref), and Index Only Scan (return data directly from leaf nodes without touching the heap; MySQL: Using index). These aren’t arbitrary labels: they map exactly to the B-tree operations described above. An Index Only Scan is the planner telling you a covering index is being used. An Index Scan means a double lookup is happening. A Seq Scan on a table with a relevant index often means the query touches enough rows that the planner judges a full table scan cheaper than thousands of individual B-tree descents.

Understanding the tree makes these plan choices legible rather than mysterious.

Range queries are cheap because of sorted leaf ordering. A query like WHERE created_at BETWEEN '2025-01-01' AND '2025-01-31' descends the tree in $O(\log n)$ to find the starting leaf, then follows the linked list forward until the range is exhausted. The I/O is sequential, which is the best-case access pattern for any storage medium.

SELECT *
FROM transactions
WHERE transaction_date BETWEEN '2025-01-01' AND '2025-01-31'
ORDER BY transaction_date ASC;

Prefix queries are cheap because of sorted key ordering. WHERE name LIKE 'Smith%' can use a B-tree index on name because 'Smith...' corresponds to a contiguous range in the sorted key space. WHERE name LIKE '%Smith' cannot, since a trailing wildcard has no range interpretation in a sorted structure, and the planner will fall back to a sequential scan.

ORDER BY can be free when it matches an index. If the B-tree index on created_at already returns rows in sorted order, and your query orders by created_at, the optimizer can satisfy the sort by reading the index’s leaves in order, with no additional sorting step required. This is one of the most commonly overlooked performance benefits of well-chosen index key ordering.

Composite index column order is not arbitrary. An index on (status, created_at) is sorted first by status, then by created_at within each status value. This means it can efficiently serve a query filtering on status alone, or one filtering on both status AND created_at. It cannot efficiently serve a query filtering on created_at alone: without a status filter to anchor the search, the engine would need to scan the entire index to find matching dates scattered across different status partitions.

-- This does NOT use an index on (status, created_at)
-- No leading column filter to anchor the B-tree descent
SELECT * FROM orders WHERE created_at > '2025-01-01';

-- This DOES use the (status, created_at) index efficiently
SELECT * FROM orders WHERE status = 'pending' AND created_at > '2025-01-01';

The rule is: a composite index is only usable for a prefix of its defined columns. Think of it as the tree’s first-level sort order: if you don’t filter on that first column, you have no anchor point in the tree, and the advantage of sorted storage evaporates.