IIT Delhi·5 days ago
How B+ Trees power database indexes: Why not binary search trees?
Binary search trees have deep heights (O(log2 N)), meaning every lookup requires 15-20 disk I/O operations. B+ Trees have a high fan-out (each node holds hundreds of keys), keeping tree height at 3-4 even for millions of records. Plus, all leaf nodes are linked in a doubly linked list, making range queries (`WHERE age BETWEEN 20 AND 30`) blistering fast.
