Exercise 3: An Index Built Before Any Data Exists — Possible Solution
====================================================================

THE TEST
------------------------------
    cat = Catalog(tmp)
    cat.create_table('customers', [('id', 'INTEGER'), ('name', 'TEXT')])
    cat.create_table('orders', [('id', 'INTEGER'), ('customer_id', 'INTEGER')],
                      foreign_keys=[ForeignKey('customer_id', 'customers', 'id')])
    cat.create_index('customers', 'id')   # index built on an EMPTY customers table

    cat.insert('customers', [1, 'Alice'])   # index updated incrementally afterward

    try:
        cat.insert('orders', [1, 2])   # customer 2 doesn't exist yet
        e3_raised = False
    except ForeignKeyViolation:
        e3_raised = True

    cat.insert('orders', [1, 1])   # customer 1 DOES exist -- should succeed
    _, orders_table = cat.tables['orders']
    print(list(orders_table.scan()))

RESULT
------------------------------
    orders after building the index on an empty table, then inserting customers/orders: [[1, 1]]

e3_raised is True (the invalid order was correctly rejected), and the
final orders table contains exactly the one valid order -- the index,
built before any customer rows existed, still correctly reflects
reality by the time it's actually needed.

WHY BUILDING THE INDEX EARLY DOESN'T LEAVE IT STALE
------------------------------
create_index() builds its initial BTreeNode by scanning whatever rows
already exist at that moment -- on an empty table, that's a real,
valid (if empty) B-tree with zero keys. From that point forward,
EVERY call to cat.insert() maintains every registered index
incrementally:

    for (t_name, col_name), root in list(self.indexes.items()):
        if t_name == table_name:
            col_idx = column_names.index(col_name)
            self.indexes[(t_name, col_name)] = btree_insert(root, values[col_idx], location)

This loop runs on every single insert into 'customers', regardless of
whether the index was built before or after any data existed -- there
is no special "catch-up" logic needed, because the index was never
allowed to fall behind in the first place. When [1, 'Alice'] is
inserted, btree_insert() is called immediately, and the index
genuinely contains key 1 from that point on.

WHY THE FK CHECK STAYS ACCURATE THE WHOLE TIME
------------------------------
_value_exists() always reads from self.indexes[(table_name, column)]
directly -- it has no separate, cached notion of "what customers
existed when the index was created." Checking customer_id=2 against
an index that has only ever seen key 1 correctly returns False (2 was
never inserted at all, regardless of index timing). Checking
customer_id=1 correctly returns True, since key 1 was added to the
SAME index object the moment customer 1 was inserted.

WHY THIS WORKS AS AN ANSWER
------------------------------
Building the index before any data exists, rather than after data is
already present (the order every other chapter's own index examples
used), rules out the possibility that create_index()'s own initial
scan is doing something the incremental btree_insert() calls
couldn't also achieve on their own -- confirming the index-maintenance
loop, not the initial build, is what actually keeps a foreign-key
check trustworthy over a table's entire lifetime.