What is a B-tree and why is it used in databases?

• A. A simple linked list used for in-memory data.
• B. A binary search tree that can become unbalanced.
• C. A hash table used for fast lookup.
• D. A balanced search tree optimized for block storage; provides efficient logarithmic insert/search/delete for disk-based systems.

Answer: (D)

Databases store vast amounts of data on disk, so minimizing disk I/O is the key to fast access. A B-tree is a balanced multi-way search tree designed for block storage: each node holds many keys and pointers to children, and all leaves sit at the same depth. This high branching factor means the tree can be shallow, so searching, inserting, or deleting typically touches only a few disk blocks, yielding efficient logarithmic-time operations even as the dataset grows. The nodes are sized to fit disk blocks, which optimizes reads and writes and supports good performance for range queries and scans—common in database workloads. In contrast, a simple linked list would require many reads to find or traverse data; a binary search tree can become unbalanced and tall, worsening performance; and a hash table prioritizes fast exact lookups but doesn’t maintain order or support efficient range operations. For on-disk databases, a balanced, block-friendly structure like a B-tree provides predictable, scalable performance.