Introduction

Most of us treat the database as the one part of the stack we never open. You write INSERT, it comes back fast, and when it stops coming back fast you add an index and hope. That works until a migration locks a table for twenty minutes, or a query that used an index yesterday does a sequential scan today, and nobody on the team can say why.

This series opens it. Each article takes one layer of a database engine (pages, B-trees, LSM trees, the write-ahead log, MVCC, indexes, the planner, replication) and walks through how it actually works, using PostgreSQL and SQLite as the real code to read. The Data Structures with Golang series built trees and hash tables in memory; here we see what changes when those structures have to live on disk and survive a power cut.

Two halves of a database

Strip away the wire protocol and the config files and a relational database is roughly two programs glued together.

The query layer takes text and turns it into work: parse the SQL, check it against the catalog, pick a plan, and run that plan as a tree of operators (scan, filter, join, sort).

The storage engine owns the bytes: how rows are laid out in fixed-size pages, which pages are cached in memory, how indexes find rows, how a change is made durable before the commit returns, and how two transactions avoid seeing each other's half-finished work.

Most of the series is on the storage side, because that is where the surprising behavior comes from. A planner choosing a bad plan is usually reacting to something real about pages and statistics. A slow UPDATE in PostgreSQL makes sense once you know it writes a whole new row version instead of changing the old one in place.

Series roadmap

Each layer leans on the one before it. MVCC makes little sense before you know what a page and a WAL record look like, so the order matters.

Code examples are in Go, same as the data structures series. They are small and meant to show an idea, not to compete with a real engine.

An append-only store and where it breaks

The fastest way to see why engines are built the way they are is to build the dumbest thing that works and watch it break. Here is a key-value store that appends every write to a file and keeps a hash map from key to the byte offset of its latest record:

package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strings"
)

type DB struct {
	f     *os.File
	index map[string]int64 // key -> offset of the latest record
}

func Open(path string) (*DB, error) {
	f, err := os.OpenFile(path, os.O_RDWR|os.O_CREATE|os.O_APPEND, 0o644)
	if err != nil {
		return nil, err
	}
	db := &DB{f: f, index: map[string]int64{}}
	return db, db.rebuild()
}

// rebuild scans the whole file to recover the index after a restart.
func (db *DB) rebuild() error {
	r := bufio.NewReader(io.NewSectionReader(db.f, 0, 1<<62))
	var off int64
	for {
		line, err := r.ReadString('\n')
		if err == io.EOF {
			return nil // a partial last line is silently ignored
		}
		if err != nil {
			return err
		}
		key, _, _ := strings.Cut(line, ",")
		db.index[key] = off
		off += int64(len(line))
	}
}

func (db *DB) Set(key, value string) error {
	off, err := db.f.Seek(0, io.SeekEnd)
	if err != nil {
		return err
	}
	if _, err := fmt.Fprintf(db.f, "%s,%s\n", key, value); err != nil {
		return err
	}
	db.index[key] = off
	return nil
}

func (db *DB) Get(key string) (string, bool, error) {
	off, ok := db.index[key]
	if !ok {
		return "", false, nil
	}
	r := bufio.NewReader(io.NewSectionReader(db.f, off, 1<<62))
	line, err := r.ReadString('\n')
	if err != nil {
		return "", false, err
	}
	_, value, _ := strings.Cut(strings.TrimSuffix(line, "\n"), ",")
	return value, true, nil
}

func main() {
	db, err := Open("toy.db")
	if err != nil {
		panic(err)
	}
	db.Set("user:1", "ana")
	db.Set("user:1", "ana maria")

	v, _, _ := db.Get("user:1")
	fmt.Println(v) // ana maria
}

Writes are one sequential append, which is about the cheapest thing you can ask a disk to do. Reads are one hash lookup plus one positioned read. This is close to how Bitcask, Riak's storage engine, works, and for some workloads it is genuinely good.

Now try to use it for anything real.

Run Set("user:1", ...) a million times and the file holds a million records, of which one is alive. You need something that rewrites the file without the dead records while writes keep arriving. That is compaction, and doing it well with sorted files is the whole idea behind LSM Trees.

Ask for every key between user:100 and user:200. A hash map has no order, so you scan everything. The index also has to fit in RAM, and it is rebuilt by reading the entire file on every restart. A sorted structure that lives on disk and loads one page at a time is what B-Trees and Pages & Storage Layout are about.

Pull the power cable right after Set returns. Fprintf returned once the bytes reached the OS page cache, not the disk. The write might be gone, or half of it might be there, and rebuild will quietly skip the torn line. Then the next append gets glued onto it, so after a crash mid-write of user:2 the file ends in user:2,toruser:1,ana and the store now believes a key called user:2 exists. Getting "commit returned" to mean "it is on disk", without calling fsync on every row, is the job of the Write-Ahead Log.

Run two goroutines that move money between account:a and account:b. Nothing stops a reader from seeing the debit without the credit, and the map itself is not even safe for concurrent writes. Transactions & MVCC cover how engines let readers and writers proceed without blocking each other and without seeing half a change.

Then come the questions that only exist once there is a query language: finding users by email when the key is an ID (Indexes), deciding between an index and a full scan (Query Planning), and keeping a second machine in sync (Replication).

Every article in the series fixes one of the gaps above, and each fix costs something somewhere else. B-trees make reads cheap and writes scattered; LSM trees do the opposite. MVCC removes reader/writer blocking and leaves garbage that someone has to vacuum. Most of the series is about those trade-offs.

How to follow along

You need two engines installed, and both are free:

• PostgreSQL 18, easiest through Docker: docker run --rm -e POSTGRES_PASSWORD=pg -p 5432:5432 postgres:18
• SQLite 3, which is probably already on your machine as sqlite3

They make a good pair. PostgreSQL is a client-server engine with a separate WAL, a buffer pool and heap tables. SQLite is a single C library with one database file, so the whole file layout fits in your head.

A few commands we will use often:

-- PostgreSQL
SHOW block_size;                         -- 8192: the page size
SELECT pg_relation_filepath('users');    -- where the table lives on disk
EXPLAIN (ANALYZE, BUFFERS)
  SELECT * FROM users WHERE id = 42;     -- the plan, plus pages read/hit
CREATE EXTENSION pageinspect;            -- read raw page contents

-- SQLite
PRAGMA page_size;                        -- 4096 by default
EXPLAIN QUERY PLAN
  SELECT * FROM users WHERE id = 42;

EXPLAIN (ANALYZE, BUFFERS) is the one to get used to. It reports how many pages a query touched and whether they came from the buffer pool (shared hit) or had to be read (read). That number ties almost every later article back to something you can measure.

When we read source, these are good places to start:

• PostgreSQL: src/include/storage/bufpage.h (page layout), src/backend/access/nbtree/README (B-tree design notes), src/backend/access/transam/README (transactions and WAL)
• SQLite: src/btree.c, src/pager.c and src/wal.c, plus the file format document
• LevelDB: doc/impl.md, a short and readable description of an LSM tree

The PostgreSQL READMEs are worth knowing about. They are long, plain-text design documents written by the people who wrote the code, and they explain the reasoning behind the code better than most books do.

What you should already know

• Enough SQL to write joins and know what a primary key is
• Enough Go to read the examples
• Trees and hash tables at the level of Part 2 and Part 3 of Data Structures with Golang

The B-tree article in particular assumes you have seen a binary search tree and a balanced tree before. It spends its time on why disks want a tree that is wide and shallow instead of tall and thin.

Conclusion

A database is a query layer sitting on a storage engine, and nearly every behavior you notice in production, whether a slow update, a bloated table or a plan that flipped, comes from a trade-off one of those layers made. The toy store above has every gap a real engine closes.

Next is Pages & Storage Layout: why everything is read in 8 KB pages, how a row is placed inside one, and what the buffer pool does with them.