From append-only log to index: the core trade-off
From append-only log to index: the core trade-off
Append-only log
every db_set appends
writes: O(1), sequential
reads: full scan O(n)
cheap writes
The read problem
db_get scans every line
no index, no shortcuts
restart = rescan all
slow reads
Add a derived index
key-sorted structure
reads: O(log n)
writes update it too
Every index is a trade-off
Reads: faster
jump straight to data
Writes: slower
index updated per write
Space: bigger
a derived copy on disk
No free index: choose by query pattern