Databases

Almost every program eventually needs to remember something after it stops running. You could just write to files — and for a config file or a log, that's exactly right. But the moment you have lots of data, many users touching it at once, and a need to find specific records quickly, plain files fall apart. A database is the machinery that makes persistent data fast, concurrent, and trustworthy.

Specifically, a database gives you four things files don't:

• Efficient querying — find the rows you want without scanning everything.
• Concurrent access — many users reading and writing at once, safely.
• Transactions — groups of changes that either all happen or none do.
• Structure — indexes, relationships, and constraints that enforce rules about the data.

Analogy: A pile of files is a shoebox of receipts. A database is an accountant's filing system — indexed, cross-referenced, and protected against two people scribbling on the same page at once.

Relational Databases (SQL)

The dominant model for fifty years. Data lives in tables of rows and columns, and tables are linked by keys — a value in one table that refers to a row in another.

You query with SQL, a declarative language: you describe what you want, and the database figures out how to get it.

-- "Total spent by Alice, across all her orders"
SELECT u.name, SUM(o.price) AS total
FROM Users u
JOIN Orders o ON u.id = o.user_id
WHERE u.name = 'Alice'
GROUP BY u.name;
-- Result:  Alice | 17.00

That JOIN is the relational model's superpower: data is stored once and stitched together at query time. The declarative style is also why two databases can run the same SQL with wildly different performance — the optimizer (Chapter 21) chooses the execution strategy.

ACID — The Guarantees That Make Money Safe

A transaction is a group of operations treated as a single unit. The classic guarantees a relational database provides are summarized by the acronym ACID:

Property	Meaning	Example
Atomicity	All-or-nothing — if any part fails, the whole transaction rolls back	A bank transfer debits and credits, or neither happens
Consistency	Every transaction moves the DB from one valid state to another	A constraint that balances can't go negative is never violated
Isolation	Concurrent transactions don't step on each other	Two people withdrawing can't both grab the same $100
Durability	Once committed, data survives crashes	After "transfer complete," a power outage can't lose it

Atomicity is the one most worth internalizing: without it, a crash halfway through a transfer leaves money debited from one account but never credited to the other.

Indexes — Speed Up Reads

Without help, finding a specific row means scanning the whole table — O(n). An index is a separate data structure that maps column values to row locations, usually a B+ tree (a balanced tree designed for disk):

A B+ tree turns a query like WHERE name = 'Bob' from O(n) into O(log n) — and because each node holds many keys, even a billion-row table is reached in a handful of disk reads.

Analogy: An index is the index at the back of a textbook. Without it, you flip through every page to find "photosynthesis." With it, you jump straight to page 247. But the index isn't free — every time you add a page, you must update it too.

That trade-off is the whole story of indexing:

• Reads get faster ✓
• Writes get slower ✗ — every insert/update/delete must also update the index
• Storage grows ✗ — the index is extra data on disk

So you index the columns you filter and join on, not every column. Over-indexing is a common cause of mysteriously slow writes.

Normalization — Store Each Fact Once

Normalization is organizing tables so that each fact lives in exactly one place. The enemy is duplication, which leads to update anomalies — change a value in one row and forget the copies, and now your data contradicts itself.

The trade-off runs the other way too: heavily normalized data needs more joins to reassemble, which can be slow. So real systems sometimes denormalize deliberately — duplicating data to avoid expensive joins on hot read paths — accepting the maintenance cost for speed. Knowing when to break the rule is a senior skill.

NoSQL Databases

Relational databases assume a fixed schema and value consistency above all. When that doesn't fit — schemas that change constantly, data too large for one machine, or relationships that are the data — a family of NoSQL stores offers different trade-offs:

Type	Examples	Best for	Mental model
Document	MongoDB, CouchDB	Flexible, JSON-like records	Folders of varied documents
Key-Value	Redis, DynamoDB	Simple lookups, caching	A giant dictionary
Column-Family	Cassandra, HBase	Wide rows, time-series, analytics	Rows with different columns each
Graph	Neo4j, Neptune	Relationship-heavy data	A social network map

A document database embeds related data together instead of splitting it across tables — the opposite philosophy to normalization:

{
  "_id": "user123",
  "name": "Alice",
  "orders": [
    { "item": "Book", "price": 15 },
    { "item": "Pen",  "price": 2 }
  ]
}

Embedding makes reads fast (one fetch gets everything) but writes redundant (Alice's name is duplicated wherever she appears). It's denormalization as a default.

Analogy: SQL is a neatly ruled spreadsheet with strict rules about what goes in each cell. NoSQL is a folder of Post-it notes — more flexible, but the discipline is now your responsibility, not the database's.

Choosing: SQL or NoSQL?

This is one of the most consequential early decisions in a system, and the honest answer is start with a relational database unless you have a specific reason not to. Reach for SQL when you need complex queries, multi-row transactions, and strong consistency (most business and financial data). Reach for NoSQL when you have a clear scaling or shape mismatch: massive write volume, a genuinely schemaless domain, geographic distribution, or relationship-first data. Many mature systems use both — relational for the source of truth, a key-value cache and a search index alongside it.

CAP Theorem

The moment a database is spread across multiple machines, a fundamental limit appears. The CAP theorem says that during a network partition (when nodes can't talk to each other), you must choose between two goals:

• Consistency — every read returns the most recent write.
• Availability — every request gets a (non-error) response.
• Partition tolerance — the system keeps working despite dropped messages between nodes.

The subtlety beginners miss: partitions will happen in any real distributed system — networks fail. So partition tolerance isn't optional; you're really choosing, during a partition, between consistency and availability. That's why systems are described as CP (refuse some requests to stay correct) or AP (answer everything, possibly with stale data).

Analogy: A chain of stores should all show the same prices (consistency). A network outage cuts them off from headquarters (partition). Do they close until they can confirm prices match (CP — consistent but unavailable), or stay open and risk showing a slightly stale price (AP — available but inconsistent)? There's no third option that keeps both during the outage.

• CP: traditional RDBMS clusters, HBase, MongoDB (default)
• AP: Cassandra, DynamoDB, CouchDB

In practice this isn't all-or-nothing — modern systems tune consistency per operation. Before opening the engine up to see how these guarantees are built, the next chapter covers the skill that decides whether a database serves you well or fights you at every turn: designing the schema itself.

Picking a database is the easy part. The decision that quietly governs everything afterward — how fast your queries run, whether your data can drift into contradiction, how painful next year's feature will be — is how you model your data. A schema is a contract: it declares what your data is and what rules it must always obey. Get it right and the database does enormous work on your behalf; get it wrong and you spend years writing application code to paper over the cracks.

Modeling proceeds in three levels of refinement. The conceptual model names the real-world things you care about (customers, orders, products) and how they relate, ignoring any database. The logical model turns those into tables, columns, and keys. The physical model adds the engine-specific details — types, indexes, partitions. Beginners often jump straight to typing CREATE TABLE; the discipline is to think in concepts first.

Entities and Attributes

An entity is a thing worth storing — a user, an order, a product. In a relational database each entity type becomes a table, each instance becomes a row, and each property becomes a column (an attribute). The art is deciding what counts as its own entity versus an attribute of another: an order's total is an attribute, but the customer who placed it is an entity in its own right, because customers exist independently and are referenced by many orders.

Keys — How Rows Are Identified and Linked

Keys are the backbone of relational modeling. Every table needs a primary key (PK): a column (or set of columns) that uniquely identifies each row. A foreign key (FK) is a column holding the primary key of another table — the thread that stitches tables together.

A recurring design decision is natural vs surrogate keys. A natural key is real-world data that happens to be unique (an email, an ISBN). A surrogate key is a meaningless, system-generated id (an auto-incrementing integer or UUID). Surrogate keys are usually the better default: real-world "unique" values change (people change emails) and leak business meaning into your references. A composite key combines several columns when no single one is unique — common in join tables, where the pair (order_id, product_id) identifies a row.

Analogy: A primary key is a person's unique ID number; a foreign key is writing that ID number on a form to point at them. Using a natural key like a phone number as the ID works until someone changes their number — and now every form pointing at them is wrong.

Relationships and Cardinality

Entities relate to each other, and cardinality describes how many of one connect to how many of the other:

• One-to-one (a user and their profile): fold into one table, or split for security or size reasons.
• One-to-many (a user and their orders): the most common shape — put a foreign key on the "many" side. An order carries its user_id; you never store a list of orders on the user.
• Many-to-many (orders and products — each order has many products, each product appears in many orders): relational tables can't express this directly. You introduce a join table (also called a junction or associative table) whose rows pair one key from each side, turning one M:N into two 1:N relationships.

Getting cardinality right is most of schema design. The classic beginner mistake — cramming a comma-separated list of product ids into a column on the orders table — destroys your ability to query, index, or enforce integrity. The join table exists precisely to avoid that.

Constraints — Letting the Database Enforce the Rules

A schema isn't just shape; it's also the rules the data must always satisfy. Encoding these as constraints means the database guarantees them for every writer, forever — far safer than hoping every code path remembers to check:

CREATE TABLE orders (
  id          BIGINT        PRIMARY KEY,                   -- unique, not null
  user_id     BIGINT        NOT NULL REFERENCES users(id), -- FK must point at a real user
  total       NUMERIC(10,2) NOT NULL CHECK (total >= 0),   -- never negative
  email       TEXT          UNIQUE,                        -- no duplicates
  created_at  TIMESTAMPTZ   NOT NULL DEFAULT now()
);

NOT NULL, UNIQUE, CHECK, DEFAULT, and REFERENCES (foreign-key) constraints turn the schema into an active guardian of correctness. Referential integrity — the database refusing to let an order reference a user that doesn't exist, or to delete a user who still has orders — eliminates whole categories of bugs that would otherwise lurk in application code.

Analogy: Constraints are the guardrails on a mountain road. You could trust every driver to stay on the road, or you could install barriers so that even a careless one can't go over the edge. The barrier protects everyone — including the code you'll write next year and forget the rules for.

Model for Your Queries, Not Just Your Data

The deepest principle, and the one that separates textbook modeling from production modeling: design the schema around how the data will be read and written, not only how it's structured. Normalization (Chapter 19) gives you a clean, duplication-free starting point — but the access patterns decide where you bend it.

This is exactly where relational and NoSQL modeling diverge. In a relational database you normalize first and let JOIN reassemble data at query time. In a document or wide-column store there are no cheap joins, so you model the other way around: you study the queries first and shape the data to match them, often duplicating fields so a single read returns everything a screen needs. Neither is "correct" in the abstract — the right model is the one that makes your most frequent and most critical queries fast and your invariants safe.

Analogy: Relational modeling is organizing a warehouse by category and picking items from several aisles per order. Document modeling is pre-packing the most common orders into ready-to-ship boxes. The first is tidy and flexible; the second is faster to ship — and which wins depends entirely on what customers actually order.

With a sound model in place, the next chapter opens the engine itself — how the database turns these tables, keys, and constraints into fast, crash-safe, concurrent operations.

A database looks like magic from the outside: you hand it SQL, it hands back rows. Inside, a handful of clever mechanisms turn unreliable disks and chaotic concurrent access into the ACID guarantees introduced earlier in this part. Understanding them is what lets you diagnose a slow query or reason about what happens during a crash — the difference between using a database and operating one.

How a Query Executes

When you submit SELECT name FROM users WHERE age > 25 ORDER BY name, it passes through a small pipeline:

The optimizer is the brain and the most complex part of any database. For even a moderate query there are many possible plans — use the index on age or scan the whole table? Which join algorithm? In what order? — and the optimizer estimates the cost of each using statistics about the data (how many rows, how values are distributed) and picks the cheapest.

Analogy: The optimizer is a GPS evaluating routes — index scan vs full scan vs scan-then-sort — and choosing the fastest based on live traffic data (table statistics). When statistics go stale, it picks bad routes; this is why ANALYZE / refreshing statistics fixes mysteriously slow queries.

Write-Ahead Logging (WAL)

How does a database keep durability (the D in ACID) when a crash can strike mid-write? The answer is the write-ahead log: before touching the actual data pages, the database appends a record of the change to a sequential log and flushes it to disk. Only then is the transaction considered committed.

This is also a performance trick, not just a safety one: appending to a log is sequential I/O (fast), while updating data pages scattered across disk is random I/O (slow). WAL lets the database confirm a commit quickly and apply the slow random writes lazily in the background.

Analogy: WAL is an aircraft's black box. Even if the plane crashes, the recorder holds an exact account of what happened — so you can reconstruct the final state precisely. On restart the DB redoes committed log entries and undoes uncommitted ones.

Transactions, Concurrency, and Isolation Levels

Isolation (the I) is the hardest guarantee, because letting transactions run concurrently is essential for performance but invites three classic anomalies:

Anomaly	What happens
Dirty read	You read data another transaction wrote but hasn't committed (it may roll back)
Non-repeatable read	You read the same row twice and get different values
Phantom read	You run the same query twice and get a different set of rows

SQL defines isolation levels that trade correctness against concurrency — stronger levels prevent more anomalies but allow less parallelism:

Level	Dirty read	Non-repeatable	Phantom
Read Uncommitted	possible	possible	possible
Read Committed	prevented	possible	possible
Repeatable Read	prevented	prevented	possible
Serializable	prevented	prevented	prevented

The practical lesson: higher isolation = more locking = less throughput. Most databases default to Read Committed or Repeatable Read as a sensible middle ground; you reach for Serializable only where correctness truly demands it (e.g. financial ledgers).

MVCC — Concurrency Without Blocking Readers

Naively, isolation is enforced with locks — but locks make readers and writers wait on each other. Modern databases (PostgreSQL, MySQL's InnoDB, Oracle) instead use Multi-Version Concurrency Control: rather than overwriting a row, a write creates a new version. Each transaction sees a consistent snapshot of the data as of when it started, so readers never block writers and writers never block readers.

Analogy: MVCC is Google Docs version history. You're reading version 5 while a colleague edits version 6. You see a coherent view the whole time, and your reading doesn't freeze their typing.

The cost is that old row versions accumulate and must be cleaned up — PostgreSQL's VACUUM and the dreaded "table bloat" both come straight from this design.

Replication and Sharding

A single machine has limits — on storage, on throughput, and on the bad day when it dies. Two complementary techniques scale beyond it:

Replication copies the same data to multiple servers. It buys availability (a replica takes over if the primary fails) and read scalability (spread reads across copies). The common shape is leader–follower: writes go to the leader, which streams them to followers; reads can be served by any. The catch is replication lag — a follower may briefly serve slightly stale data, which is eventual consistency showing up in practice.

Sharding (partitioning) splits different data across servers — by hash of a key, or by range. It's how you scale writes and store data too large for any single machine. The hard parts: queries that must touch many shards, keeping shards balanced, and picking a shard key that doesn't create hot spots.

Analogy: Replication is printing several copies of the same book — if one library burns down, the others still have it, and many people can read at once. Sharding is splitting an encyclopedia into volumes — A–E on one shelf, F–J on another — so each shelf holds less, but you must know which volume to grab.

Together, replication and sharding are the foundation of every large-scale data system — and the bridge into distributed systems, the subject of the next part.

Every database, under all the SQL and APIs, has a storage engine — the code that actually puts bytes on disk and gets them back. Almost all of them are built on one of two structures, and the choice between them shapes everything about the database's performance.

B+ Trees vs LSM Trees

A B+ tree keeps data sorted in a shallow, wide tree and updates pages in place. Internal nodes hold only keys for navigation; leaf nodes hold the data and are linked together for fast range scans:

An LSM tree takes the opposite approach, optimizing for writes by never updating in place. Writes land in an in-memory memtable, flush to immutable sorted files (SSTables), and are merged in the background by compaction:

The trade-off is fundamental. B+ trees give faster reads and lower amplification (good for OLTP); LSM trees give faster writes via sequential I/O (good for write-heavy and time-series workloads), at the cost of reads checking multiple levels and compaction rewriting data.

Analogy: A B+ tree is a well-organized filing cabinet — finding a file is fast, but filing a new one means inserting it in exactly the right place. An LSM tree is an inbox tray where new documents drop instantly, and a clerk periodically files them into sorted folders. Filing is fast; finding may require checking the tray and the folders.

Write-Ahead Logging

Both engines rely on a write-ahead log for durability. The change is appended to a sequential log and flushed before the data pages are touched:

This is both a safety mechanism (replay the log to recover after a crash) and a performance one — sequential writes to the log are far faster than random writes scattered across data pages, so the database can confirm a commit immediately and update the pages lazily.

Analogy: The WAL is a lab notebook. Before running an experiment (modifying data), you write down exactly what you intend to do. If anything goes wrong, you reconstruct the state from the notebook.

MVCC in Detail

How do PostgreSQL and friends let many transactions read and write concurrently without blocking each other? Multi-Version Concurrency Control keeps multiple versions of each row, tagged with the transactions that created and superseded them:

id	name	xmin (created by)	xmax (superseded by)	visible to
1	Alice	TX 100	TX 200	transactions 100–199
1	Alicia	TX 200	—	transactions 200+

A transaction reads the version valid as of when it began — so reader TX 150 sees "Alice" while reader TX 250 sees "Alicia," and neither blocks the other. The price is accumulating dead row versions, which a background VACUUM must reclaim.

Analogy: MVCC is a wiki with full version history. Every edit creates a new revision; different readers can view different points in time; and the wiki periodically purges ancient revisions nobody could still need (VACUUM).