Exercise 3: Tree Height at Five Real Data Sizes — Possible Solution
====================================================================

THE TEST
------------------------------
    for n in (1, 5, 15, 40, 100):
        root = BTreeNode(leaf=True)
        for k in range(1, n + 1):
            root = btree_insert(root, k, f"v{k}")
        print(n, tree_height(root))

RESULT
------------------------------
    1 key    -> height 1
    5 keys   -> height 2
    15 keys  -> height 3
    40 keys  -> height 4
    100 keys -> height 4

The height does NOT grow smoothly or proportionally with the number of
keys -- it jumps at specific thresholds and then stays flat for a
while, including staying at exactly height 4 across the jump from 40
keys all the way to 100 keys.

WHY HEIGHT GROWS IN JUMPS, NOT SMOOTHLY
------------------------------
Height only ever increases in ONE specific circumstance: when the
overflow signal from a split propagates all the way up through every
ancestor and reaches the ROOT itself, forcing btree_insert's own
top-level code to build a genuinely new root:

    new_root = BTreeNode(leaf=False)
    new_root.keys = [promoted_key]
    new_root.children = [root, new_right]

Every OTHER split -- a leaf splitting, or an internal node below the
root splitting -- gets fully absorbed by its own parent (the promoted
key and new sibling simply become one more key and one more child in
an existing node) without ever needing the height to change at all.
With MAX_KEYS=3, a huge number of splits can happen at the leaf and
lower-internal levels, silently reorganizing the tree's own shape,
long before enough of those splits ever cascade all the way to the
root to force one more level of height.

ROUGHLY HOW MANY KEYS IT TAKES TO REACH EACH NEW LEVEL
------------------------------
Going from the measured data: height 1 -> 2 happens somewhere between
1 and 5 keys (a single leaf can hold up to 3 keys with MAX_KEYS=3,
so the very first split happens on the 4th insert). Height 2 -> 3
happens somewhere between 5 and 15 keys. Height 3 -> 4 happens
somewhere between 15 and 40 keys. And critically, height stays at 4
all the way from 40 to at least 100 keys -- a single level of
internal nodes below the root can absorb a genuinely large number of
additional keys before ITS OWN capacity is exhausted and a new level
becomes necessary again.

WHY THIS WORKS AS AN ANSWER
------------------------------
This is the real, concrete meaning behind "a B-tree's own height grows
logarithmically" (Chapter 1's own real log2(n) comparison) -- it isn't
a smooth curve at all; it's a step function that stays flat for long
stretches and only increases at specific, increasingly-spaced-apart
thresholds, which is exactly what makes a B-tree's own worst-case
lookup cost stay small even as the amount of data stored grows very
large.