What is the difference between a B-Tree and a B+ Tree? Why are B+ Trees better for disk access?

Difficulty: 5/10

tree structures, disk I/O, indexing

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.

Scenario Questions

0-2 years experience

Follow-up Questions