B-Tree Indexing

Introduction to B-Trees

Imagine a physical dictionary with 10,000 pages. If you want to find the word “Zebra,” you do not start at page 1 and read every single word until you reach the end. That would take days. Instead, you open the book to the middle (Page 5,000, “Monkey”). You know “Zebra” comes after “Monkey,” so you instantly ignore the entire first half of the book. You repeat this splitting process until you find the word in seconds.

This is exactly how a database index works.

If a database table has 1 billion rows of customers, and you run SELECT * FROM customers WHERE id = 9999, a database without an index must scan all 1 billion rows (Full Table Scan), which is incredibly slow. To solve this, relational databases (like PostgreSQL, MySQL, and Oracle) use a data structure called a B-Tree (Balanced Tree) to organize data for lightning-fast reads.

How the B-Tree Works

A B-Tree is a hierarchical, upside-down tree structure designed specifically to minimize the number of times the database has to interact with the slow, physical hard drive.

The Anatomy of the Tree

• Root Node: The very top of the tree. It contains a few broad ranges (e.g., [1 - 300,000] and [300,001 - 1,000,000]).
• Internal Nodes: The middle layers. They break the broad ranges into smaller, more specific ranges.
• Leaf Nodes: The absolute bottom of the tree. The Leaf Node contains the actual, physical location on the hard drive where the user’s data is stored.

The Search Process (Logarithmic Time)

If you search for id = 9999:

1. The database reads the Root Node (1 disk read). It sees that 9999 falls into the [1 - 300,000] bucket. It follows the pointer down the left side of the tree.
2. It reads the Internal Node (1 disk read). It sees 9999 falls into the [5,000 - 15,000] bucket. It follows the pointer down.
3. It hits the Leaf Node (1 disk read). The Leaf Node says, “Customer 9999 is located at Hard Drive Sector 42.”
4. The database fetches the data.

Instead of reading 1 billion rows, the database found the exact record with only 4 disk reads. This is mathematically known as $O(\log n)$ time complexity.

B-Tree vs. B+ Tree

Almost all modern databases actually use a variation called the B+ Tree. In a standard B-Tree, data can be stored in the Internal Nodes. In a B+ Tree, data is only stored at the absolute bottom (the Leaf Nodes). Furthermore, in a B+ Tree, every Leaf Node has a pointer linking it directly to the Leaf Node next to it. This makes Range Queries (SELECT * FROM customers WHERE id BETWEEN 10 AND 50) incredibly fast. The database finds id=10, and then simply slides sideways across the linked Leaf Nodes to grab the rest of the data, without having to traverse back up and down the tree.

The Write Penalty

B-Trees are heavily optimized for Read Speed. The penalty is Write Speed. The “B” stands for Balanced. The tree must always be perfectly symmetrical to guarantee fast searches. If you insert a million new records, the tree becomes unbalanced. The database must physically pause, break the tree apart, and rebuild (rebalance) the nodes on the hard drive. If a database is hit with a massive spike of incoming write traffic, this constant rebalancing will cause the database to lock up and crash.

Conclusion

The B-Tree is one of the most important data structures ever invented in computer science. By organizing data into a massive, self-balancing, hierarchical index, it allows relational databases to execute highly precise, instantaneous queries against datasets that are millions of times larger than the computer’s available memory.