Questions
22 of 26
What is the difference between a B-Tree and a B+ Tree? Why are B+ Trees better for disk access?
Difficulty: 5/10
B-Tree vs B+ Tree
Both B-Trees and B+ Trees are multi-way balanced search trees designed for external storage. In a B-Tree, records or record pointers may exist in internal nodes and leaves. In a B+ Tree, internal nodes primarily contain separator keys and child pointers, while records or record pointers are stored at the leaf level. B+ Tree leaves are commonly linked, making sequential and range access particularly efficient.
javascript
- 1
B+ Tree internal nodes can fit more separator keys because records are kept at leaves.
- 2
Higher fan-out generally reduces tree height.
- 3
Linked leaves make range scans efficient.
- 4
Uniform leaf-level record access simplifies many database index operations.
- 5
Both structures are designed to reduce storage I/O.
Follow-up Questions
- Why does higher fan-out reduce disk I/O?
- How does a B+ Tree execute a range query?