Databases

A database holds state that outlives any single request and serves many readers and writers at once. The questions that turn hard are not how to store a row. They are the questions that surface once concurrency and failure enter the picture.

Two forces generate this whole cluster. Everything below is an instance of one of them.

The first force is correctness under concurrency and failure. When many transactions touch the same data at once, and machines crash partway through, the system has to answer three questions. What survives a crash. What one transaction sees while another is partway through a write. What a commit guarantees. The guarantees a transaction makes, and the isolation levels that relax them, are the vocabulary for reasoning about this force.

The second force is the read, write, and space tradeoff across on-disk structures. The data has to live somewhere on disk in a shape that supports lookups, range scans, and updates. No single structure is best at all three of reading, writing, and space at once. Each on-disk structure picks a point in that tradeoff, and the choice of structure follows from which of the three matters most for the workload.

Hold these two forces and the cluster organizes itself. The transaction guarantees sit at the top, describing what the database promises. The on-disk structures sit at the bottom, describing how it keeps those promises against physical storage. The pages between them fill in the mechanisms.

The two generating forces

Correctness under concurrency and failure

ACID transactions name the four guarantees a transaction makes: atomicity, consistency, isolation, and durability. Each one promises something specific about what holds when a transaction commits or aborts. Isolation is the guarantee that bends. Isolation levels trade correctness for throughput, relaxing what one transaction sees of another's in-progress work in exchange for more concurrency.

That tradeoff is where this force gets its depth. The stricter the isolation, the less concurrency the system allows, and the more a commit costs. Read the ACID page for the four guarantees and how isolation levels move along the correctness-versus-throughput axis.

Read, write, and space tradeoff across on-disk structures

B-tree is the default on-disk index in relational databases. It keeps sorted keys with high fanout and updates them in place. That shape makes it strong on reads and range scans, since a lookup walks a shallow tree and a range scan follows sibling links.

LSM-tree is the write-optimized alternative. It buffers writes in memory, flushes immutable files to disk, and compacts them in the background. That shape makes it strong on write throughput and ingest volume, since a write appends instead of seeking to update in place.

The B-tree and LSM-tree pages frame the storage choice around the same read, write, and space tradeoff from opposite corners. Reading them together shows the tradeoff directly: one structure optimizes reads, the other optimizes writes, and the workload decides which corner to sit in.

Atomic pages

• ACID transactions. The four guarantees a transaction makes (atomicity, consistency, isolation, durability), what each one promises, and how isolation levels trade correctness for throughput.
• B-tree. The default on-disk index in relational databases: sorted keys, high fanout, in-place updates, strong on reads and range scans.
• LSM-tree. The write-optimized alternative: buffer in memory, flush immutable files, compact in the background, strong on write and ingest volume.

More atomic pages land as the cluster grows: isolation levels in depth, multiversion concurrency control, two-phase commit, and write-ahead logging. Each one slots under one of the two forces above. Isolation levels and multiversion concurrency control extend the correctness force. Write-ahead logging connects both, supplying the durability that the storage structures rely on.