B-Tree Indexing: Under the Hood

From Slow Scans to Fast Searches

Imagine trying to find a name in a massive, unsorted phone book. You'd have to start at page one and read every entry until you found the one you were looking for. This is a sequential scan, and it's what a database is forced to do on a table without an index.

Now, imagine the phone book is sorted alphabetically. You can open it to the middle, see if you've gone too far or not far enough, and repeatedly halve the search space. This is a binary search. But what if we could do even better? What if the first page of the book was an index that told you "A-C starts on page 50, D-F on page 150," and so on? You could jump directly to the right section. This is the core idea behind a database index.

Why Not a Simple Binary Search Tree?

Given your computer science background, a binary search tree (BST) might seem like an obvious choice for an index. While BSTs are efficient for in-memory operations, they are a poor fit for data stored on disk.

Let's look at why.

The key issue is that each step down a level in a BST could require a separate disk I/O operation. Since disk access is thousands of times slower than memory access, and BSTs can get very deep, the number of I/Os quickly becomes a bottleneck.

We need a data structure that is "short and fat" rather than "tall and skinny" to minimize the number of disk reads. This is precisely what a B-tree provides.

Introducing the B+ Tree

Most modern databases, including PostgreSQL and MySQL, use a variant of the B-tree called a B+ tree. It is a self-balancing tree data structure that keeps data sorted and allows for efficient search, insertion, and deletion operations, all while minimizing disk I/O.

Let's begin with a video that builds the intuition for B+ trees from the ground up.

Now that you've seen why the simple approach fails, let's see how the B+ tree is designed to succeed. The core idea is to create nodes that are large enough to hold many keys and pointers, often sized to match a single disk page (e.g., 8KB or 16KB), which you learned about in the last lesson.

Key Differences: B-Tree vs. B+ Tree

The video uses the term B+ tree, and it's important to understand the specific characteristics that distinguish it from a classic B-tree.

The two most important rules for a B+ tree are:

1. Data is stored only in leaf nodes. Internal nodes contain only key values that act as "signposts" to guide the search. This allows internal nodes to be very dense, packing in many keys. A higher density means a higher branching factor (or "fanout"), which results in a shallower, wider tree. A shallower tree means fewer levels to traverse, and thus fewer disk I/Os.
2. Leaf nodes are linked together. This forms a sorted, doubly-linked list at the bottom level of the tree, which makes range queries (e.g., WHERE id BETWEEN 100 AND 500) extremely efficient.

B+ Tree Operations in Detail

Now let's see how this structure enables fast operations.

Lookup (Search)

A lookup operation traverses the tree from the root down to a leaf. At each internal node, the database performs a search (like a binary search) on the keys within that node to find which pointer to follow to the next level. This process repeats until a leaf node is reached. The total number of disk I/Os is equal to the height of the tree.

A B+ tree with a height of just 3 or 4 can index hundreds of millions of rows, meaning you can find any single row with only 3-4 disk reads instead of millions. This is the magic of B-tree indexes.

Range Scan

The linked list at the leaf level is what makes B+ trees shine for range scans.

Insertions, Deletions, and Balancing

To keep the tree efficient, it must remain balanced. B+ trees achieve this through two key mechanisms: page splits on insertion and page merges on deletion.

Let's dive deeper into the rebalancing logic.

• Insertion and Page Splits: When a new key is inserted, the database traverses to the correct leaf page. If there's space, the key is added. If the page is full, a split occurs:

  1. A new leaf page is allocated.
  2. About half of the keys from the full page are moved to the new page.
  3. A copy of the first key in the new page is "promoted" up to the parent internal node to act as a separator.
  4. If the parent node is also full, it splits too, and this process can continue all the way up to the root. The tree only grows taller when the root node itself splits.

• Deletion and Page Merges: When a key is deleted, it's removed from its leaf page. If this causes the page to become less than half full, the database may merge it with a sibling page to keep the tree compact and efficient. This is the reverse of a split. Note that some databases, like PostgreSQL, handle this lazily through a background VACUUM process rather than merging immediately on every deletion.

To see this in action, the following resource is invaluable.

B+ Trees in Real Database Systems

Finally, let's connect this theory to how databases like MySQL and PostgreSQL actually use B+ trees.

• MySQL (InnoDB): Clustered vs. Secondary Indexes
  The InnoDB storage engine uses a special type of B+ tree for the primary key called a clustered index. In a clustered index, the leaf nodes of the B+ tree are the table data; they contain the entire row. This means the table's physical data on disk is ordered according to the primary key.

  Any other index on the table (a secondary index) is a separate B+ tree whose leaf nodes contain the indexed column's value and the primary key of the corresponding row. Therefore, a query using a secondary index must first search the secondary index to find the primary key, and then use that primary key to search the clustered index to retrieve the full row. This is a crucial concept known as a "double lookup".

• PostgreSQL: Non-Clustered Indexes
  In PostgreSQL, all indexes are effectively secondary indexes. The table data is always stored in a separate heap file (as we learned in the last lesson). The B+ tree index's leaf nodes contain the indexed column's value and a direct pointer (called a CTID) to the row's physical location in the heap file. This means a lookup on any index requires only one index traversal followed by one heap fetch.

Conclusion

You now have a deep, practical understanding of how B+ tree indexes work. This is one of the most important data structures in all of software engineering, responsible for the performance of countless applications.

Key Takeaways:

• B-trees are "short and fat" trees designed to minimize slow disk I/O operations by aligning node size with disk page size.
• Databases typically use the B+ tree variant, where data is stored only in leaf nodes, and leaf nodes are linked together.
• Lookups are fast and predictable, requiring a number of disk reads equal to the tree's height (typically 3-4).
• Range scans are highly efficient due to the linked list structure of the leaf nodes.
• The tree stays balanced via page splits during insertions and page merges during deletions.
• Real-world databases like MySQL and PostgreSQL use B+ trees to implement both primary and secondary indexes, though the specifics of what's stored in the leaf nodes can differ (full row vs. primary key vs. CTID).

Preview of the Next Lesson:
B-trees are fantastic for a wide range of queries, especially those involving ranges. But are they always the best choice? In our next lesson, we will compare B-tree indexes with hash indexes and explain when each is appropriate, giving you another tool for your database optimization toolkit.