Course contentsShow
← Computer Science
Lesson 1685 of 2,87238. Database Transactions and IndexingFree lesson

B-Tree Height and Disk I/O

How B-Tree height relates to number of keys, fan-out factor, and disk access cost in databases.

B-Tree Height and Disk I/O

What you'll learn: How B-Tree height directly determines the number of disk accesses needed to find data in a database.

Why Height Matters in Databases

When your B-Tree index lives on disk (not in memory), every time you traverse from one node to another, you typically perform a disk I/O operation—one of the slowest operations in computing. The height of your B-Tree tells you the maximum number of disk reads needed to find any key.

The Height Formula

B-Tree height grows logarithmically with the number of keys. With a fan-out factor (branching factor) of d, a B-Tree of height h can store approximately d^h keys.

For example:

  • Fan-out of 100, height 3: ~1,000,000 keys
  • Fan-out of 100, height 4: ~100,000,000 keys

This means even massive databases require surprisingly few disk accesses!

The Disk Access Connection

If your B-Tree has height 3:

  • Search: Up to 3 disk reads (root → internal → leaf)
  • Insertion: Up to 3 reads + possible writes for splits
  • Deletion: Similar pattern

Compare this to a binary search tree storing the same million keys: you'd need up to log₂(1,000,000) ≈ 20 disk accesses. The high fan-out of B-Trees is specifically designed to minimize height and thus minimize expensive disk I/O.

Why B-Trees Stay Short

B-Trees keep nodes highly populated (typically 50-100% full) and use large fan-out factors (often 100-200 or more). This "wide and shallow" structure is perfect for disk-based storage, where reading one large node costs nearly the same as reading a small one.

Key Takeaway: B-Tree height determines worst-case disk I/O cost; by keeping trees shallow through high fan-out, databases can access millions of records with just 2-4 disk reads.