Here is a database. It is not a toy — it has properties that real storage engines work hard to keep.
db_set () { echo "$1,$2" >> database; }
db_get () { grep "^$1," database | sed -e "s/^$1,//" | tail -n 1; }db_set appends a line. db_get finds every line for a key and takes the last
one. That is it.
$ db_set 42 '{"name":"Ada"}'
$ db_set 42 '{"name":"Ada Lovelace"}'
$ db_get 42
{"name":"Ada Lovelace"}It handles updates — by appending a newer record and letting the reader prefer the last one. It survives a crash mid-write, because a truncated final line leaves every earlier record intact.
Why the write path is genuinely excellent
db_set is, near enough, the fastest possible write. Appending to a file is
sequential, and sequential beats random by a wide margin on every storage
device ever built — for different reasons each time, which is why the advantage
keeps surviving hardware changes.
On spinning disks the head had to physically move for a random write. On SSDs there is no head, but the flash translation layer must erase a whole block before rewriting part of one, so scattered small writes turn into a great deal of internal copying. Sequential appends let the drive fill blocks in order and mostly avoid that.
The idea
An append-only log is the highest-throughput write pattern available. Nearly every high-write storage engine is, underneath, a log plus some machinery to make reading it bearable — including the write-ahead log inside the update-in-place engines you will meet later in this module.
Why the read path is unusable
db_get scans the entire file. Every time. For every key.
That is O(n) in the number of records ever written — not records currently live, records ever written, because the old versions are still sitting there. Double the writes and every read gets twice as slow, including reads of keys you wrote years ago.
The second problem: the file never stops growing
Write the same key a thousand times and the file holds a thousand records, of which 999 are dead. Disk fills with history nobody asked for.
The fix is compaction: read the log, keep only the most recent value for each key, write a new file, swap it in, delete the old one.
before k1=a k2=b k1=c k3=d k1=e k2=f
after k3=d k1=e k2=fThe clever part is that compaction is itself a sequential read and a sequential write, and it happens in the background on files nobody is appending to. The live log stays append-only throughout; a compacted file is produced beside it and swapped in when complete. That structure — never modify, always produce a new file and switch — is what makes crash recovery straightforward, and it will reappear in every engine in this module.
What we actually need
To fix reads without giving up the append-only write, we need to answer where is the record for key k without scanning. That is precisely what an index is.
An index is derived data — an additional structure maintained on the side, from which the original data could always be reconstructed. That gives us the governing trade-off of the entire module:
The index trade
Every index speeds up reads that use it and slows down every write, because the write must now update the data and the index. There is no such thing as a free index — the question is always whether the reads you gain are worth the writes you pay.
This is why databases do not index every column by default, and why a table with nine indexes is slow to insert into. It is also why the next lesson starts with the simplest possible index and finds out where it breaks.
Check yourself
Why does an append-only log beat updating records in place, even on an SSD with no moving parts?
What to take away
The two-line database is fast to write, impossible to read, and grows forever. Compaction fixes the growth. The rest of this module is about fixing the reads — and every solution will cost you something on the write path, on the read path, or in space.