Inside a Database

A database is tables of rows whose keys point at each other: a primary key names a row, a foreign key points at one, and the engine refuses every row that would break a pointer.

An index is a wide, shallow tree with every leaf at one depth: a lookup reads one page per level, an insert splits upward, and the root grows only at the top, so any row is a few reads away.

A join pairs the rows of two tables whose keys agree: a nested loop, a hash table, and two sorted runs find the same pairs at three prices, and the outer joins keep the rows nobody matched.

SQL says what, not how: a cost-based planner reads the table statistics, prices every way of scanning and joining in page reads, prunes the dearer plan over the same tables, and runs the cheapest.

A transaction is all or nothing and alone in the world. Interleave two transfers and an update is lost; lock what each touches until it ends and the books balance, at the price of the odd deadlock.

Write the intention to a log before touching a page, force the log at commit, and after a crash replay what was promised and undo what was not.

Writes fill a sorted table in memory, full tables flush to disk as immutable runs, runs merge downward in the background, and a read checks the layers newest first.