B-Tree vs Binary Search Tree
You'll learn why B-Trees store multiple keys per node and how this design choice dramatically reduces disk I/O operations in databases.
The Core Difference
Binary Search Trees (BSTs) store one key per node with two child pointers. B-Trees, in contrast, store many keys per node (often hundreds) with many child pointers. This isn't just a structural curiosity—it's a deliberate optimization for disk-based storage.
Why Multiple Keys Per Node?
Here's the critical insight: disk I/O is thousands of times slower than memory access. When your database reads from disk, it doesn't fetch a single byte—it fetches an entire block or page (typically 4KB–16KB).
With a BST, each node visit requires a separate disk read. To find a key in a million-record database might require 20 disk reads (log₂ 1,000,000 ≈ 20 tree levels).
The B-Tree advantage: By packing hundreds of keys into one node that fits in a single disk block, you might only need 3–4 disk reads to search the same million records (since each level handles far more branching). One disk read gives you hundreds of comparison opportunities instead of just one.
Real-World Analogy
Think of searching for a word in a dictionary. A BST is like a dictionary with one word per page—you'd flip constantly. A B-Tree is like a normal dictionary with many words per page—you make far fewer page turns because each page gives you more information to narrow your search.
The Trade-off
B-Trees are more complex to implement and use more CPU per node (searching hundreds of keys), but this CPU cost is negligible compared to the massive savings in disk I/O.
Key Takeaway: B-Trees use multiple keys per node specifically to minimize disk I/O—each disk read fetches an entire node packed with keys, reducing the number of expensive disk operations needed for database lookups.