Presets

Pick a table; every slider stays editable.

Table and pages

Index and cache

Query

Tree order (live tree)

Live results

Experiments

The science

Pages, not rows. A disk database reads fixed pages (default 8 KiB). With row size r a heap page holds rpp = floor(page / r) rows, so N rows need P = ceil(N / rpp) pages. A full (sequential) scan reads all P pages at cost cseq each.

B+ tree. An index page holds keys and child pointers; with key size k, an 8-byte pointer and fill factor f the fanout is F = floor(f * page / (k + 8)) and the leaf level holds ceil(N / F) pages. The height (pages read from root to leaf) is h = ceil(logF N), at least 1. A point lookup reads h index pages plus one heap page: it grows with the logarithm of N, so a billion rows still need only 3 to 5 reads at typical fanouts.

Cache. If C index pages stay in memory, the top levels (1, F, F2, ... pages) are cached first; levels that fit are free, the first level that does not fit is cached in proportion (C - cached) / pages in level. The remaining reads are random I/O at cost crand (default 4, a typical SSD/OS-cache planning ratio, not a measurement).

Range queries. For selectivity s the query returns m = s N rows: h - 1 + ceil(m / F) index pages, then heap pages. If the table is not ordered by the key, each row lands on a random page and the expected number of distinct pages touched is Cardenas' P (1 - (1 - 1/P)^m), each at crand; if it is clustered it is ceil(s P) sequential pages. The planner picks the cheaper of that and the full scan; the crossover selectivity s* is found by bisection.

Hash index. A hash table with load factor a and linear probing needs on average (1 + 1/(1 - a)) / 2 probes for a hit (Knuth). It answers equality in about one page but cannot answer ranges or ordering, so it never beats the B+ tree for them.

Honest simplifications. No write cost, locking, WAL, concurrency, variable-length keys, prefix compression, bloom filters, or the real planner's statistics; leaf pages are assumed full to the fill factor (a randomly built tree is about 69 % full, ln 2, so real heights can be one level larger); costs are in abstract page-read units. The live tree uses small orders so splits are visible; the cost chart scales the same maths to any table size.