Skip to content

B-Trees: The Data Structure Powering Every Database You've Ever Used

6 min read4 views[Backend]
Cover image for "B-Trees: The Data Structure Powering Every Database You've Ever Used"

The Data Structure Powering Every Database You've Ever Used

If you've ever run a query with a WHERE clause on a column that has an index, you've already benefited from a B-tree. You just didn't know it. PostgreSQL, MySQL, SQLite, most filesystems — they all rely on B-trees at their core. It's one of those data structures that quietly does enormous work without ever announcing itself.

So let's talk about what it actually is, why it was invented, and how it keeps your queries fast even when your table has 50 million rows.


The Problem It's Solving

Imagine you have a phone book. A million entries, sorted alphabetically. You want to find "Ramirez, Carlos."

You don't start from page one. You flip to roughly the middle, see you're in the M's, flip forward, narrow it down, find the R section, and from there it's a few more pages at most. That's essentially binary search — you're cutting the search space in half each time.

Now imagine the phone book is not a physical book but data stored on a hard drive or SSD. The problem is that reading from disk is orders of magnitude slower than reading from memory. Every time your database needs to "flip to a page," it's doing a disk read. If you have to do 30 of those for a single query, that's slow. Very slow.

Binary search trees are fast in terms of number of comparisons, but the standard binary search tree has a fatal flaw for disk-based storage: each node holds only one value and has two children. That means for a million records, you're looking at around 20 levels deep. Twenty disk reads, minimum.

B-trees were invented in 1970 by Rudolf Bayer and Edward McCreight to fix exactly this problem.


The Idea: Fat Nodes, Shallow Trees

The key insight of a B-tree is deceptively simple: instead of each node holding one value and two children, make each node hold many values and many children.

Think of it like this. With a regular binary tree, each "filing cabinet drawer" holds one folder and can point to two more drawers. With a B-tree, each drawer holds hundreds of folders, and can point to hundreds of other drawers.

The result? The tree gets much, much shorter. Instead of 20 levels for a million records, you might need only 3 or 4. That's 3 or 4 disk reads instead of 20. For a billion records, you're still looking at maybe 5 or 6 levels.

This is what makes B-trees so well-suited for databases. Each "node" in a B-tree maps nicely to one disk page (typically 4KB or 8KB). Loading a node from disk gives you hundreds of keys to work with at once, not just one.


How It's Structured

A B-tree has three types of nodes:

The root — the top of the tree. Every search starts here. It holds some keys and pointers to child nodes.

Internal nodes — the middle layers. They hold keys that act as dividers: "everything less than 42 goes left, everything between 42 and 87 goes middle, everything above 87 goes right." They don't hold the actual data, just the navigation information.

Leaf nodes — the bottom layer. This is where the actual data (or pointers to the actual data) lives. In most database implementations, the leaves are also linked together in a chain, so range queries ("give me all users with ID between 100 and 500") can scan leaves sequentially without going back up the tree.

The specific variant used by most databases is actually called a B+ tree, where only leaf nodes store data values. Internal nodes only hold keys for navigation. This is a small but important distinction — it means internal nodes can pack more keys per page (since they don't store heavy data), keeping the tree even shorter.


Staying Balanced

One of the best properties of a B-tree is that it's always balanced. Every path from the root to a leaf has the same length. Always.

This is not an accident — it's enforced by the insertion algorithm. When you insert a new value and a node gets too full (exceeds its capacity, called the "order" of the tree), the node splits in half. The middle key gets pushed up to the parent. If the parent is also full, it splits too, and this can bubble all the way up to the root.

If the root itself splits, a new root is created one level above. This is the only time a B-tree grows taller — from the top, not the bottom.

Deletions work similarly in reverse: if a node gets too empty after a deletion, it either borrows a key from a sibling or merges with a sibling, and again this can ripple upward.

The end result is that regardless of how many inserts and deletes you do, the tree stays balanced and the worst-case number of disk reads stays predictably low.


Why This Matters in Practice

When you create an index on a column in PostgreSQL, it builds a B+ tree over the values in that column. The leaf nodes store pairs of (column value, pointer to row). When you query with a WHERE id = 12345, PostgreSQL:

  1. Starts at the root of the B-tree index.
  2. Navigates down through internal nodes, following the right pointers based on comparisons.
  3. Hits a leaf node containing (12345, page 847, offset 23).
  4. Fetches that specific row from disk.

Total disk accesses: maybe 4. Without the index, it would scan every single row in the table — potentially millions of disk reads.

For range queries like WHERE created_at BETWEEN '2024-01-01' AND '2024-06-30', the database finds the starting leaf, then follows the leaf chain to the right until it's past the end date. The chain linking of leaves is what makes this efficient.


What B-Trees Aren't Good At

B-trees are optimized for exact lookups and range queries on ordered data. They're not the right tool for everything:

Equality-only lookups on high-cardinality data — hash indexes are faster here. A hash index does a single computation and jumps directly to the value. No tree traversal needed. PostgreSQL supports both.

Full-text search — searching for a word inside a document isn't a range query. That's what inverted indexes (like in Elasticsearch or PostgreSQL's tsvector) are for.

Write-heavy workloads with lots of random inserts — splits and rebalancing cause write amplification. This is why some storage engines (like RocksDB, used by Cassandra and CockroachDB) use a different structure called an LSM-tree (Log-Structured Merge-tree) instead. LSM-trees batch writes and sort them later, trading write performance now for compaction overhead later.


The Takeaway

B-trees are one of those inventions that turned a genuinely hard problem — fast access to large datasets on slow storage — into something elegant and practical. They've been around for over 50 years and are still the default index type in every major relational database.

When someone asks "why is my query slow after adding more data?" the answer is almost always about indexes and whether the database can use them. Understanding B-trees is how you understand why an index works, not just that it does.

It's the difference between using a tool and actually knowing what it's doing.

# Comments (0)

No comments yet. Be the first.

0/1000