B-Tree Index Overview
You'll learn what B-Tree indexes are, why databases rely on them, and how they differ from simpler tree structures.
What Is a B-Tree Index?
A B-Tree index is a self-balancing tree structure that databases use to organize and quickly locate data on disk. Unlike the binary search trees (BSTs) you might've seen in algorithms courses, B-Trees are designed specifically for systems that read and write large blocks of data to disk, not just RAM.
Think of a B-Tree like a multi-level index in a phone book. Each page (node) contains many names and pointers to other pages, not just one or two. This means you can skip huge sections of the book with just a few page turns, minimizing how many times you need to flip pages (disk reads).
Why Databases Use B-Trees
Disk I/O is thousands of times slower than memory access. A database query that reads from disk 100 times will be painfully slow. B-Trees minimize disk reads by:
- Storing many keys per node (often hundreds), matching the size of disk blocks
- Keeping the tree shallow, so you traverse fewer levels
- Staying balanced automatically, ensuring consistent performance even after many inserts and deletes
How They Differ from In-Memory BSTs
| Feature | In-Memory BST | B-Tree Index |
|---|---|---|
| Keys per node | 1 | Hundreds |
| Optimized for | RAM access | Disk I/O |
| Height | Often taller | Very shallow |
| Node size | Tiny | Matches disk block |
A BST might require 20 hops to find a record; a B-Tree might need only 3–4 disk reads for millions of records.
Key Takeaway: B-Tree indexes are disk-optimized structures that dramatically speed up database queries by minimizing expensive disk I/O operations through wide, shallow trees.