When an application starts slowing down under heavy traffic, the instinct is almost always to throw more CPU cores at the database or add a caching layer in front of it. Yet once the working dataset outgrows available RAM, performance comes down to something much more fundamental: how the underlying storage engine arranges bytes on disk.
Almost every database you use in production relies on one of two core data structures under the hood—a B+ Tree (used by PostgreSQL, MySQL InnoDB, and SQLite) or a Log-Structured Merge-Tree, or LSM-Tree (used by RocksDB, Cassandra, ScyllaDB, and InfluxDB). Understanding the physical trade-offs between these two designs makes it far easier to predict when a database will thrive and when it will hit a wall.
The Core Tension: Random Updates vs. Sequential Appends
Storage hardware—even modern NVMe SSDs—behaves very differently depending on whether you overwrite small chunks of data in place or stream large, contiguous blocks sequentially.
A B+ Tree keeps data sorted in fixed-size pages on disk (typically 4 KB to 16 KB). When you update an existing row, the engine traverses the tree, finds the exact leaf page holding that record, modifies it in memory, and writes that entire page back to its original spot on disk. Because user requests arrive in unpredictable order, those page writes end up scattered across different physical locations. To guarantee durability if power cuts out mid-write, the database also appends every change to a Write-Ahead Log (WAL) first—meaning every logical modification triggers at least two separate disk operations.
An LSM-Tree takes the opposite stance: never overwrite existing files on disk. Instead, incoming writes go straight into an in-memory buffer called a MemTable (while still being recorded in a sequential WAL for crash recovery). Once the MemTable fills up, the engine sorts its keys and flushes the entire batch to disk as an immutable file called a Sorted String Table (SSTable). Updates and deletes do not touch older SSTables; the engine simply writes a newer version of the key or a special deletion marker called a tombstone into the latest MemTable.
Where LSM-Trees Pay the Price: Background Compaction
Turning random writes into fast sequential appends sounds like a free lunch, but there is a catch. If you keep flushing new SSTables indefinitely, two problems build up quickly:
1. Duplicate versions pile up, wasting disk space.
2. Reads get slower, because finding a single key might require checking the MemTable plus several different SSTables created over time.
To keep reads fast and reclaim wasted space, LSM engines run a background process called compaction. Compaction reads multiple SSTables, merges their sorted keys, discards overwritten values or expired tombstones, and writes out fresh, consolidated SSTables.
This is where engineers get caught off guard in production. While client-facing writes look blazingly fast, background compaction consumes significant disk I/O and CPU bandwidth. Under sustained high write load, if compaction falls behind the rate of incoming flushes, the storage engine deliberately throttles incoming writes—causing sudden p99 latency spikes that look mysterious if you are only watching average response times.
How Reads Behave Under Both Designs
For point lookups and range queries, B+ Trees remain remarkably predictable:
- Predictable Read Depth: Because a B+ Tree has a high branching factor (often hundreds of keys per internal node), even a table with tens of millions of rows usually takes only three or four page lookups to reach the target leaf. If the upper levels sit in the buffer pool cache, a lookup often requires just a single disk read.
- Fast Range Scans: Leaf pages in a B+ Tree are linked together in sorted order. Scanning all orders placed between 9:00 AM and 10:00 AM means finding the starting key and reading adjacent leaf pages straight across.
LSM-Trees work much harder on reads, especially when querying keys that do not exist. To avoid opening every SSTable on disk for a missing key, LSM engines attach Bloom filters (compact probabilistic bit arrays) to each SSTable. A Bloom filter can confirm with 100% certainty when a key is not inside a file, skipping unnecessary disk reads. Even so, wide range scans across an LSM-Tree must merge iterators from the MemTable and multiple SSTable levels on the fly, which adds noticeable CPU and I/O overhead compared to scanning a single sorted B+ Tree leaf chain.
Practical Rules for Choosing Between Them
You rarely pick a storage engine in isolation, but matching your workload shape to the underlying data structure saves painful migrations later:
Stick with a B+ Tree engine (like PostgreSQL or InnoDB) when:
- Your workload is read-heavy or balanced between reads and transactional updates.
- You rely on multiple secondary indexes and frequent range queries.
- Strict, predictable tail latency matters more than raw ingestion ceiling.
- Tip: Avoid random UUIDv4 primary keys on large B+ Tree tables—random inserts scatter across leaf pages, triggering frequent page splits and fragmentation. Time-ordered IDs (like UUIDv7 or ULIDs) keep new inserts clustered at the right edge of the tree.
Reach for an LSM-Tree engine (like RocksDB, Cassandra, or ScyllaDB) when:
- Writes dominate your traffic—such as telemetry pipelines, IoT sensor ingestion, audit logs, or high-volume event streams.
- Your dataset is massive and on-disk compression efficiency directly impacts cloud storage bills.
- Your access patterns mostly look up records by primary key rather than running complex multi-index range scans.
- Tip: Watch tombstone buildup closely if your application frequently deletes records or relies on short TTLs—heavy tombstone density slows down range scans until compaction clears them out.



.png)