Data and databases

01 · FILES VS DATABASES

Files vs databases

A program's variables live in RAM, which forgets everything when the power goes (Memory shows why). To keep data you must write it to storage, a disk or SSD, and the simplest way is a file. Here is a tiny shop's customer list as a CSV file (comma-separated values), and the two things you'll want to do with it: find something, and change something.

// A file is just bytes. Here is a tiny "database" kept as CSV text.
let file = `id,name,city
1,Ana,Oslo
2,Ben,Lima
3,Chen,Oslo
4,Dara,Pune
5,Eli,`;
​
// To find Chen, read from the start until you reach the line.
function find(name) {
  let bytesRead = 0;
  for (const line of file.split("\n")) {
    bytesRead += line.length + 1;
    const [id, n, city] = line.split(",");
    if (n === name) return { id, city, bytesRead };
  }
  return { bytesRead };
}
console.log(find("Chen"));
​
// To change one city, write the whole file out again.
function setCity(name, city) {
  file = file.split("\n").map((line) => {
    const cells = line.split(",");
    return cells[1] === name ? cells[0] + "," + name + "," + city : line;
  }).join("\n");
}
setCity("Ben", "Quito");
console.log(file);
console.log("rewrote", file.length, "bytes to change one city");

That works for a hundred rows. It falls apart as data grows and more people use it at once:

• Finding means reading from the start. The 3D shows the read head crawling byte by byte.
• Changing means rewriting. If the power fails halfway, the file is half old and half new.
• Two writers at once overwrite each other's changes.
• No rules: nothing stops a typo, a missing comma, or a city in the price column. A name like Lee, Jr breaks the format itself.

A database is a program that owns the files and fixes all four. It stores data in fixed-size pages (4 KB by default in SQLite, 8 KB in PostgreSQL, 16 KB in MySQL's InnoDB) and keeps an index that says which page holds what. On the right of the 3D, the database asks the index, then reads one page: two reads, however big the table. It also enforces rules, lets many programs work at once, and survives crashes. The rest of this chapter is how.

02 · TABLES AND KEYS

Tables, rows and keys

In 1970 Edgar F. Codd, at IBM, proposed keeping all data in tables (he called them relations). It is still how most data in the world is stored. A table has named columns, each holding one kind of value, and rows, one per thing. This is the sample shop the whole chapter uses, in SQL's own words:

CREATE TABLE customers (
  id    INTEGER PRIMARY KEY,
  name  TEXT NOT NULL,
  city  TEXT
);
 
CREATE TABLE orders (
  id          INTEGER PRIMARY KEY,
  customer_id INTEGER NOT NULL REFERENCES customers(id),
  item        TEXT,
  total       INTEGER,
  day         TEXT
);

Two columns matter more than the rest:

• A primary key identifies each row: unique, never empty, and it shouldn't change. Names make bad keys (two people called Ana, or Ana marries and changes hers), so most tables use a number.
• A foreign key is a column that holds another table's primary key. orders.customer_id = 3 means "this order belongs to customer 3". In the 3D, each order is wired to its customer.

The point of declaring keys is that the database enforces them, so no program, however buggy, can store an order for a customer who doesn't exist. Here are those rules written by hand in JavaScript:

const customers = new Map();          // primary key → row
function insertCustomer(row) {
  if (customers.has(row.id)) throw new Error("duplicate primary key " + row.id);
  customers.set(row.id, row);
}
​
const orders = [];
function insertOrder(row) {             // customer_id is a foreign key
  if (!customers.has(row.customer_id)) throw new Error("no customer " + row.customer_id);
  orders.push(row);
}
​
insertCustomer({ id: 1, name: "Ana", city: "Oslo" });
insertCustomer({ id: 2, name: "Ben", city: "Lima" });
insertOrder({ id: 101, customer_id: 1, total: 30 });
insertOrder({ id: 103, customer_id: 2, total: 25 });
console.log(orders.length, "orders saved");
​
try {
  insertCustomer({ id: 1, name: "Someone else" });
} catch (e) {
  console.log("rejected:", e.message);
}
insertOrder({ id: 110, customer_id: 9, total: 99 });   // who is customer 9?

And here is the real thing. Run it: the first insert works, the second is refused.

-- The database guards its own rules. Try each insert:
INSERT INTO orders (id, customer_id, item, total, day)
VALUES (109, 2, 'tea', 6, '2026-03-05');
​
INSERT INTO orders (id, customer_id, item, total, day)
VALUES (110, 9, 'cake', 99, '2026-03-05');

03 · SELECT · WHERE

Asking questions: SELECT and WHERE

SQL (Structured Query Language) is how you talk to a relational database. It grew out of SEQUEL, designed at IBM in 1974, and is now an ISO standard. It is declarative: you describe the answer you want, and the database works out how to get it. This console runs a small SQL engine written for this page, in your browser. Edit anything and press Run SQL (or Ctrl+Enter):

SELECT * FROM customers;

SELECT picks columns, FROM picks the table, WHERE keeps only the rows that pass a test. In the 3D, the scan bar tests each customer; the two in Oslo pass and step forward, then SELECT name drops the other columns.

SELECT name, city
FROM customers
WHERE city = 'Oslo';

Under the words, it is the same as two array methods you already know:

const customers = [
  { id: 1, name: "Ana", city: "Oslo" },
  { id: 2, name: "Ben", city: "Lima" },
  { id: 3, name: "Chen", city: "Oslo" },
  { id: 4, name: "Dara", city: "Pune" },
  { id: 5, name: "Eli", city: null },
];
​
// SELECT name FROM customers WHERE city = 'Oslo'
const result = customers
  .filter((c) => c.city === "Oslo")      // WHERE: keep some rows
  .map((c) => ({ name: c.name }));       // SELECT: keep some columns
​
console.table(result);

SQL has more: AND, OR, ORDER BY to sort, LIMIT to take the first few. A query is read in this order, even though it is written differently: FROM, WHERE, GROUP BY, HAVING, SELECT, ORDER BY, LIMIT.

-- Try each one: change, run, predict
SELECT id, item, total
FROM orders
WHERE total >= 20 AND item <> 'cake'
ORDER BY total DESC;

NULL: the value that means "unknown"

Eli's city is NULL: nobody knows it. SQL takes that literally. Is an unknown city equal to Oslo? Unknown. Is it different from Oslo? Also unknown. WHERE keeps a row only when the test is true, so Eli falls through every comparison. Predict all three results, then run:

-- Eli's city is NULL: unknown. Which rows come back?
SELECT name FROM customers WHERE city = NULL;
SELECT name FROM customers WHERE city <> 'Oslo';
SELECT name FROM customers WHERE city IS NULL;

Your turn. Show the id and total of every order of tea or coffee that cost more than 10, biggest first.

SELECT id, total
FROM orders
WHERE …;

04 · JOIN

JOIN: putting tables back together

Orders only store a customer's id. To print "Ana bought coffee" you need both tables at once. JOIN pairs up rows whose keys match:

SELECT customers.name, orders.item, orders.total
FROM orders
JOIN customers ON customers.id = orders.customer_id
ORDER BY orders.id;

How does the database find the pairs? The obvious way, comparing every order with every customer, is a nested loop: 8 × 5 = 40 comparisons here, but a million × a million in a big shop. So for a join on = a database usually builds a hash table of one side and probes it with the other, which is what the 3D shows: customers flash once as they go into the hash table, then each order finds its customer in one step.

const customers = [
  { id: 1, name: "Ana" }, { id: 2, name: "Ben" }, { id: 3, name: "Chen" },
  { id: 4, name: "Dara" }, { id: 5, name: "Eli" },
];
const orders = [
  { id: 101, customer_id: 1, total: 30 }, { id: 102, customer_id: 3, total: 12 },
  { id: 103, customer_id: 2, total: 25 }, { id: 104, customer_id: 1, total: 8 },
  { id: 105, customer_id: 4, total: 40 }, { id: 106, customer_id: 3, total: 20 },
  { id: 107, customer_id: 2, total: 5 },  { id: 108, customer_id: 1, total: 15 },
];
​
// 1. Nested loop: compare every order with every customer.
let compared = 0;
const slow = [];
for (const o of orders) {
  for (const c of customers) {
    compared++;
    if (c.id === o.customer_id) slow.push({ name: c.name, total: o.total });
  }
}
console.log("nested loop:", compared, "comparisons");
​
// 2. Hash join: build a Map of customers once, then one lookup per order.
let steps = 0;
const byId = new Map();
for (const c of customers) { byId.set(c.id, c); steps++; }
const fast = [];
for (const o of orders) {
  steps++;
  const c = byId.get(o.customer_id);
  if (c) fast.push({ name: c.name, total: o.total });
}
console.log("hash join:", steps, "steps, same", fast.length, "rows");
console.table(fast);

Notice Eli is missing from the result: he has no orders, so nothing matched him. A LEFT JOIN keeps every row of the left table, and fills the missing side with NULL:

-- LEFT JOIN keeps customers with no orders (Eli)
SELECT c.name, COUNT(o.id) AS orders
FROM customers AS c
LEFT JOIN orders AS o ON o.customer_id = c.id
GROUP BY c.name
ORDER BY orders DESC, c.name;

Your turn. List every item Chen bought, with its total. (Hint: join, then filter on the customer's name.)

SELECT …
FROM orders
JOIN customers ON customers.id = orders.customer_id
WHERE …;

05 · GROUP BY

GROUP BY: from rows to answers

Questions like "how much did each city spend?" need rows squashed into summaries. Aggregate functions do the squashing: COUNT, SUM, AVG, MIN, MAX. GROUP BY says which rows go together. In the 3D, each joined row drops into its city's bucket, and each bucket becomes one tower as tall as its sum.

SELECT c.city, COUNT(*) AS orders, SUM(o.total) AS spent
FROM orders AS o
JOIN customers AS c ON c.id = o.customer_id
GROUP BY c.city
ORDER BY spent DESC;

The same thing in JavaScript is a Map of buckets:

const rows = [   // the JOIN's output: one row per order, with the city
  { city: "Oslo", total: 30 }, { city: "Oslo", total: 12 }, { city: "Lima", total: 25 },
  { city: "Oslo", total: 8 },  { city: "Pune", total: 40 }, { city: "Oslo", total: 20 },
  { city: "Lima", total: 5 },  { city: "Oslo", total: 15 },
];
​
// GROUP BY city: one bucket per distinct city...
const groups = new Map();
for (const row of rows) {
  if (!groups.has(row.city)) groups.set(row.city, []);
  groups.get(row.city).push(row);
}
​
// ...then the aggregates squash each bucket to one row.
const result = [];
for (const [city, bucket] of groups) {
  const spent = bucket.reduce((sum, r) => sum + r.total, 0);
  result.push({ city, orders: bucket.length, spent });
}
result.sort((a, b) => b.spent - a.spent);   // ORDER BY spent DESC
console.table(result);

One rule trips everyone up: after grouping, each row of the result is a whole group, so every column you select must either be in the GROUP BY or inside an aggregate. Asking for name per city makes no sense, since Oslo has two. Try adding c.name to the SELECT above. (PostgreSQL refuses, like this engine; SQLite quietly picks one name for you, which hides bugs.)

WHERE filters rows before they are grouped. To filter whole groups after, use HAVING:

-- WHERE filters rows before grouping; HAVING filters groups after
SELECT item, COUNT(*) AS sold, AVG(total) AS average
FROM orders
WHERE day >= '2026-03-02'
GROUP BY item
HAVING COUNT(*) >= 2;

Your turn. How much did each customer spend? Show name and the sum, keep only those who spent more than 30, biggest first.

SELECT …
FROM orders
JOIN customers ON customers.id = orders.customer_id
GROUP BY …;

06 · INDEXES

Indexes: B-trees

With no index, WHERE id = 97 has one option: read every page of the table and test every row. That is a full scan, and the bottom half of the 3D loop shows it walking all 16 leaf pages. An index is a second structure, kept sorted, that leads straight to the right page. Almost every database uses the same one: the B-tree, invented by Rudolf Bayer and Edward McCreight in 1972.

A B-tree is a tree of pages. Each page holds many sorted keys, and between them, pointers to the pages below:

• The root page here holds 40, 80 and 120, so it splits the keys into four ranges: under 40, 40 to 79, 80 to 119, 120 and up.
• Each branch page splits its range four ways again.
• The leaf pages hold the keys themselves (and in a real table, the rows or where to find them). In the B+tree variant nearly every database uses, leaves are also linked in order, so a range like BETWEEN 40 AND 70 finds the first leaf, then walks sideways.

To find 97, the lookup reads the root (97 is in 80–119), one branch (90–99), one leaf: 3 pages, against 16 for the scan. The gap grows fast. A real 8 KB page holds a few hundred keys, so each level multiplies the reach by a few hundred: 3 levels reach tens of millions of rows, 4 reach billions. Build one with a million keys:

const PAGE = 100;             // keys per page (real 8 KB pages hold hundreds)
const N = 1000000;            // one million rows, keys 0, 3, 6, 9, ...
​
// Bulk-load a B+tree: fill the leaf pages in order, then build each level above.
let level = [];
for (let i = 0; i < N; i += PAGE) {
  const keys = [];
  for (let k = i; k < i + PAGE; k++) keys.push(k * 3);
  level.push({ leaf: true, keys });
}
const leafPages = level.length;
const firstKey = (node) => (node.leaf ? node.keys[0] : firstKey(node.kids[0]));
let height = 1;
while (level.length > 1) {
  const up = [];
  for (let i = 0; i < level.length; i += PAGE) {
    const kids = level.slice(i, i + PAGE);
    up.push({ leaf: false, kids, keys: kids.slice(1).map(firstKey) });
  }
  level = up;
  height++;
}
const root = level[0];
​
// A lookup reads one page per level: pick the child whose range holds the key.
function lookup(key) {
  let node = root;
  let pagesRead = 1;
  while (!node.leaf) {
    let i = 0;
    while (i < node.keys.length && key >= node.keys[i]) i++;
    node = node.kids[i];
    pagesRead++;
  }
  return { key, found: node.keys.includes(key), pagesRead };
}
​
console.log("leaf pages:", leafPages, "· levels:", height);
console.log(lookup(2999997));
console.log(lookup(1234567));
console.log("without the index, a search may read all", leafPages, "pages");

This page's SQL engine builds real B+trees too (with small pages of 64 keys), and EXPLAIN shows what a query did. Here are 20,000 page visits, searched before and after an index:

-- 20,000 page visits. Who is user 4242?
EXPLAIN SELECT * FROM visits WHERE user_id = 4242;
​
CREATE INDEX idx_visits_user ON visits (user_id);
​
EXPLAIN SELECT * FROM visits WHERE user_id = 4242;
SELECT * FROM visits WHERE user_id = 4242;

Indexes aren't free. Every INSERT, UPDATE and DELETE must update every index on the table, and each index takes space. Index the columns you search, join and sort on; leave the rest. Real databases show their plans the same way: EXPLAIN in PostgreSQL and MySQL, EXPLAIN QUERY PLAN in SQLite.

07 · TRANSACTIONS

Transactions and ACID

Moving 30 from Ana to Ben is two writes: take 30 from Ana, give 30 to Ben. If the program crashes between them, 30 has vanished. A transaction groups writes so they happen all together or not at all. You open one with BEGIN and finish with COMMIT, or undo everything with ROLLBACK.

SELECT * FROM accounts;
​
-- Move 30 from Ana to Ben: two writes, one transaction
BEGIN;
UPDATE accounts SET balance = balance - 30 WHERE owner = 'Ana';
UPDATE accounts SET balance = balance + 30 WHERE owner = 'Ben';
COMMIT;
​
SELECT * FROM accounts;

The accounts table has a rule: CHECK (balance >= 0). Now Ana tries to send 500. Ben's +500 succeeds first, then Ana's −500 breaks the rule. Does Ben keep the money?

-- Ana tries to send 500. The CHECK (balance >= 0) rule says no.
BEGIN;
UPDATE accounts SET balance = balance + 500 WHERE owner = 'Ben';
UPDATE accounts SET balance = balance - 500 WHERE owner = 'Ana';
COMMIT;
​
-- Did Ben keep the 500 he was given first?
SELECT * FROM accounts;

The guarantees a transaction gives are known by the acronym ACID, coined by Theo Härder and Andreas Reuter in 1983:

• Atomic: all of it or none of it. No half-done transfer is ever left behind.
• Consistent: every transaction takes the database from one valid state to another; rules like keys and CHECKs are never broken at a commit.
• Isolated: transactions running at the same time don't see each other's half-done work. (How strictly is a setting: the next section.)
• Durable: once COMMIT returns, the change survives a crash or power cut.

How can a database promise that, when power can fail at any instant? With a write-ahead log. Before changing any data page, it appends a record of the change to a log, and at COMMIT it forces the log to disk. After a crash, recovery reads the log: changes from committed transactions are redone, changes from uncommitted ones are undone. The 3D runs both endings: a commit flushed to the log on disk, then a power cut halfway, after which recovery finds no COMMIT and puts Ana's 100 back.

const db = { ana: 100, ben: 50 };
​
function transfer(from, to, amount, crash = false) {
  const undo = [];                              // the log: how to put things back
  const write = (key, value) => {
    undo.push([key, db[key]]);                  // log first...
    db[key] = value;                            // ...then change the data
  };
  try {
    write(from, db[from] - amount);
    if (db[from] < 0) throw new Error("CHECK failed: balance >= 0");
    if (crash) throw new Error("power cut!");
    write(to, db[to] + amount);
    console.log("COMMIT  ", JSON.stringify(db));
  } catch (e) {
    for (const [key, value] of undo.reverse()) db[key] = value;   // all or nothing
    console.log("ROLLBACK", JSON.stringify(db), "(" + e.message + ")");
  }
}
​
transfer("ana", "ben", 30);
transfer("ana", "ben", 30, true);
transfer("ana", "ben", 500);
console.log("money in the system:", db.ana + db.ben);

08 · ISOLATION

Isolation: when transactions overlap

A busy database runs many transactions at once; running them strictly one after another would be far too slow. The trouble starts when two touch the same data. Two shoppers buy the last mugs at the same moment, and each program does "read the stock, then write stock − 1":

let stock = 10;   // one row in the database: 10 mugs left
​
// Each shopper's program does: read stock, then write stock - 1.
function run(schedule) {
  stock = 10;
  const seen = {};
  for (const [tx, op] of schedule) {
    if (op === "read") seen[tx] = stock;
    if (op === "write") stock = seen[tx] - 1;
    console.log(tx, op.padEnd(5), "stock =", stock);
  }
  return stock;
}
​
console.log("one after the other →", run([["T1", "read"], ["T1", "write"], ["T2", "read"], ["T2", "write"]]));
console.log("interleaved        →", run([["T1", "read"], ["T2", "read"], ["T1", "write"], ["T2", "write"]]));

Each kind of overlap problem has a name. The SQL standard defines isolation levels by which ones they rule out; a stricter level is safer, and usually slower.

Write skew is the sneaky one. A hospital needs at least one doctor on call. Two doctors on call both feel ill; each transaction checks "is someone else on call?", sees yes, and signs off. Both commit. Nobody is on call. (The example is from Martin Kleppmann's Designing Data-Intensive Applications.)

Defaults differ, so know yours: PostgreSQL runs at Read Committed, MySQL's InnoDB at Repeatable Read, and SQLite's transactions are serializable. Ways to stop the lost update:

• Let the database do the arithmetic in one statement: UPDATE items SET stock = stock - 1 WHERE id = 7.
• Lock the row while you work: SELECT stock FROM items WHERE id = 7 FOR UPDATE makes the second shopper wait, as in the second loop of the 3D.
• Check a version number when you write, and retry if it changed (optimistic concurrency):

let row = { stock: 10, version: 1 };
​
// Optimistic concurrency: write only if nobody changed the row since you read it.
function save(seen, newStock) {
  if (row.version !== seen.version) return false;   // someone got there first
  row = { stock: newStock, version: seen.version + 1 };
  return true;
}
​
const t1 = { ...row };                 // both shoppers read version 1
const t2 = { ...row };
console.log("T1 saves:", save(t1, t1.stock - 1));
console.log("T2 saves:", save(t2, t2.stock - 1), "← conflict, so read again");
const again = { ...row };
console.log("T2 retries:", save(again, again.stock - 1));
console.log(row);

Most modern databases (PostgreSQL, MySQL, Oracle) use MVCC, multi-version concurrency control: they keep old versions of changed rows, so a reader sees a consistent snapshot and never waits for a writer. PostgreSQL's Serializable level adds a check on top that aborts one of two transactions whose combination couldn't have happened one at a time; your code must then retry it.

09 · NORMALIZATION

Normalization: each fact in one place

Why split customers and orders at all? Why not one wide table with everything? Look at it: Ana's city appears on every one of her orders. That repetition causes three kinds of trouble, called anomalies:

• Update: Ana moves, you update two of her three rows, and now the database says she lives in two cities.
• Insert: you can't record a new customer until they order something.
• Delete: cancel Dara's only order and you lose that Dara exists at all.

// One wide table: every order repeats its customer's details.
const flat = [
  { order: 101, customer: "Ana", city: "Oslo", total: 30 },
  { order: 104, customer: "Ana", city: "Oslo", total: 8 },
  { order: 108, customer: "Ana", city: "Oslo", total: 15 },
  { order: 103, customer: "Ben", city: "Lima", total: 25 },
];
​
// Update anomaly: Ana moves, and one copy gets missed.
const broken = flat.map((r) => ({ ...r }));
broken[0].city = "Bergen";
broken[1].city = "Bergen";
const anaCities = new Set(broken.filter((r) => r.customer === "Ana").map((r) => r.city));
console.log("Where does Ana live?", [...anaCities]);
​
// Normalize: each fact in exactly one place, linked by a key.
const customers = new Map();
const orders = [];
for (const r of flat) {
  if (!customers.has(r.customer)) customers.set(r.customer, { id: customers.size + 1, name: r.customer, city: r.city });
  orders.push({ id: r.order, customer_id: customers.get(r.customer).id, total: r.total });
}
customers.get("Ana").city = "Bergen";   // one write, and it's true everywhere
console.table([...customers.values()]);
console.table(orders);

Normalization is the discipline of splitting tables until every fact is stored exactly once, joined back by keys. In the 3D the repeated cells flash red, then the wide table splits: the city moves to a customers table, once per customer, and the order keeps only a customer_id. The classic steps are the normal forms:

• 1NF: one value per cell. No lists of items squeezed into one column.
• 2NF: no column depends on just part of a multi-column key.
• 3NF: no column depends on another non-key column (city depends on the customer, not on the order).

William Kent summed up 3NF in 1983: every non-key column must provide a fact about "the key, the whole key, and nothing but the key".

Rules are there to be broken on purpose. Joins cost time, so systems that read far more than they write sometimes store a copy on purpose, like an order's total next to its items, or a whole report table rebuilt every night. That is denormalization, and it means taking on the job of keeping the copies in step.

10 · NOSQL

NoSQL: other shapes of data

Relational databases are the default for good reason, but not every problem is shaped like tables. From the mid-2000s, companies serving huge traffic built stores that gave up joins or strict transactions in exchange for spreading data across many machines and simpler, faster access paths. Google's Bigtable (2006) and Amazon's Dynamo (2007) papers set the pattern. They are grouped as NoSQL, usually read as "not only SQL". Four families:

// KEY-VALUE: one big Map. Get and put by key, nothing else (Redis, DynamoDB).
const kv = new Map();
kv.set("session:9f2c", { user: 1, cart: ["coffee", "cake"] });
console.log("key-value  →", kv.get("session:9f2c").cart);
​
// DOCUMENT: a whole nested record fetched in one read (MongoDB, Firestore).
const order = {
  _id: 101,
  customer: { id: 1, name: "Ana" },
  items: [{ sku: "coffee", qty: 2 }, { sku: "cake", qty: 1 }],
};
console.log("document   →", order.customer.name, "bought", order.items.length, "things");
​
// GRAPH: nodes and edges; queries walk the edges (Neo4j).
const follows = { ana: ["ben", "chen"], ben: ["dara"], chen: ["dara", "eli"], dara: [], eli: ["ana"] };
const twoHops = (who) => [...new Set(follows[who].flatMap((f) => follows[f]))].filter((x) => x !== who);
console.log("graph      → friends of friends of ana:", twoHops("ana"));
​
// WIDE-COLUMN: rows sorted by key, each with its own columns (Cassandra, Bigtable).
const readings = new Map([
  ["oslo#2026-03-01T10", { temp: 4.1 }],
  ["oslo#2026-03-01T11", { temp: 4.6, wind: 7 }],
  ["pune#2026-03-01T10", { temp: 31.0, humidity: 62 }],
]);
const oslo = [...readings.keys()].sort().filter((k) => k.startsWith("oslo#"));
console.log("wide-column→ oslo rows:", oslo.length, readings.get(oslo[1]));

The trade-offs are real. A document store makes reading a whole order trivial, but asking "which customers bought cake?" across documents is harder than a JOIN. Many NoSQL systems relax consistency across machines so that they keep working when the network splits. Spreading data over machines (sharding) and keeping copies (replication) is its own subject; the Cluster page shows it in hardware.

11 · CACHING

Caching: remember the answer

The fastest query is the one you don't run. Reading main memory takes about 100 nanoseconds; a seek on a spinning disk about 8 milliseconds, some 80,000 times longer. SSDs and networks sit in between, but the shape is the same: the same memory hierarchy that puts caches in every CPU. A cache keeps recent answers somewhere fast, usually in RAM, often in a store like Redis or Memcached in front of the database.

The usual pattern is cache-aside: look in the cache; on a hit, done; on a miss, ask the database and store the answer for next time. A cache is small, so when it is full something must go. LRU (least recently used) evicts whatever has gone unused longest. The 3D plays this exact request sequence through a 3-slot cache:

let dbReads = 0;
function slowDbGet(id) {             // pretend this costs a network trip and a disk read
  dbReads++;
  return { id, name: "user " + id };
}
​
const CAPACITY = 3;
const cache = new Map();             // a Map keeps insertion order: oldest first
let hits = 0, misses = 0;
​
function get(id) {
  if (cache.has(id)) {
    hits++;
    const v = cache.get(id);
    cache.delete(id);                // move it to the newest end
    cache.set(id, v);
    return v;
  }
  misses++;
  const v = slowDbGet(id);
  cache.set(id, v);
  if (cache.size > CAPACITY) cache.delete(cache.keys().next().value);   // evict the least recently used
  return v;
}
​
for (const id of [1, 2, 1, 3, 1, 4, 2, 1, 1, 5]) get(id);
console.log({ hits, misses, dbReads, hitRatio: hits / (hits + misses) });
console.log("in the cache now:", [...cache.keys()]);

The hard part is not storing answers but knowing when they're wrong. When the database changes, the cached copy is stale until it is removed (invalidated) or expires (a TTL, time to live):

const db = new Map([["price:tea", 3]]);
const cache = new Map();
​
function read(key) {                 // cache-aside: try the cache, else the database
  if (cache.has(key)) return cache.get(key);
  const v = db.get(key);
  cache.set(key, v);
  return v;
}
​
console.log("first read:", read("price:tea"));
db.set("price:tea", 4);              // someone updates the database...
console.log("after update:", read("price:tea"), "← stale!");
cache.delete("price:tea");           // ...so the copy must be invalidated
console.log("after invalidate:", read("price:tea"));

Databases cache too: every one keeps recently used pages in a buffer pool in RAM, so a hot B-tree root is almost never read from disk at all.

12 · CHOOSING

Choosing: which database when

There is no best database, only a best fit. A rule of thumb many engineers use: start relational, and move only when you can name the problem it doesn't solve.

Many real systems use several: PostgreSQL as the source of truth, Redis as a cache, a search engine for text, a columnar warehouse for reports. Each copy is a cache with an invalidation problem, so add them only when you must. For how these pieces fit together across machines, see Systems and Cluster.