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.
Discussion
💡 Discussion rules
- Ask and answer about this concept. Off-topic gets removed.
- No homework dumps. Show what you tried first.
- Corrections are welcome. Cite a source when you claim an error.
Loading discussion…
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)