Andreas Maita

Early this winter, I got an email from our production database.
It calmly informed me that during the night it had run a reindex and how long that took.

I started to get nervous.

Not because it broke anything — everything was green — but because it sounded like the database had quietly performed open-heart surgery while we slept. And then left a note on the kitchen table like, “FYI, I rebuilt your indexes. Took 47 minutes. Have a nice day.”

First of all, I had no idea what that actually meant. After about five minutes of reading and debugging my own panic, I realized it wasn’t a big deal at all. But the email stuck with me. I started wondering:

What exactly is being “reindexed”?
Why does it take this long?
What would happen if we didn’t do it?
And… what even is an index in concrete terms?

That question pulled me straight back to my database class from more than ten years ago. And I had to admit something uncomfortable:

I use databases every day, but I understand surprisingly little about how they actually work.

Sure, I can design schemas, write queries, add indexes, tune a query plan when I have to. I know the rituals. But if you asked me what really happens when you run CREATE INDEX, or why a range query is fast on one table and slow on another, my answer would be a mix of folklore and half-remembered lecture slides.

So I decided to change that.

I’m going to build my own database engine from scratch.

Not a “production competitor”. Not a distributed monster. A small, readable database that I can understand end-to-end — and that will force me to stop hand-waving the parts I’ve been outsourcing to “the DB”.

Welcome to MiniDB.

What I want from “my” database

Before writing a single line of code, I wrote down a few properties this database should have:

It should be scalable (at least conceptually): performance should degrade gracefully as data grows
Interacting with it should be a good developer experience: understandable errors, predictable behavior, easy local usage
It should be flexible to deploy: standalone binary, in containers, or embedded into another app
It should support a familiar SQL dialect, but also ship with a small, readable query language
It should be inspectable: I want to be able to print pages, dump trees, and see what’s actually happening

Will my first prototype achieve all of this? Of course not.
But these goals will be the compass for every design decision going forward.

Also: I’m doing this in Rust. Partly because I enjoy it, partly because systems constraints are the point here. I want to think about memory layout, file I/O, and correctness — not just “it seems to work”.

The mental model: storage, pages, and an engine

One thing I always found tricky about databases is that they look like a single black box. You send SQL in, rows come out. But inside, there are multiple subsystems cooperating:

A storage layer that persists bytes to disk (usually in fixed-size blocks)
An index structure that maps keys to data locations efficiently
A query layer that parses, plans, and executes requests
A transaction/recovery layer (think: WAL) that makes crashes boring instead of catastrophic

This series will build those pieces incrementally, starting with the one that makes “reindex” make sense: the index structure.

First stop: how is data organized?

When you dig into how real databases work, the first big topic you hit is data layout and index structures.

There’s a lot of thought behind it, because we all have implicit expectations about databases:

Reads should be fast
Writes should be fast
Queries should still be fast even when there are millions of rows
“Find all rows between A and B” should be fast, not a full scan
The database should not fall apart the moment data no longer fits into RAM

The way data is organized has to deliver on those expectations.

And that’s where the innocent sounding word “index” becomes a real engineering object.

An index is not magic. It’s a data structure with trade-offs. It improves some workloads while making others more expensive. And sometimes it needs maintenance — like a reindex — because the structure can become inefficient or inconsistent over time (depending on the engine, the workload, and how it stores tuples).

Why a simple list is not enough

Imagine we store rows in a simple list or array.

If we want to find the row with a certain key, the most straightforward algorithm is:

Start at the beginning
Walk through the list until we find the element

The problem is obvious: in the worst case, the element is at the last position (or it doesn’t exist). That means we have to inspect almost every entry. For large datasets, that’s painfully slow.

We can improve lookups if the list is sorted by a key:

Use binary search
Start in the middle, decide “left or right”, and repeat
Lookup time becomes logarithmic in the number of elements

Great for reads.

But now inserts become painful: every time we add a new element, we have to find the correct position and shift elements around to keep the list sorted.

And it gets worse when you think like a database:

Data often lives on disk, not in memory
Disk likes sequential access, but hates tiny random writes
Shifting “elements in an array” becomes “rewriting a large portion of a file”
Concurrency means multiple readers/writers want to touch the structure at once

There has to be a better structure.

Enter trees (and why databases love B+ Trees)

This is where computer scientists came up with trees: hierarchical structures that organize data in levels instead of a flat list.

You’ll find many tree variants (binary search trees, AVL trees, red-black trees, …). But the vast majority of database engines use a family called B-Trees, and most specifically B+ Trees, as their core index structure.

Why?

Very roughly:

They keep data sorted by key, so point lookups and range queries are efficient
They are designed so that each node fits into a disk page, minimizing I/O
They stay balanced automatically: inserts and deletes keep the height small
They support high fan-out (many children per node), which keeps trees shallow even for huge datasets

A key intuition: databases don’t optimize for “number of comparisons”. They optimize for “number of page reads”. If your tree is only 3–4 levels deep for millions of rows, you can often locate data with just a handful of disk page accesses.

And this is where the earlier email starts to sound less mysterious: “reindex” is often about rebuilding or compacting these structures so they’re efficient again, or to recover from bloat/fragmentation that accrues under certain workloads.

Why B+ Trees specifically?

In a B+ Tree, internal nodes act like a routing table: they hold separator keys and child pointers. The actual record references (or the records themselves, depending on design) live in the leaf nodes.

The leaves are usually linked, which makes range queries incredibly natural: find the first leaf for key k, then walk leaf-by-leaf until you’re done.

As a mental model:

Internal nodes answer: “Which direction should I go?”
Leaf nodes answer: “Here are the actual entries, in order.”

That separation is one of the reasons B+ Trees fit disk-based workloads so well.

A tiny illustration

Imagine each node is a page-sized box. A (simplified) internal node might look like this:

Keys: [10, 20, 30]
Children: C0, C1, C2, C3

Then:

key < 10 goes to C0
10 <= key < 20 goes to C1
20 <= key < 30 goes to C2
key >= 30 goes to C3

You repeat that until you reach a leaf page, which contains sorted entries and a pointer to the next leaf page.

What “reindex” starts to mean

At this point, “reindex” stops being scary and becomes concrete: if indexes are trees on disk, rebuilding an index is essentially reconstructing that tree so it’s consistent and efficient again.

Different databases do this for different reasons (and with different mechanics), but common themes are:

Rebuilding an index from the underlying table data
Removing fragmentation/bloat and restoring a compact layout
Fixing structural inconsistencies after certain failures or upgrades

In other words: not magic — just expensive, because it’s a lot of data movement and I/O.

What’s next in this series

In the rest of this series, I will:

Implement a B+ Tree step by step (search, insert, split, delete)
Introduce pages and a tiny pager abstraction so the tree can live on disk
Build a minimal storage format for keys/values
And along the way, demystify terms like “reindex”, “page”, and “WAL” that production databases casually throw at us

If you’ve ever added an index, seen a query become (100\times) faster, and thought “I kind of know why”, this series is for you.

Let’s build the thing.