Technology Database Design Simulation

B+tree indexes versus table scans, with real page arithmetic

Controls

Live readout

What you are seeing

A database stores rows in fixed-size pages and an index is a tree of pages. A lookup walks root to leaf (one page per level) and then reads one heap page; a scan reads on average half of the table. The top shows a lookup path in a tiny tree, the bottom plots pages read against table size on log axes: the scan line climbs steeply, the index line is nearly flat.

Independent check

computing...
The science

Page arithmetic. Index fan-out f = floor(page / (key + 8-byte pointer)) x fill factor. Leaf pages = ceil(N/f); tree height h = 1 + ceil(logf(leaf pages)). Heap pages = ceil(N / floor(page/row)). An index point lookup costs h + 1 page reads (the +1 fetches the row); a full scan of an unsorted heap reads on average heap/2 pages.

Time = pages x device latency (0.1 ms NVMe random read, 8 ms HDD seek).

Check. The page builds a real bulk-loaded B+tree in memory (up to 300,000 keys) and counts the pages touched by 20,000 random successful and unsuccessful lookups.

Simplifications: no buffer cache (in real systems the upper levels sit in RAM), no inserts or page splits (bulk loaded), no concurrency, no sequential-read speed advantage of scans (which narrows the gap on HDD). Relational normalisation is not modelled here.