GATE CS 2000 Q1.22 — File Organization and Indexing (B and B+ Trees)

The primary bottleneck in database systems is disk I/O (Input/Output). Accessing data from a secondary storage device (disk) is several orders of magnitude slower than accessing main memory (RAM).

To minimize the number of disk accesses, we need an indexing structure with a very small height:

• Binary Search Trees (BSTs): Have a fan-out (branching factor) of at most $2$. For $N$ records, the height of a balanced BST is $O( m{log}_2 N)$. Searching a record requires traversing many levels, resulting in a high number of disk reads.
• $\text{B}^+$-Trees: Have a very high fan-out $d$ (typically in the hundreds), because each node is designed to fit exactly into one disk block. The height of a $\text{B}^+$-tree is $O(\rm{log}_d N)$. For example, if $N = 10^6$ and $d = 100$, the height is only $\approx 3$, meaning we need at most 3 disk accesses to find any record.

Thus, because disk access is much slower than memory access, $\text{B}^+$-trees are preferred to minimize disk reads by keeping the tree height extremely low.