B-Trees and LSM Trees
The two dominant ways databases organize data on disk — B-trees update records in place for fast reads, LSM trees batch writes into sorted files for fast writes — and why a quant's storage engine choice depends on which workload dominates.
A tick-data database needs to do two very different things well: accept a firehose of new trades and quotes as they happen, and answer "give me AAPL's prices between 10:00 and 10:05" quickly, on demand. Every mainstream storage engine is built around one of two data structures for reconciling those goals, and knowing which is which explains a lot about why Postgres, MySQL, RocksDB, and Cassandra behave so differently under load.
A B-tree keeps data sorted on disk at all times, updating records in place — reads are fast and predictable, writes require finding and modifying the right page. An LSM tree instead appends new writes to an in-memory buffer and periodically flushes them as new sorted files, merging older files together in the background — writes are fast and sequential, reads may have to check several files.
How each one works
A B-tree is a balanced, disk-oriented search tree: each node holds a sorted range of keys and pointers to child nodes, and the tree stays balanced so any key is reachable in a small, predictable number of disk reads. Updating a record means locating its page and overwriting it in place — a random-access write to wherever that page happens to live on disk.
An LSM tree (log-structured merge tree) never edits existing files. New writes go into an in-memory table (the memtable); once that fills, it's flushed to disk as a new immutable, sorted file (an SSTable). Reads must potentially check the memtable and several SSTables, newest first, and a background process periodically merges (compacts) older SSTables together to bound how many files a read has to touch.
Worked example
A trading system logs 200,000 order events per second and occasionally needs to look up a single order by ID. With a B-tree engine, each insert is a random-access disk write to the correct leaf page — at 200,000 writes/second, a spinning or even SSD-backed disk can become the bottleneck because random I/O is far slower than sequential I/O. With an LSM engine, all 200,000 writes/second land sequentially in the memtable and are flushed as large sequential blocks — dramatically higher write throughput — but a lookup for one order ID might have to check the memtable plus several SSTables (mitigated with an index and a Bloom filter per SSTable to skip files that can't contain the key) before it finds a match, so single-key reads are slower and less predictable than a B-tree's.
What this means in practice
Postgres and MySQL's default engine (InnoDB) use B-trees, favoring the read-heavy, update-in-place patterns of transactional systems. RocksDB, Cassandra, and most time-series and log-ingestion databases use LSM trees, favoring the write-heavy, append-only patterns of event streams — which is why tick-data and order-log storage increasingly defaults to LSM-based engines. A quant choosing infrastructure for a data pipeline is implicitly choosing this trade-off: how much of the workload is "ingest fast" versus "look up one thing fast."
LSM trees defer cost, they don't eliminate it — compaction is a real, ongoing background workload that competes for disk and CPU, and a system with heavy write volume but poorly tuned compaction can suffer read latency spikes ("read amplification") or a growing backlog of unmerged SSTables that never fully catches up.
Related concepts
Practice in interviews
Further reading
- Kleppmann, Designing Data-Intensive Applications (storage engines chapter)
- O'Neil et al., 'The Log-Structured Merge-Tree (LSM-Tree)' (1996)