Height, Disk I/O & Applications

The whole reason B-trees exist is to be short. Because every non-root node holds at least t − 1 keys, the node count grows explosively with depth. A B-tree of height h holds at least:

The height is logarithmic in n with base t — and t is large. That base is what makes B-trees flat.

Concrete numbers (t = 500, a realistic disk-page fan-out):

Three levels index a quarter-billion keys. A balanced binary tree would need ~28 levels for the same data — and each level is a separate disk seek.

B-trees were designed for data too big for RAM, living on disk (or SSD). The cost model there is brutally simple:

Reading one byte from disk costs almost the same as reading a whole block. The expensive part is the seek — positioning the head / addressing the page — not the bytes transferred. A disk access is ~100,000× slower than a memory access.

So the metric that matters is not comparisons but the number of disk accesses, and B-trees are engineered to minimize it with one design rule:

Make each node exactly the size of one disk page (or block).

A typical page is 4 KB, 8 KB, or 16 KB. If each key + pointer takes, say, 16 bytes, a 4 KB page holds ~250 keys — so we pick t ≈ 128 and one node fills one page. Then:

• One disk read loads an entire node — all ~250 keys and their child pointers arrive together.
• A search / insert / delete touches only O(log_t n) nodes = O(log_t n) disk accesses.
• With the numbers above, any key in a 100-million-row table is found in ≤ 3 disk reads.

A binary search tree, by contrast, would need one disk seek per key comparison — ~27 seeks for the same data. This 10× reduction in I/O is the entire reason B-trees (and their variant B+ trees) power essentially every database and file system.

Most production systems actually use a B+ tree, a small refinement of the B-tree:

• All data records live in the leaves; internal nodes hold only separator keys (routing information). This lets internal nodes pack in more keys → even higher fan-out → even shorter trees.
• Leaves are linked in a sorted linked list. That makes range scans ("all orders between March and June") trivially fast — find the start leaf, then walk sideways — without climbing back up the tree.

Everything you learned about splitting, borrowing, and merging still applies; B+ trees just relocate the actual data to the leaf level.

MySQL's default storage engine, InnoDB, stores every table as a B+ tree and builds every secondary index as a B+ tree too.

• Clustered index: the table's rows are physically stored in the leaves of a B+ tree keyed by the primary key. The table is a B-tree. Looking up a row by primary key is just a B+ tree search — 2–4 page reads even for huge tables.
• Page size = node size: InnoDB's default page is 16 KB, and each B+ tree node is exactly one page. High fan-out (hundreds of keys per node) keeps indexes 3–4 levels deep in practice.
• Secondary indexes (e.g. INDEX(email)) are separate B+ trees whose leaves hold the primary-key value, used to jump back into the clustered index.
• Range queries like WHERE age BETWEEN 20 AND 30 exploit the linked leaves — one descent, then a sequential leaf scan.

This is why "add an index on that column" turns a full-table scan (O(n) reads) into an O(log n) lookup — you are literally building a B+ tree over the column.

File systems face the same problem: a single directory may hold hundreds of thousands of files, and the OS must locate a file by name quickly on disk.

Windows' NTFS stores directory contents as a B+ tree indexed by file name (the $INDEX_ROOT / $INDEX_ALLOCATION attributes). Consequences:

• Fast name lookup: finding report.docx in a directory of 500,000 files takes a handful of page reads instead of a linear scan.
• Sorted listings for free: an in-order walk of the B+ tree returns file names already sorted.
• Index records = disk clusters: each tree node maps to a fixed-size cluster, mirroring the "node = page" rule.

Other file systems use the same idea: HFS+ / APFS (macOS) use B-trees for their catalog, and Btrfs ("B-tree file system") and XFS are built almost entirely from B-trees. The pattern is universal: whenever a sorted index must live on disk, it is a B-tree.

For a B-tree of minimum degree t holding n keys:

The disk-access column is the one that matters in practice, and it is a small constant (≤ 3–4) for datasets up to billions of keys. That guaranteed shallowness — never degrading regardless of insertion order — is what makes the B-tree the default on-disk index structure.