B-Tree & B+ Tree
Scenario
You need to search through 1 billion rows in a database table. A binary search tree would require 30 disk reads to find a record.
How do modern databases reduce those 30 agonizingly slow disk reads down to just 3 or 4?
Mental model
Instead of a tall, skinny tree with 2 branches per node, imagine a short, fat tree with 100 branches per node.
Disk reads are slow. B-Trees optimize for disk by packing many keys into a single 'block' (node), drastically flattening the tree and reducing the number of times the disk must be accessed.
Explanation
To understand database indexing, you first have to understand hardware. Reading from memory (RAM) is lightning fast. Reading from a spinning hard disk (or even an SSD) is thousands of times slower. When data is on disk, it is read in chunks called 'blocks' or 'pages' (typically 4KB to 16KB). If you use a standard Binary Search Tree for 1 billion records, the tree is ~30 levels deep. That means traversing it takes 30 separate disk reads. That is far too slow.
Enter the B-Tree. It is a self-balancing search tree designed explicitly for systems that read and write large blocks of data. Instead of having just 1 key and 2 children per node, a B-Tree node is exactly the size of one disk block and contains hundreds of keys and children. This makes the tree extremely wide and extremely shallow. A B-Tree with a branching factor of 100 can store 1 million records in just 3 levels, and 100 million in 4 levels. Finding any record takes at most 3 or 4 disk reads.
While B-Trees are great, databases almost exclusively use a variant called the B+ Tree. In a standard B-Tree, both the search keys and the actual data pointers are stored in every node (root, internal, and leaf). This takes up space, meaning fewer keys fit in a block, making the tree taller.
The B+ Tree solves this with two massive improvements. First, it pushes ALL the actual data pointers down to the leaf nodes. The internal nodes only contain search keys to guide the traversal. Because internal nodes now hold no data, they can pack in far more keys, making the tree even shorter and flatter.
Second, in a B+ Tree, all the leaf nodes are linked together in a continuous, doubly-linked list. This makes range queries (e.g., `WHERE age BETWEEN 20 AND 30`) incredibly fast. In a standard B-Tree, you would have to constantly traverse up and down the tree branches to find the next value. In a B+ Tree, you traverse down the tree exactly once to find '20', and then simply walk sideways across the linked leaves until you hit '30'.
Key points
- Disk Block Optimization: B-Tree nodes are sized to match disk blocks, packing many keys into one read to minimize slow disk access.
- B-Tree: Stores data pointers in ALL nodes (internal and leaf). Good for single-key lookups.
- B+ Tree: Stores data pointers ONLY in leaf nodes. Internal nodes just guide search. Results in a flatter tree.
- Linked Leaves: B+ Tree leaves are linked sequentially, allowing blazing fast range scans without traversing up and down the tree.
Common mistakes
- Thinking binary search trees are fine for databases: BSTs are great in RAM, but terrible on disk because their depth requires too many separate I/O operations.
- Confusing B-Tree and B+ Tree lookups: In a B-Tree, if the key is in the root, the search stops immediately. In a B+ Tree, the search MUST always travel all the way to a leaf node, because internal nodes don't have the actual data.
Glossary
- B-Tree
- A wide, shallow tree data structure optimized for fast read and write operations on slow storage systems like hard drives, where each node stores many keys and data pointers.
- B+ Tree
- An advanced version of a B-Tree where all the actual data is kept only in the bottom leaf nodes, allowing the upper levels to pack in more search keys and the leaves to be linked for fast range searches.
- leaf nodes
- The bottom-most elements in a tree structure that do not have any child nodes beneath them. In a B+ Tree, these hold the actual data or pointers to the data.
Recall questions
- Why are B-Trees preferred over Binary Search Trees for databases?
- Where is the actual data stored in a B+ Tree?
- What structural feature of a B+ Tree makes range queries extremely fast?
Questions & answers
Explain the difference between a B-Tree and a B+ Tree.
In a B-Tree, data is stored in all nodes. In a B+ Tree, data is only in leaf nodes, and leaves are linked. B+ Trees have higher fan-out (shorter trees) and faster range queries.
Approach: Always emphasize the linked leaves for range queries, as it's the primary reason relational databases use B+ Trees.
How many disk accesses are required to find a record in a B+ Tree?
Equal to the height of the tree (usually 3 or 4). The root node is almost always cached in RAM, reducing it further.
Approach: Mention that the height is log_m(N) where m is the massive branching factor (like 100+).