What you are building

A database stores records and provides operations for finding and changing them. This project starts with an append-only data file, then adds an index, a small query planner, transactions, and crash recovery. The application interface stays mostly unchanged while the storage layer grows.

The app is the one you already have, from the small web app project. It saves by turning its whole list into one piece of text and handing that text to the browser to keep (step 12 of Writing an Application), then reading the whole thing back when it starts. That is fine for forty items and hopeless for four hundred thousand. Write this build as a program on your own machine rather than inside the browser tab, because you need a file you can add to the end of, and both Node and Python will do that in two lines.

Teal entries are build checks. The four magenta entries explain a storage limitation and link to the relevant lesson.

Project milestones

Append one record to a data file.
A file is a numbered strip of bytes kept on the disk, still there after the program stops, and a byte is one small number. Open the file in the mode that adds to the end rather than replacing what is there, write one row, close it. Then open the file in a text editor and count the characters.
Read that row back into the app.
Reading is the harder half, because nothing in the file says where a row ends. Choose the rule, either a newline character after every row or a count of bytes written in front of each one, then write the reader that trusts the rule. Get the row onto the screen in your app.
Find the row you want by reading every row.
Ask for one thing by name: the quest called Feed the cat. Start at the beginning, compare, stop at the match. Count how many rows you read to answer it, and print that count. The rest of the build is an attack on that number.
Measure the cost of a full scan.
Add rows in a loop until the file is a few hundred megabytes. The question that used to answer instantly now takes seconds. Ask for a quest that is not in the file at all and it is slower still, because the only way to be sure a thing is absent is to read every row there is.

What you need
An index: a second structure, much smaller than the file, kept in order by the value you search on, so that each look at it throws away half of what is left instead of one row. The shape that does this is a binary search tree. An index on a table is that same shape with the rows left where they are, holding the value and the position in the file where its row begins.
step 2Finding one row without reading them all step 10The binary search tree
Find one row by index, with the index in memory.
Memory is the fast space a running program works in, and it is wiped when the program stops. Read the file once at startup and build the ordered structure there, then ask the same question again and print how many rows you touched. One, out of two hundred thousand, after about twenty hops down the tree.
Move the index to disk without reading it all.
Rebuilding the index at every start costs more than the queries save, so you write the tree out to its own file and read the nodes back as you walk down it. Now every hop from one node to the next is a separate trip to the disk, and a tree with two keys per node has a great many hops.

What you need
A disk will not hand you one number. It hands over a whole page, four thousand bytes or so, and charges nearly the same for that as for a single byte. So a node has to be a page in size and hold hundreds of values rather than two, which makes the tree wide and only three or four levels tall. That shape is a B-tree, and it is what nearly every database keeps its indexes in.
step 3Fat, shallow trees
One row out of a million, in a handful of page reads.
Count the pages a lookup reads and print the count. Then move the index file out of the way, run the same lookup, and watch it fall back to reading the lot. Those two numbers side by side are what the last hour bought you.
Plan a filtered, ordered, limited query.
Every question so far has meant new code in the app. A filter and an ordering and a limit, all in one question, is where that stops being reasonable. So you write the question as a sentence in SQL, the language stores are asked questions in, and then find you have nothing that can receive the sentence.

What you need
The sentence has to become a plan before anything can run. First the words become a tree, so the filter and the ordering are separate branches rather than text. Then the tree becomes a short ordered list of operations (read this table, keep the rows where done is false, sort those by date, stop after ten) which the scanning and index code you have already written can carry out one row at a time. Choosing that list is a different job from running it.
step 3Write down what the query has to do
Run a query and print its chosen plan.
One sentence with a filter, an ordering and a limit in it, answered out of your own file, with the plan printed beside the answer. Read the plan and check by eye that it went through the index rather than reading everything.
Reproduce a partial transaction after a crash.
Some changes have two parts: take the potion out of the bag and put it in the chest, move ten points from one column to another. Do the first write, kill the program before the second, reopen the app, and the potion is in neither place. Kill it in the middle of one write instead and the file ends in half a row, which stops your reader dead on the next start.

What you need
Write down what you are about to do before you do it, into a separate file that only ever grows, and add a mark meaning finished only once all of it is safely down. On restart, read that file first: replay every change carrying the finished mark and throw away every change that does not. The file is a write-ahead log, and a group of writes carrying that both-or-neither promise is a transaction. It rests on knowing when a write has genuinely reached the disk, rather than sitting in the operating system's memory waiting its turn.
step 8Writing it down before you do it
Recover complete transactions after any injected crash.
Put the changes in a loop and kill the program at twenty random points, including during the restart itself. Every time, the app comes back with each change either wholly applied or wholly absent, and no half row anywhere in the file. That is the build finished, and that promise is most of what separates a database from a file.

Review the database in four passes

Review the same database for expected behaviour, edge cases, query cost, and recovery.

Make it work

Done, above. Rows go in, one comes back without reading the rest, a query is answered, and a kill tears nothing.

Make it correct

Open two copies of the app on the same file. Have both read the same row, both change a different part of it, both write it back. Then look at the row and count how many of the two changes are still in it.

Make it fast

Time ten thousand inserts with the index in place and then with it removed, so you know what the fast reads cost the writes. Then find the question your plan still answers by reading every row.

Make it survive

Cut the power during the recovery rather than during a write, and run the recovery twice on purpose. If replaying a finished change twice leaves anything different from replaying it once, the recovery is not safe to interrupt, and it will be interrupted.

Course links for each pass

Each of those three later passes has a step behind it, in the two database courses. Take them when you want them and not before.

The change that quietly vanished.
Make it correct
Both writers read the row, both worked out a new value from what they read, and the second write landed on top of the first with no complaint from anywhere. The pattern that breaks is read-modify-write and the standard it has to meet is that the result must match what you would have got by running the two changes one after the other, in some order.
step 9The update that disappears
The plan that was built on a guess.
Make it fast
Choosing between reading everything and going through the index means guessing how many rows will match before a single one has been read. The guess comes from a few counts the engine keeps about the table, its statistics, and a plan built on a wrong guess can be slower than having no index at all.
step 9One bad guess, and the plan that follows
What the disk has actually promised you.
Make it survive
Saved has three meanings: your program has written it, the operating system has accepted it, and the drive itself holds it. Only the third one survives the power going off. Reaching it means asking for it, with an instruction called fsync that costs real time, which is exactly why it gets left out.
step 12What "saved" actually promises

Optional extension: semantic retrieval with cited answers

Keep exact keys, SQL filters and transactions for facts that must match. Add semantic search only for a collection of documents where similar wording is useful, then make retrieval and generation separately measurable.

Store chunks, provenance and permissions beside each embedding.
Every vector points back to a document version, location, owner and access rule. Deleting or updating a document must update its index entries. A vector without provenance cannot support a citation.
Build a retrieval evaluation before adding generation.
Write questions with known supporting chunks. Measure recall at k, exact identifier lookup and latency under realistic corpus size. Compare lexical, vector and hybrid retrieval, and test stale and access-controlled documents.
Generate only from authorised retrieved evidence.
Apply identity and metadata filters as part of retrieval, treat document text as untrusted data, and require citations. Check that each cited passage supports the sentence; a present citation can still be irrelevant.
Crash the index update and rebuild it from the source of truth.
The embedding index is derived data. After interruption, it must be possible to resume or rebuild without inventing, losing or exposing documents. Keep the transactional document store authoritative.

Relevant lessons: retrieval-augmented generation, hybrid text retrieval, nearest-neighbour indexes, and system evaluation.

Related projects and courses

A file that only grows, an index that skips most of it, a plan you can print, and a log that makes a group of writes all or nothing. Those four pieces are what sits inside the database behind a bank as well as the one inside the messages app on your phone. What comes next is more than one machine holding the same rows, where two of them can be told different things at the same moment and each be certain it is right.

All builds or read Inside a Database and Build a Query Engine straight through, which cover the same ground in order and go considerably further.