Logs and sorted files

A database stores data and finds it again. Engines for small transactions are either log-structured (append only) or B-trees (change pages in place). This unit builds the first kind.

Index trade-off

The simplest store appends a "key,value" line to a file and scans the whole file on each read. Writes are fast, but reads slow down as the file grows. An index is an extra structure built from the data that makes finding things fast. It never changes your data, only speed. Each index takes space and slows every write, so add only the ones you need.

Hash index over a log

Keep the append-only file, plus an in-memory map from each key to the byte offset of its newest value. A read is one lookup and one seek. Limits: old values waste disk, the map must be rebuilt by a full scan after a restart, all keys must fit in memory, and range queries are slow.

SSTables and sparse index

An SSTable (Sorted String Table) keeps keys sorted, each key once, in blocks of a few KB. A sparse index keeps only the first key of each block. To find a key, jump to the block whose range holds it and scan that block. Blocks can be compressed.

Memtable and flush

New writes go into a sorted map in memory, the memtable. At a few MB, it is written out as a new SSTable. Reads check the memtable, then the newest file, then older ones. Each write is also appended to an unsorted log on disk, used only to rebuild the memtable after a crash.

Merge, compaction, tombstones

In the background, files are merged like mergesort, keeping the newest value of each key. Files never change once written, so a half-built file is just thrown away. Write-once files also suit object storage, such as S3. A delete writes a tombstone, a marker that hides older values until merging removes them.

Remember

• Indexes speed reads and slow writes.
• SSTable: sorted blocks, sparse index.
• Memtable in memory, crash log on disk.
• Deletes are tombstones, cleaned up by compaction.