How databases
store your data
Two families of storage engines, and why your database’s write and read speed depend on which one it uses.
→ next · ← back · N notes · F full screen
The world’s simplest database: two shell functions.
kv_set () {
printf '%s,%s\n' "$1" "$2" >> store.log
}
kv_get () {
grep "^$1," store.log | tail -n 1 | cut -d, -f2-
}Fix the reads with an index: extra structure derived from the data. Every index speeds reads and slows writes.
Log-structured engines
Only ever append. Clean up later.
Hash index: remember where each key lives.
Keep an in-memory hash map from each key to its byte offset in the log. One seek per read.
Split the log into segments; compact and merge them in the background.
Great for
Lots of writes per key, all keys fit in RAM. Example: a play counter per video.
Weak at
Too many keys for memory. Range queries: each key must be looked up separately.
Lab: append-only log + hash index
Set a key a few times, then Get it, then Compact.
SSTables: keep each segment sorted by key.
B-trees
The default for 50 years: fixed pages, updated in place.
Pages pointing to pages.
LSM vs B-tree: no universal winner.
| LSM-tree | B-tree | |
|---|---|---|
| Writes | ✓ usually faster, sequential | ✕ each write hits WAL + page |
| Reads | ✕ may check several segments | ✓ one path down the tree |
| Disk usage | ✓ compresses well, less fragmentation | ✕ pages partly empty after splits |
| Latency tail | ✕ compaction can stall requests | ✓ more predictable |
| Transactions | ✕ a key can live in many segments | ✓ each key in exactly one place |
Write amplification: one logical write turning into many physical writes. On SSDs it eats both throughput and lifespan.
Other indexes
Secondary, clustered, multi-dimensional, fuzzy, in-memory.
Beyond the primary key.
Secondary index
Keys aren’t unique: store a list of row IDs, or make keys unique by appending the row ID.
Heap vs clustered
A heap file holds rows and indexes point at it (PostgreSQL). A clustered index stores the row inside the index (MySQL InnoDB primary key).
Covering index
Stores some extra columns in the index so certain queries never touch the table (INCLUDE in PostgreSQL).
Multi-column
Concatenated keys, or R-trees for things like latitude and longitude (PostGIS).
Fuzzy
Full-text search engines like Lucene can match misspellings within an edit distance.
In-memory
Redis, VoltDB: fast mainly because they skip encoding data for disk, not because they skip disk reads.
Lab: which index structure fits?
Now, our system.
Indexes on hot tables
Every index slows writes. How many indexes do our busiest settlement tables carry, and are they all used?
Covering indexes
Which reports could be served from an index alone with INCLUDE columns?
Update patterns
We update status rows in place many times. How does that show up as table and index bloat in PostgreSQL?
Write-heavy paths
Do any audit or event tables look like append-only logs? Would an LSM-based store suit them better?
Analytics and column storage
Why reporting queries need a completely different storage layout. Chapter 3, part 2.