Algorithms and Data Structures · Senior · Question 14 of 75
Why do databases use B-trees rather than binary search trees for indexes?
- 1Binary trees can't store string keys efficiently
- 2B-trees use less CPU per comparison than BSTs
- ✓Correct answer: Wide nodes match disk pages, so lookups need few page reads
Explanation
A node holds hundreds of keys, so a tree over millions of rows is only 3-4 levels deep, and each level is one disk page read. A binary tree would be about 20 levels with poor locality.