Which one of the following is a key factor for preferring B+ -trees to binary…
2005
Which one of the following is a key factor for preferring B+ -trees to binary search trees for indexing database relations?
- A.
Database relations have a large number of records
- B.
Database relations are sorted on the primary key
- C.
B+ -trees require less memory than binary search trees
- D.
Data transfer from disks is in blocks
Attempted by 110 students.
Show answer & explanation
Correct answer: D
Solution: Data transfer from disks is in blocks; B+ trees are optimized for block-based I/O.
Disk transfers are done in blocks, so B+ tree nodes are sized to fill a block. Each node stores many keys and pointers (high fanout), which greatly reduces the tree height and the number of disk reads required for a lookup.
Internal nodes keep only keys and pointers while actual records or record pointers reside at the leaves. This allows more keys per internal node and better utilization of each disk block.
Leaf nodes are linked for sequential access, making range queries and scans efficient with minimal additional disk I/O.
By contrast, a binary search tree has fanout of two and typically does not align nodes to disk blocks, so searches and range scans often require many more disk reads.
Therefore, because disk I/O is the dominant cost in database indexing, the block-oriented design and high fanout of B+ trees make them a better choice than binary search trees.