Finding the Needle in the Haystack
Imagine a phone book with 10 million entries, sorted randomly. To find "Smith, John," you'd have to read every single entry from the beginning. That's a full table scan — the database equivalent of reading every page in the book. For large tables, this is catastrophically slow.
An index is a separate data structure that the database maintains alongside the table. It stores a subset of the table's data (the indexed column values) in a way that allows fast lookup, then provides a pointer back to the full row in the heap file.
Why Trees? The Sorted Search Advantage
The most efficient way to search a sorted dataset is binary search: start in the middle, go left if your target is smaller, go right if it's larger, repeat. Binary search on a sorted array of N items takes O(log₂ N) steps instead of O(N). For 1 million rows, that's 20 comparisons instead of 1,000,000.
A B-Tree (Balanced Tree) generalizes this idea to disk-based storage. Instead of a sorted array, it's a tree where each node can hold many keys, and the tree stays balanced (all leaf nodes are at the same depth) through automatic rebalancing on insert and delete.
B-Tree vs. B+ Tree: The Critical Difference
Almost all modern RDBMS use a specific variant called the B+ Tree. The distinction matters:
Standard B-Tree:
- Every node (internal and leaf) stores both keys AND data pointers (row locations).
- Searching can terminate at any level of the tree if the key is found.
B+ Tree (what databases actually use):
- Internal nodes store only keys — they are pure routing nodes. No data pointers.
- All data pointers live exclusively at the leaf level.
- Leaf nodes are linked together in a doubly-linked list.
Why B+ Trees Win for Databases
Reason 1: Wider, shallower trees.
Because internal nodes store only keys (not data), you can fit far more keys per node. A node that fits in one 8 KB page might hold 200 keys instead of 50. This means the tree is much wider and shallower — typically 3-4 levels deep even for tables with hundreds of millions of rows. Fewer levels = fewer page reads to find any given key.
Reason 2: Range queries are fast.
This is the killer feature. To find all users with id BETWEEN 100 AND 500:
1. Traverse the tree once to find the leaf node containing id=100. (O(log N) steps)
2. Follow the linked list of leaf nodes rightward, collecting all IDs up to 500.
You never have to go back up the tree. Without linked leaves, you'd have to re-traverse the tree for every single value in the range.
Reason 3: Full index scans are sequential.
Because all data is at the leaf level and leaves are linked, scanning the entire index is a sequential read — the fastest possible disk access pattern.