Real World Maths Busters

The Maths Behind Everyday Life

The story, the formula and a worked example — see exactly where this maths shows up in the world around you.

Back to all stories
Technology 3 min read

Why Databases Don’t Search Row by Row

A B-tree index finds any record in about 20 steps among billions.

Without an index, finding a record in a billion-row table means checking up to a billion rows. A B-tree index narrows it to about log(n) steps.

B-tree Depth

A B-tree with branching factor 100 and 1 billion records needs only log₁₀₀(10⁹) ≈ 4.5 levels. So finding any record takes about 5 disk reads.

Depth=⌈log⁡b(n)⌉\text{Depth} = \lceil \log_b(n) \rceil

b = branching factor, n = records

1 billion records, branching factor 100

  1. 1

    Depth

    ⌈log⁡100(109)⌉=⌈4.5⌉=5\lceil \log_{100}(10^9) \rceil = \lceil 4.5 \rceil = 5
Answer

5 levels — just 5 disk reads to find any record

The takeaway

B-tree indexes turn billion-row searches into a handful of lookups. That’s how databases stay fast.

Back to all stories