Databases from First Principles: How Storage, Indexes and Transactions Really Work

Here is the cleanest definition of a database I know: it is a program that turns a file on disk into something you can trust. Everything else, from SQL to indexes to replication, exists because a plain file breaks the moment real users show up.

This post is part of the Engineering Foundations series and picks up where Backend Engineering from First Principles left off. That post called the database your source of truth. This one opens the box and shows how it keeps that promise, so you can reason about it in an interview or an incident instead of guessing.

Because a JSON file has no answer for three problems: two writers at once, a crash halfway through a write, and finding one record fast. Say you keep a cloud kitchen's orders in orders.json. Each request reads the file, adds an order and writes the whole thing back. It works on your laptop. Then lunch rush hits.

• Concurrency: two requests read the file at the same moment, each adds its order, each writes back. The second write silently erases the first order.
• Crashes: the process dies while writing a 40 MB file. Now there's half a JSON document on disk and every request after restart fails to parse it.
• Lookups: finding order 98123 means parsing the entire file. Fine at 10 orders, painful at 10 million.
• Write cost: changing one field rewrites the whole file.

Every big idea inside a database fixes one of these. Pages fix the write cost. The write-ahead log fixes crashes. Indexes fix lookups. Transactions and MVCC fix concurrency. Keep that list in mind and the rest of this post will feel obvious.

A page is the fixed-size block a database reads and writes as one unit. PostgreSQL stores every table and index as an array of 8 kB pages; MySQL InnoDB uses 16 KB pages by default. Fixed blocks turn 'update one row' into 'rewrite one page' instead of 'rewrite the whole file'.

The buffer pool is a chunk of RAM where the database caches pages (PostgreSQL calls it shared_buffers). To read a row, the engine first checks whether its page is already in memory. To update a row, it changes the page in memory and marks it dirty. The dirty page goes back to disk later, not at commit time.

That should worry you. If the change only lives in RAM and the power goes out, is your committed order gone? It isn't, and the reason is the most important idea in this post.

A write-ahead log (WAL) is an append-only file where the database records every change before it touches the real data pages. Log first, data later. On commit, only the log has to be flushed to disk with fsync, not every page the transaction touched.

It's a clever trade. Writing scattered pages all over the disk is slow; appending a few hundred bytes to one file is fast, and one fsync can commit many concurrent transactions together. So commits become durable through the cheap sequential log, and a background process (the checkpointer in PostgreSQL) writes dirty pages home whenever it's convenient.

After a crash, the server finds the last checkpoint and replays the WAL forward from there. Pages that never reached disk get rebuilt; transactions with no commit record are treated as if they never happened. The same log later powers replication, point-in-time recovery and change data capture.

Neither wins everywhere. B-trees suit read-heavy work with range queries and power PostgreSQL, MySQL InnoDB and SQLite. LSM trees suit write-heavy work and power RocksDB, Cassandra and LevelDB.

A B-tree is a balanced tree of pages: internal pages hold sorted keys pointing to children, leaf pages hold keys and row locations. Each page holds hundreds of keys, so the tree is shallow. A handful of page reads finds any key in a table of hundreds of millions of rows, and the top pages are usually already in the buffer pool.

An LSM tree (log-structured merge tree, described by O'Neil and colleagues in 1996) never updates data in place. Writes go to an in-memory sorted memtable plus a WAL. When the memtable fills, it's flushed as an immutable sorted file called an SSTable. Background compaction merges SSTables and throws away overwritten and deleted values.

Reads check the memtable, then SSTables from newest to oldest. Each SSTable carries a Bloom filter that cheaply answers 'this key is definitely not here', so most files are skipped. Still, a lookup can touch more places than in a B-tree.

My rule of thumb: a normal product backend runs on a B-tree, and it should. Reach for LSM when writes clearly dominate, like ingesting app events faster than one B-tree primary can keep up with.

An index is a separate sorted structure, usually a B-tree, that maps column values to the location of matching rows. Without one, the database reads every page of the table (a sequential scan). With one, it walks a few index pages straight to the row.

Now the bill. Every INSERT adds an entry to every index on the table, every DELETE removes one, and every UPDATE of an indexed column moves entries around. Each of those dirties index pages and writes WAL.

• Write latency: a table with eight indexes does nine structure updates per insert instead of one.
• Page splits: inserting into a full B-tree page splits it in two. Random keys like UUIDv4 cause this constantly; time-ordered keys like bigserial or UUIDv7 mostly append at the right edge.
• Memory and replication: indexes compete with table pages for the buffer pool, and more WAL per write means more for replicas to replay.

PostgreSQL softens this with heap-only tuple (HOT) updates: if no indexed column changes and the new row version fits on the same page, the indexes aren't touched. One more reason not to index columns that change constantly.

A composite index covers several columns, sorted by the first, then by the second within each first value, and so on. Think of a phone book sorted by last name, then first name. Finding all the Sharmas is fast, finding Rahul Sharma is faster, but finding every Rahul means reading the whole book.

That's the leftmost prefix rule: an index on (user_id, status, created_at) efficiently serves filters on user_id, on user_id and status, or on all three, but not on status alone. MySQL documents this rule directly. PostgreSQL can still scan the index without the leading column, and version 18 added skip scan for leading columns with few distinct values, but it's most efficient when the leading columns are constrained.

Here's EXPLAIN in PostgreSQL for the 'My orders' screen of a food delivery app: a user's paid orders, newest first.

CREATE INDEX idx_orders_user_status_created
  ON orders (user_id, status, created_at);

-- Uses the index: equality on the two leading columns,
-- and created_at is already sorted inside that slice.
EXPLAIN SELECT id, total, created_at
FROM orders
WHERE user_id = 42 AND status = 'PAID'
ORDER BY created_at DESC
LIMIT 20;

-- Limit  (cost=0.43..24.87 rows=20 width=24)
--   ->  Index Scan Backward using idx_orders_user_status_created on orders
--         Index Cond: ((user_id = 42) AND (status = 'PAID'::text))

-- Skips the leading column, so the planner falls back to scanning the table.
EXPLAIN SELECT count(*) FROM orders WHERE status = 'PAID';

-- Aggregate
--   ->  Seq Scan on orders
--         Filter: (status = 'PAID'::text)

Your cost numbers will differ, and on a small table the planner may choose differently. Read the shape: Index Cond means the index narrowed the search; Filter under a Seq Scan means it read everything and discarded rows. There's also no Sort node in the first plan, because the index already returns rows in created_at order.

A transaction is a group of reads and writes that the database treats as one unit: all of it happens or none of it does. ACID names its four promises, and each maps to a mechanism you've already met.

• Atomicity: all or nothing. If a UPI transfer debits one account and the credit fails, the debit is rolled back.
• Consistency: constraints like UNIQUE, foreign keys and CHECK (balance >= 0) keep data valid, though most business rules are still your code's job.
• Isolation: concurrent transactions interfere only as much as the chosen isolation level allows.
• Durability: once COMMIT returns, the change survives a crash, thanks to the WAL fsync.

BEGIN;
UPDATE accounts SET balance = balance - 500 WHERE id = 1 AND balance >= 500;
-- in your code: if 0 rows were updated, ROLLBACK
UPDATE accounts SET balance = balance + 500 WHERE id = 2;
INSERT INTO transfers (from_id, to_id, amount) VALUES (1, 2, 500);
COMMIT;

Isolation levels trade correctness for concurrency: stronger levels block or abort more transactions, weaker ones let more strange interleavings through. The anomalies first.

• Dirty read: you read another transaction's uncommitted change. If it rolls back, you acted on data that never existed.
• Non-repeatable read: you read the same row twice in one transaction and get different values because someone committed in between.
• Phantom read: you run the same range query twice ('free seats in coach S4') and rows appear or vanish because someone inserted or deleted in that range.
• Lost update: two transactions read the same value, both compute a new one, both write. The second silently overwrites the first. This is how the last Tatkal seat gets sold twice.

Two lessons. Your database's default level is weaker than you think, so lost updates are on you. And stronger levels don't make conflicts disappear, they turn them into errors: PostgreSQL will say 'could not serialize access due to concurrent update', and your code must retry the whole transaction.

For the classic stock-counter bug you usually don't need a stronger level. You need to stop doing read-modify-write in application code.

-- Buggy: two requests both read stock = 1, both write 0, two orders placed.
SELECT stock FROM products WHERE id = 7;      -- app sees 1
UPDATE products SET stock = 0 WHERE id = 7;   -- app writes 1 - 1

-- Fix 1: let the database do the math atomically, with a guard.
UPDATE products SET stock = stock - 1
WHERE id = 7 AND stock > 0;                   -- 0 rows updated = sold out

-- Fix 2: lock the row for the rest of the transaction.
SELECT stock FROM products WHERE id = 7 FOR UPDATE;

MVCC (multi-version concurrency control) means the database keeps several versions of a row and shows each transaction the version that matches its snapshot. An update creates a new version instead of overwriting, so, as the PostgreSQL docs put it, reading never blocks writing and writing never blocks reading.

Row: order 501

  v1  status = PLACED     created by tx 100, replaced by tx 230
  v2  status = PAID       created by tx 230, replaced by tx 410
  v3  status = DELIVERED  created by tx 410, current

  tx 300 (snapshot taken before 410 committed) reads -> v2  PAID
  tx 500 (snapshot taken after 410 committed)  reads -> v3  DELIVERED

  Nobody waited. Old versions are cleaned up later (VACUUM in PostgreSQL,
  undo log purge in InnoDB) once no snapshot can still see them.

This explains a common production surprise: a transaction left open for hours holds an old snapshot, cleanup can't remove dead versions, and tables bloat while queries slow down. PostgreSQL stores old versions in the table itself; InnoDB rebuilds them from undo logs. Same idea, different plumbing.

Replication copies every change from the primary to replicas, usually by streaming the WAL. You get a standby that can take over if the primary dies, and extra servers for read queries.

The catch: PostgreSQL streaming replication is asynchronous by default. The primary commits, tells your app 'done', and ships WAL a moment later. The docs say the delay is typically under a second when the standby keeps up; under heavy load or long-running replica queries it can be much longer.

Here's the bug as an example. A user changes their display name and hits save. The API writes to the primary and redirects to the profile page, whose read goes to a replica that hasn't replayed the change yet. The user sees the old name, assumes the save failed, and edits again. Support gets a ticket saying profile save is broken. It isn't broken, it's lagging.

The guarantee the user expected is called read-your-writes consistency. Fixes, simplest first:

1. 1

   Read your own data from the primary

   Profile, settings and 'my orders' read from the primary; browse and search use replicas.

2. 2

   Pin a user to the primary after a write

   Set a short-lived flag so that user reads from the primary for the next few seconds.

3. 3

   Track the WAL position

   Note pg_current_wal_lsn() on the primary after the write, and only read from a replica whose pg_last_wal_replay_lsn() has passed it.

4. 4

   Use synchronous replication where it matters

   COMMIT waits for a standby to confirm. Safer, but every write pays a network round trip.

Sharding splits one logical table across several independent databases, each owning the rows for a range or hash of a shard key. Replicas scale reads; sharding is for when writes or data size outgrow one primary.

It solves one problem and creates several. Queries without the shard key hit every shard. Cross-shard joins and transactions get slow or hard. A bad key creates a hot shard: shard orders by seller during a big sale and one popular seller melts a single node. Exhaust cheaper options first (indexes, caching, replicas, archiving, a bigger machine), then pick the shard key from your most common query, often user_id or tenant_id.

Start with SQL unless you can name the specific reason it won't work. Relational databases give you transactions, constraints, joins and ad hoc queries, and scale further than most products need. Choose NoSQL when the access pattern is narrow and known and you need horizontal write scale or a data model SQL handles badly.

Most real systems use more than one: orders and payments in PostgreSQL, carts and sessions in Redis, product search in Elasticsearch, clickstream in a write-optimised store. The skill is matching each piece of data to the store whose trade-offs fit it.

• Indexing every column 'just in case'. Index for queries you actually run and drop the ones your statistics show are unused.
• Composite indexes in the wrong order, then wondering why EXPLAIN shows a Seq Scan.
• Read-modify-write in application code without a lock, atomic UPDATE or version check.
• Sending every read to a replica and forgetting read-your-writes.
• Calling a payment gateway inside BEGIN ... COMMIT, which holds locks and snapshots far too long.

A good next step: run EXPLAIN on your three most frequent queries and check whether each says Index Scan or Seq Scan. Twenty minutes of that teaches you more about your system than another week of reading.