B+ Trees vs. Binary Search Trees for Disk-Based Indexing

Introduction

In our last module, we explored how a database manages data on disk and in memory. We saw how critical the buffer pool is for minimizing slow disk I/O. However, even with a perfectly tuned buffer pool, if the database has to scan an entire multi-gigabyte table to find a single record, performance will be terrible. The question we ended with was: how can we find data without doing a full scan?

The answer is an index. Today, we begin our study of the most important indexing structure in the database world: the B+ Tree. Our learning outcome is to explain why B+ trees are preferred over binary search trees for disk-based indexing. We will dissect the performance characteristics of storage hardware, see why a classic data structure like a binary search tree is a poor fit, and understand how the B+ Tree is specifically designed to solve these problems.

1. The Core Problem: The High Cost of Disk I/O

Before we can compare data structures, we must first deeply understand the environment they operate in. For a disk-based database, the single greatest performance bottleneck is accessing data from storage. The time difference between accessing data in RAM versus on an SSD or HDD is staggering.

To get a concrete feel for this, let's watch a video that breaks down the mechanics and costs of disk operations.

As the video clearly demonstrates, every disk I/O operation is costly. The primary goal of a disk-based index is therefore to minimize the number of disk blocks we need to read to find our data.

2. Why Binary Search Trees (BSTs) Are a Bad Fit for Disk

Given your background in data structures, you know that a balanced binary search tree offers excellent O(log n) performance for search, insert, and delete operations. So, why don't we use them for database indexes?

The answer lies in the O(log n) complexity itself when applied to disk. The height of a balanced BST is approximately log₂(n). For 1 million records, this is about 20 (2²⁰ ≈ 1 million). If the tree is stored on disk, each level we traverse to find a record could require a separate disk read, as each node might reside in a different disk block. A single lookup could therefore trigger up to 20 disk I/Os.

This article provides a concise summary of this problem.

The fundamental issue is that BSTs are tall and skinny. They are designed for in-memory operations where pointer chasing is cheap. For disk, where each "pointer chase" to a new block is incredibly expensive, this design is disastrous.

3. The B-Tree Solution: Short and Wide Trees

If a tall tree is bad for disk I/O, the logical solution is to create a tree that is as short as possible. This is the core idea behind the B-Tree.

Instead of nodes with only two children, a B-Tree node can have hundreds or even thousands of children. This is called an m-way search tree. By making the nodes "wider," we dramatically reduce the height of the tree.

How wide? The key design insight is to make the size of a single tree node equal to the size of a disk page (e.g., 4KB, 8KB, or 16KB). When the database performs one disk read to fetch a node, it gets a large block containing many keys to evaluate.

The following video provides a brilliant comparison, continuing the 1-million-record example.

The result is a logarithmic complexity with a much larger base: O(logₘ n), where m is the "order" or fanout of the tree (the max number of children). Since m is large (e.g., >100), the height of the tree is extremely small. A B-Tree indexing billions of records might only be 4 or 5 levels deep. This means finding any record requires only 4-5 disk I/Os, a massive improvement over a BST.

4. The "Plus" Advantage: Why B+ Trees are Even Better

Most modern databases use a specific variant called a B+ Tree. It refines the B-Tree design with two key modifications that provide significant performance benefits.

1. Data Pointers Only in Leaf Nodes: In a standard B-Tree, keys and data pointers (or the data itself) can be stored in any node (internal or leaf). In a B+ Tree, the internal nodes store only keys, which act as "signposts" to guide the search. All actual data pointers are stored exclusively in the leaf nodes.
2. Linked Leaf Nodes: All leaf nodes in a B+ Tree are linked together, forming a doubly-linked list.

This image provides an excellent visual comparison of the two structures.

So, what are the advantages of the B+ Tree design?

• Higher Fanout (Even Shorter Trees): Because internal nodes only store keys and not bulky data values/pointers, they are much smaller. This allows more keys to fit into a single node (a single disk page). A higher number of keys per node means a higher fanout (m), which in turn leads to an even shorter tree and fewer I/Os for a lookup.
• Efficient Range Queries: This is a huge advantage. If you need to execute a query like SELECT * FROM employees WHERE age BETWEEN 30 AND 40, the process is simple. You traverse the tree once to find the first record (age 30), and then you just follow the linked list at the leaf level to scan all subsequent records in the range. In a standard B-Tree, you would have to traverse up and down the tree to find all the records in the range, which is much less efficient.

This brief video segment and article section summarize these advantages perfectly.

Conclusion

Today we established the fundamental principles behind disk-based indexing. We saw how the physical constraints of storage hardware dictate the design of efficient data structures.

Key Takeaways:

• The primary goal of a disk-based index is to minimize disk I/O operations, which are orders of magnitude slower than memory access.
• Binary Search Trees (BSTs) are a poor choice for disk because their tall, skinny structure leads to a high number of I/Os for a single lookup (tree height ≈ I/Os).
• B-Trees solve this by being short and wide. Their high fanout (many children per node) dramatically reduces tree height, corresponding to O(logₘ n) I/Os.
• B+ Trees are the preferred variant in modern databases because:
  • They store data pointers only in leaf nodes, allowing internal nodes to hold more keys, which increases fanout and further reduces tree height.
  • Their linked leaf nodes make range queries and full index scans extremely efficient.

Preview of the Next Lesson:

Now that we understand why B+ Trees are the right choice, our next step is to understand how they work dynamically. In the next lesson, we will get practical and learn how to implement insertion and deletion operations in a B+ tree, including handling the critical logic of node splits and merges.