B-Tree

(of order k)

• All nodes have at most k children
• Non-leaf nodes have at least k/2 children
• Either the root node is a leaf or it has at least 2 children
• All leaves are at the same level.

Tailored for external storage Node ~ Blocks on disk. Shallow tree means less block transfers.