Question

What is the primary difference between a B-tree and a B+ tree?

• A. B-trees have a higher fill factor.
• B. B+ trees store data pointers only in the leaf nodes.
• C. B-trees do not allow duplicate keys.
• D. B+ trees cannot be used for primary indexing.

Hint:

Most modern relational databases (like MySQL and PostgreSQL) use B+ trees specifically because of the linked leaf nodes and the efficiency of range-based searches.

Answer 1

The Correct Option is B

Concept:
Both B-trees and B+ trees are self-balancing search trees designed for storage systems where data is read and written in large blocks. They minimize disk I/O by keeping the tree "fat and short." However, their internal architecture differs significantly in how they handle data storage.

Step 1: Architecture of a B-tree.
In a B-tree, every node (both internal nodes and leaf nodes) contains three things: the key, the child pointer, and the actual data pointer (or the record itself).
• Pros: If a search hits a key in an internal node, it can stop immediately.
• Cons: Because internal nodes carry data pointers, they are "heavy," meaning fewer keys fit in a single disk block, increasing the height of the tree.

Step 2: Architecture of a B+ tree.
In a B+ tree, internal nodes only store keys to act as a directory. All actual data pointers (or records) are stored exclusively in the leaf nodes.
• This allows internal nodes to be "lighter" and hold many more keys, resulting in a much higher branching factor and a shorter tree.
• Furthermore, all leaf nodes are linked together in a linked list.

Step 3: Advantage for Range Queries.
Because all data is in the leaves and the leaves are linked, a range query (e.g., "Find all IDs between 100 and 500") is extremely efficient. In a B+ tree, you find 100 and then simply traverse the linked list of leaves. In a B-tree, you would have to perform a complex in-order traversal up and down the tree.