B-Trees and B+ Trees

If you've ever queried a massive SQL database and gotten a result back in milliseconds, you have B-Trees to thank. They are the unsung heroes of data storage, quietly keeping the digital world organized since the 1970s.

To understand why they exist, you have to understand the most painful bottleneck in computer science: Disk I/O.

Think of your computer's RAM (memory) like the desk right in front of you. You can grab anything on it instantly. Think of your hard drive (disk) like a storage warehouse down the street. If you need something from the warehouse, you have to get in your car, drive there, find the box, and bring it back. It is excruciatingly slow compared to your desk.

When databases search for a record, their primary goal is to make as few trips to that warehouse (disk reads) as possible.

The Problem with Binary Search Trees

You might remember Binary Search Trees (BSTs) from computer science class. Each node has a maximum of two children. If you have a million records, a perfectly balanced BST will be about 20 levels deep.

If that tree is stored on a disk, traversing it from root to leaf to find a record means making 20 separate disk reads. That’s 20 trips to the warehouse. For a database, that’s incredibly inefficient.

Enter the B-Tree: Short and Wide

The B-Tree (Balanced Tree) was invented to solve this exact problem.

Instead of being tall and skinny like a binary tree, a B-Tree is short and wide. It achieves this by allowing a single node to hold many keys and have many children (often hundreds).

When reading from a disk, operating systems don't just read a single byte. They read chunks of data called "blocks" or "pages" (usually 4KB or 8KB). A B-Tree is designed so that a single node fits perfectly inside one of these disk pages.

When you make one trip to the warehouse (one disk read), you don't just bring back one number. You bring back an entire node containing hundreds of numbers. Because the tree fans out so widely, even a database with billions of rows might only be 3 or 4 levels deep.

Finding any record out of a billion takes just 3 or 4 disk reads. Magic.

The Upgrade: B+ Trees

While B-Trees were great, modern relational databases (like PostgreSQL and MySQL's InnoDB engine) almost universally use an upgraded version called the B+ Tree.

Here's the thing about a standard B-Tree: the actual data (the row content) is stored inside the nodes alongside the keys. This means the nodes get bulky, and you can fit fewer keys per page, which increases the height of the tree.

A B+ Tree makes two crucial changes:

1. Data is ONLY stored in the leaf nodes. The internal nodes (the branches) only store the keys acting as traffic cops to guide the search. Because internal nodes are just keys and pointers, they are tiny. You can fit thousands of them in a single disk page, creating a massive fan-out and keeping the tree incredibly flat.
2. Leaf nodes are linked together. The bottom layer of leaves forms a doubly-linked list.

Why is the Linked List a Game Changer?

Imagine running a query like: SELECT * FROM users WHERE age BETWEEN 20 AND 30;

In a normal B-Tree, to find all those ages, the database would have to repeatedly traverse up and down the tree branches to find 20, then 21, then 22, etc.

In a B+ Tree, the database traverses down the tree exactly once to find the number 20. Once it hits the leaf node for 20, it just follows the linked list horizontally across the bottom of the tree, reading adjacent pages sequentially until it hits 30.

Sequential disk reads are incredibly fast compared to random hopping. This makes B+ Trees heavily optimized for range queries, which are overwhelmingly common in real-world applications.

Real-World Examples

• MySQL (InnoDB): The default storage engine for MySQL uses B+ Trees for its primary clustered indexes. When you create a primary key, you are literally constructing a B+ Tree on disk.
• PostgreSQL: Uses B-Trees (technically B-link trees, a variant similar to B+ trees) as its default index type.
• File Systems: Operating systems use B-Tree variants (like NTFS on Windows or APFS on Mac) to keep track of where files are physically located on your hard drive.

Summary

• Disk I/O is slow, so databases need structures that minimize the number of reads.
• B-Trees solve this by being short and wide, packing many keys into a single node that matches the size of a disk page.
• B+ Trees are the industry standard for relational databases. They store actual data only in the leaf nodes, keeping the tree flat and fast.
• Linked Leaves: B+ Trees link their leaf nodes together, making range queries (like BETWEEN X AND Y) blazingly fast through sequential scanning.