Why Databases Use B+ Trees Instead of BSTs

In RAM, a balanced Binary Search Tree (AVL, Red-Black) gives O(log₂ N) search time. But on disk, O(log₂ N) means 20 to 30 random disk I/O seeks per query!

⚡ The Fan-Out Advantage

A B+ Tree node is sized to match the storage block (typically 4KB to 16KB). With a fan-out of 512:

• Level 1: 1 page (Root)
• Level 2: 512 pages
• Level 3: 262,144 pages (~134 million keys)

Search requires only 3 disk reads instead of 27!

Read the complete storage lesson on Binary Dose.