A B-tree's height is the smallest h with Bʰ ≥ N — which is ⌈log_B N⌉ written so that a computer gets it right. A billion keys at a fanout of five hundred is four levels, the page cache holds the top two of them for a couple of megabytes, and a lookup is therefore two disk reads. Nothing about a billion is slow here.
Core ideas
The definition is a power rather than a logarithm, the base is enormous, and the cost a reader pays is neither of those but what memory does not hold.
The question is how many levels of fanout B it takes to cover N keys, and the answer is the smallest h with Bʰ ≥ N. That is a search over integers: multiply B into an accumulator and count the multiplications. ⌈log_B N⌉ names the same number in exact arithmetic, and the lab computes the power because a floating-point logarithm does not always agree.
A 4 kB page holding 500 index entries gives B = 500, so every level multiplies the reach by five hundred. Four levels reach 62 500 000 000 keys. This is why the height of a real index is a single digit, and why “log N is slow for big N” has nothing to hold onto here: the base is five hundred and it is set by the page, not by the data.
The descent reads one page per level, so h page reads — except that the root and the level below it are 4.00 kB and 2.00 MB and live in memory permanently. At N = 10⁹ and B = 500 that turns a four-I/O lookup into a two-I/O one, and no change to the tree was involved.
The material
How a height is actually computed, why a logarithm is the wrong instrument for it, and where the I/Os go.
For a tree in which every internal node holds up to B children, the height h is the smallest integer with Bʰ ≥ N, where N is the number of keys stored. Equivalently, h = ⌈log_B N⌉.
A lookup descends one node per level and reads one page per node, so an uncached lookup costs h page reads.
That table is not an illustration of the answer; it is the computation. Four multiplications and four comparisons, in exact integer arithmetic, and the height is the number of multiplications the accumulator needed. The lab draws the same four rows.
Because at every exact power of the fanout a quotient of two logarithms can land a few units in the last place above the integer, and the ceiling then adds a level that does not exist. At B = 3 and N = 9, log(9)/log(3) evaluates to 2.0000000000000004 and its ceiling is 3 — a two-level tree reported as three, which on a page about counting I/Os is a whole extra I/O. It is not a rare corner: B = 5 at N = 125, B = 8 at N = 2 097 152 and B = 19 at N = 2 476 099 all do the same thing. The lab prints what a logarithm would have said beside the exact answer and tells you when the two disagree.
Hold B = 500 and raise N. At 10⁶ the height is 3; at 10⁹ it is 4; at 10¹² it is 5. Three orders of magnitude buy one level. The height changes only when N crosses a whole power of B, so every tree holding between 125 000 001 and 62 500 000 000 keys — a range of five hundred to one — is exactly four levels deep.
Look at the level sizes rather than the level count. The top two levels together are 4.00 kB + 2.00 MB; the third is 1.00 GB and the fourth is 500.00 GB. So the levels that are cheap to keep in memory are exactly the ones every descent passes through, and keeping them is what an engine does without being asked. Two megabytes removes half the I/Os of every lookup in the system.
The number that multiplies into a workload is the cached one. Ten thousand lookups a second against this tree with two levels resident is 20 000 disk reads a second; against the same tree with nothing resident it is 40 000. The height did not change and the device's day did.
Two things the model assumes. Nodes are taken to be full, and a real B-tree's nodes sit somewhere between half full and full, so the effective fanout is below the page's capacity and the true height is occasionally one more than this calculation says. And a lookup is taken to be one page read per level, which ignores the leaf splitting across pages. Both errors point the same way — the real cost is at or just above the computed one — which is what makes the computed one usable.
Interactive
A billion keys at B = 500 is four levels, and the cache holds two of them
Method
The first step is the one people skip, and it is the one that decides every number after it.
B is the page size divided by the size of one index entry: a 4 kB page with an 8 B key and an 8 B pointer is about 250, and the same page with a shorter key is more. Every figure downstream depends on this one.
B, B², B³, …, stopping at the first value that is at least N, and count the multiplications. Four of them at B = 500 passes a billion. Do not take a logarithm; at an exact power it can round the wrong way.
Add the level sizes from the top — 4 kB, 2 MB, 1 GB — and see how far down your memory reaches. The I/Os a lookup costs are the levels below that line, not the height.
The height is a fact about the tree; the I/Os a second are the fact about the device. 10 000 lookups a second against a two-I/O tree is 20 000 reads a second, and that is the number to hold against what the disk can do.
The search is four multiplications and a comparison. Everything after it is the page cache.
Read the fourth column. Two megabytes of memory removes half the I/Os of every lookup in the system, and it is the cheapest two megabytes anyone will ever spend. The third level is a gigabyte, which is a real decision; the fourth is five hundred, which is not.
The misconception this page is aimed at is that log N gets uncomfortable for large N. Multiply the fanout out and see what it would take: five levels cover 31.25 trillion keys and six cover about fifteen quadrillion. The base is five hundred, and a base of five hundred has no large logarithm anywhere you will ever put data.
For a faded rehearsal, take N = 10⁹ with a fanout of 100 — a longer key, so fewer entries a page. The supplied first move is that 100³ = 10⁶ is far short of N. Finish the search, state the height, and then say how many levels have to be resident to keep a lookup at two I/Os. Check both on the sliders before opening the quiz.
You should be able to find a height by multiplying a fanout out, state the level sizes and therefore which of them memory will hold, and convert a lookup rate into a disk read rate without going anywhere near a logarithm.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.