Four Reads For A Billion

An on-disk index over $10^9$ keys. The storage layer reads and writes whole 8192-byte pages, and nothing is cached.

quantity	value
page size	8192 bytes
per-page header	40 bytes
one entry (key plus child pointer)	16 bytes

Internal nodes are packed full, so the fanout is $\lfloor (8192 - 40)/16 \rfloor = 509$ children per node.

How many pages must be read to look up one key?

509