Databases 01 — How Data Is Stored & Found

You type SELECT * FROM expense WHERE id = 4242 and the row comes back in under a millisecond out of ten million. That isn’t magic and it isn’t luck — it’s a sorted tree, a fixed-size block of disk, and a cache, all working exactly the way they were designed. This module cracks open the storage engine so the next time a query is slow, you don’t guess — you know which of those three is the problem.

The Goal

By the end of this module you can:

• Explain that a database stores rows in fixed-size pages, not as one giant file you scan line by line
• Distinguish the heap (where rows actually live) from an index (a sorted map to them)
• Draw a B-tree and trace a lookup through it, connecting it to the trees you walked in DSA
• Describe how the WAL makes a transaction durable even if the power dies mid-write
• Explain the buffer pool — why the first query is slow and the second is instant
• Say in one sentence why sequential reads crush random reads, and why every storage design bends around that fact

The Lesson

The database is not one big text file

Picture how a beginner imagines a table: one long file, rows stacked top to bottom, and WHERE id = 4242 means “read from the top until you find it.” If that were true, the 10-millionth row would take ten million times longer than the first. It doesn’t. So the picture is wrong.

Here’s the real one. A table on disk is a stack of pages (PostgreSQL calls them pages, others say blocks — same idea). A page is a fixed-size chunk — 8 KB in PostgreSQL — and it is the smallest unit the database ever reads or writes. You never read “a row” from disk. You read the whole 8 KB page the row sits in, then pick your row out of it in memory.

flowchart TD
    subgraph File["expense table file on disk"]
        P0["Page 0 - 8 KB"]
        P1["Page 1 - 8 KB"]
        P2["Page 2 - 8 KB"]
        P3["Page 3 - 8 KB"]
    end
    P0 --> Z["zoom into one page"]
    subgraph Page["Inside Page 1"]
        H["page header"]
        PT["item pointers - row 0, row 1, row 2"]
        FREE["free space in the middle"]
        ROWS["actual rows packed from the bottom up"]
    end

Inside one page: a small header, then a list of item pointers (tiny offsets saying “row 0 starts at byte 7920”), free space in the middle, and the actual row data packed in from the bottom. The pointers grow down from the top, the rows grow up from the bottom, and they meet in the free space. When they collide, the page is full and a new page is allocated. This two-level addressing — which page, then which slot in the page — is the foundation everything else is built on.

Why 8 KB? Because the disk says so

A page is fixed-size and chunky for one reason: disks and operating systems move data in blocks, not bytes. Asking the OS for “byte 4242” costs almost exactly the same as asking for the whole block around it. So the database stops fighting the hardware and adopts its unit. Read a page, cache a page, write a page. Every design decision in this module traces back to “the disk thinks in blocks, so we do too.”

The heap — where rows actually live

The default storage for a table is a heap: rows sit in pages in no particular order — roughly insertion order, with gaps where deleted rows used to be. The heap is the source of truth. It holds the real, complete rows.

The catch you already met in the SQL indexes module: a heap is unsorted, so finding id = 4242 by searching the heap means reading every page until you hit it. That’s a sequential scan — Seq Scan in EXPLAIN. Fine for a 4-row table. Catastrophic for ten million rows.

Each row in the heap has a physical address PostgreSQL exposes as ctid — a pair (page, slot). (0,1) means “page 0, item pointer 1.” It’s the database’s home address for that row, and you can actually print it (you will, in Build This). Hold onto ctid: it’s the thing an index points at.

The index — a sorted map back to the heap

An index doesn’t store your rows. It stores the indexed column’s values, sorted, each paired with a ctid pointing back to the heap row. Sorted data is searchable in O(log n) — the same win you proved in binary search. The heap stays unsorted and authoritative; the index is a fast lookup table laid on top.

So a lookup by an indexed column is two steps: walk the index to find the ctid, then follow the ctid into the heap to fetch the full row. That second step — the jump into the heap — is the random read that decides whether an index is worth using, which is the whole selectivity story from the SQL track.

Inside a B-tree

The index isn’t a flat sorted list — searching a flat list still means a lot of hopping. It’s a B-tree (balanced tree): the same family you walked in DSA trees, but with a crucial twist for disk. A binary tree has 2 children per node. A B-tree node has hundreds — because one node = one page, and an 8 KB page can hold hundreds of keys-plus-pointers. More children per node means a far shorter tree, which means fewer pages to read to reach any value.

flowchart TD
    R["Root page<br/>keys: under 5000 | 5000 to 9999 | 10000 and up"]
    R --> B1["Branch page<br/>under 2000 | 2000 to 4999"]
    R --> B2["Branch page<br/>5000 to 7499 | 7500 to 9999"]
    R --> B3["Branch page<br/>10000 to 14999 | 15000 and up"]
    B2 --> L1["Leaf page<br/>5000 to 6249<br/>each key plus a ctid"]
    B2 --> L2["Leaf page<br/>6250 to 7499<br/>each key plus a ctid"]
    L1 -.->|ctid points home| HEAP["Heap page - the real row"]
    L2 -.->|ctid points home| HEAP

Finding id = 6300: start at the root, which says “6300 falls in the 5000-to-9999 branch.” Go to that branch page, which narrows it to “5000-to-7499.” Go to that leaf page, scan its sorted keys, find 6300, and read its ctid. Then one jump into the heap for the full row. That’s 3 page reads to navigate the tree, plus 1 into the heap — four reads to find one row among ten million.

Here’s why it scales like nothing else. The tree is short and fat:

Multiply the table by 100 and you add one level. That is the logarithm made physical. A sequential scan over 10 billion rows reads billions of pages; the B-tree reads five. The leaves are also linked left-to-right, so a range query (WHERE id BETWEEN 6000 AND 6500) finds the start, then walks sideways across leaves — no re-descending the tree per row.

The buffer pool — why the second query is free

Reading from disk is slow even on an SSD — orders of magnitude slower than reading from RAM. So the database keeps a chunk of memory called the buffer pool (in PostgreSQL, shared_buffers) and caches recently-used pages in it.

The flow on every read: does the page I need live in the buffer pool already?

flowchart TD
    Q["query needs page 1742"] --> C{"page in<br/>buffer pool?"}
    C -->|yes - a hit| FAST["serve from RAM<br/>microseconds"]
    C -->|no - a miss| DISK["read 8 KB page from disk<br/>milliseconds"]
    DISK --> STORE["place page in buffer pool<br/>evict the least-recently-used page if full"]
    STORE --> FAST

This is why the first run of a query is slow and the second is suddenly fast — the first run pulled the pages off disk into the buffer pool; the second found them already in RAM. It’s not the planner getting smarter; it’s the cache warming up. When you benchmark, run a query twice and trust the second number — the first includes a cold-cache penalty that won’t exist in a warm production system. When the pool fills, the least-recently-used pages get evicted to make room. A well-tuned database serves the vast majority of reads from the buffer pool and barely touches the disk.

WAL — how a write survives a power cut

Now the scary part. A write changes a page. That page lives in the buffer pool (RAM), and writing it back to disk is slow, so the database doesn’t do it immediately. But RAM is volatile — pull the plug and it’s gone. So how can the database promise that once it tells you COMMIT succeeded, your money-transfer is permanent, even if the server loses power one millisecond later?

The answer is the WAL — Write-Ahead Log (Oracle calls it the redo log; the idea is universal). The rule is in the name: before any change is considered committed, a compact record of that change is appended to the WAL on disk and physically flushed. Only after the WAL record is safely on disk does COMMIT return success.

sequenceDiagram
    participant App as Your app
    participant DB as Database
    participant WAL as WAL file on disk
    participant Heap as Heap pages on disk
    App->>DB: UPDATE balance, then COMMIT
    DB->>DB: change the page in the buffer pool
    DB->>WAL: append change record and flush to disk
    WAL-->>DB: flushed and durable
    DB-->>App: COMMIT succeeded
    Note over DB,Heap: later, in the background
    DB->>Heap: write the dirty pages to the heap

Why this is brilliant: appending a small record to the end of one file is a sequential write — the fastest thing a disk does. Updating the actual heap pages would mean scattered random writes all over the disk — the slowest. So the database makes the durability guarantee with a fast sequential write now, and lazily flushes the real pages later in the background.

If the power dies before the heap pages are flushed, no problem: on restart the database replays the WAL — re-applying every committed change record to bring the heap back up to the last commit. Anything that hadn’t committed is discarded. That replay is recovery, and the WAL is exactly why the transactions module’s D in ACID — Durability is a real promise and not wishful thinking. (Bonus: the WAL is also what replication ships to replicas — module 03 — and what point-in-time backups rewind through.)

Sequential beats random — the law under everything

You’ve now seen the same fact three times wearing different costumes:

• A sequential scan reads pages in order — the disk’s read head (or the SSD controller) streams contiguous blocks at full speed.
• An index lookup ends in a random jump into the heap — and many random jumps are why the planner refuses an index for low-selectivity queries.
• The WAL is fast precisely because it’s a sequential append, while flushing scattered heap pages would be random.

The law: sequential reads and writes are dramatically faster than random ones, on every storage medium ever built — spinning disks (where the head physically moves) brutally so, SSDs less so but still real. Every storage design you’ll ever meet — log-structured engines, columnar stores, batch loaders, even ORDER BY on a clustered index — is some clever scheme to turn random access into sequential. Once you internalize this single sentence, half of database performance stops being mysterious.

Check The Concept

How This Shows Up At Work

• The cold-cache benchmark blunder. A teammate reports a query takes 400 ms and pushes for a redesign. You ask them to run it twice — the second run is 4 ms. The 400 ms was a cold buffer pool that production never has. Knowing the buffer pool exists just saved a week of unnecessary work.
• The “why is durability slow” question in a fintech interview. “Walk me through what happens between COMMIT and the data being safe.” The answer is the WAL: a sequential append flushed to disk before commit returns, with lazy background flushing of the real pages. This is a money-systems question, and the WAL answer marks you as someone who understands the machine.
• The disk-full incident caused by the WAL. Replication breaks, the primary can’t recycle old WAL segments because a replica still needs them, the WAL grows until the disk fills, and writes stop. Engineers who know what the WAL is for diagnose this in minutes; everyone else stares at a full disk in panic.
• The migration that locked the table. Adding a column or an index rewrites or scans pages, and on a big heap that can hold a lock long enough to freeze the app — exactly the territory the migrations companion doc covers. You can only reason about it once you know a table is pages on disk, not an abstract list.

Build This

All in psql against your SplitEase database (splitease_sql). You’re going to physically locate rows on disk, watch the heap-vs-index difference in a real plan, and warm the cache with your own eyes. Have the SQL indexes module’s 100,000-row seed loaded — if SELECT count(*) FROM expense; shows only a handful, run that module’s generate_series insert first.

1. Peek at where a row physically lives. ctid is the row’s home address — (page, slot):

SELECT ctid, id, amount_paise FROM expense ORDER BY id LIMIT 5;

You’ll see something like:

 ctid  | id | amount_paise
-------+----+--------------
 (0,1) |  1 |        15000
 (0,2) |  2 |        16000
 (0,3) |  3 |        17000
 (0,4) |  4 |        18000
 (0,5) |  5 |        19000

Read it: the first rows live in page 0, slots 1, 2, 3… When page 0 fills (~60 rows at this width), the next rows spill into page 1. That (page, slot) pair is exactly what every index leaf points at.

2. See how many pages your table occupies. A table is just a pile of 8 KB pages:

SELECT relname, relpages, reltuples::bigint AS approx_rows
FROM pg_class WHERE relname = 'expense';

relpages is the page count; reltuples the estimated row count. Roughly: relpages × 8 KB is your table’s size. With 100k rows you’ll see hundreds to a couple thousand pages — and that is what a sequential scan has to read end to end.

3. Watch the heap scan — the slow path. Drop any index on id is impossible (it’s the primary key), so use a non-indexed column. Pick a column with no index yet (amount_paise if you haven’t indexed it):

EXPLAIN ANALYZE SELECT * FROM expense WHERE amount_paise = 50000;

Look for Seq Scan on expense and a big Rows Removed by Filter. The database read every page to find a few rows. Write down the Execution Time.

4. Watch the index scan — the fast path. Create the index, run the same query:

CREATE INDEX IF NOT EXISTS idx_expense_amount ON expense (amount_paise);
EXPLAIN ANALYZE SELECT * FROM expense WHERE amount_paise = 50000;

Now it’s Index Scan (or Bitmap Index Scan) and Index Cond instead of Filter. That’s the B-tree walk plus the ctid jump into the heap, instead of reading all those pages. Compare the two Execution Times — that gap is this whole module.

5. Warm the cache with your own eyes. Cache hits vs disk reads are countable. Turn on buffer reporting and run a fresh query twice:

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM expense WHERE id = 73000;
-- run the EXACT same line again
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM expense WHERE id = 73000;

In the Buffers: line, the first run may show shared read=N (pages fetched from disk). The second run shows shared hit=N instead (pages found in the buffer pool). That flip from read to hit is the buffer pool warming up — the literal reason the second query is faster.

6. See the WAL exist. You can’t watch a power cut, but you can prove the log is real and growing:

SELECT pg_walfile_name(pg_current_wal_lsn());

That’s the current WAL segment file the database is appending committed changes to right now. Every COMMIT you’ve ever run flushed a record into a file like this before returning success. (No fix needed — this step is just making the invisible durability machinery visible.)

7. Break it on purpose — kill the index with a function. Reuse the lesson from SQL indexes and confirm it at the storage level:

EXPLAIN SELECT * FROM expense WHERE amount_paise / 100 = 500;

Seq Scan again — the B-tree stores amount_paise, not amount_paise / 100, so the sorted structure is useless and the engine falls back to reading every page. Naked column on the left, or index the expression. The storage view makes it obvious why: the tree only knows the values it was built from.

Interview Practice

These are asked in real backend and fintech rounds at Indian product companies. Say the answer out loud before opening each one.

Where to Practice

Check Yourself

1. What is a page, how big is it in PostgreSQL, and why is it fixed-size and chunky?
2. What’s the difference between the heap and an index, in one sentence each?
3. A B-tree node has hundreds of children, not two. Why, and what does that buy you?
4. Trace a lookup of id = 6300 through the B-tree diagram — name each level you touch.
5. What does the WAL guarantee, and why is appending to it fast?
6. Why is the first run of a query often slow and the second fast? Name the component responsible.
7. Give one example each of where a database relies on sequential access and where it pays the cost of random access.
8. What is ctid, and why must you never use it as a stable key in your code?

Explain it out loud: Explain to an empty chair the full journey of SELECT * FROM expense WHERE id = 6300 on a ten-million-row table: which structure is consulted first, the page reads down the B-tree, the ctid jump into the heap, what the buffer pool does on a second run, and why the same query without an index would read the whole heap. If you stall on “ctid” or “buffer pool,” that’s your re-read section.

Why AI Can’t Do This For You

AI can recite “PostgreSQL uses 8 KB pages and a B-tree index” in a heartbeat. What it can’t do is stand in front of your slow query at 11pm and know whether the fix is an index, a query rewrite, a warm cache the benchmark missed, or a WAL-full incident strangling writes — because that judgment comes from having run EXPLAIN (ANALYZE, BUFFERS) on your own data and watched read flip to hit with your own eyes.

The storage model is the lens that turns a wall of plan output into a diagnosis. Once you’ve physically located a row with ctid, counted your table’s pages, and seen the WAL segment file the database is appending to right now, “the database is slow” stops being a mystery and becomes a short list of suspects you can name. No prompt installs that intuition — only poking the machine does.

Module done? Add it to today’s tracker