Compare B-Tree vs Log-Structured Merge-tree (LSM-Tree) database storage engines.
❓ Interview Prompt: Compare B-Tree storage engines (PostgreSQL/MySQL - fast reads, in-place updates) vs LSM-Tree storage engines (RocksDB/Cassandra - fast sequential writes, SSTables, MemTable).
Comparing core database index storage engine architectures:
| Property | B-Tree / B+Tree (PostgreSQL, InnoDB) | LSM-Tree (RocksDB, Cassandra) |
|---|---|---|
| Write Performance | Slower (Random I/O disk writes to leaf pages) | Extremely Fast (Sequential append-only MemTable & WAL) |
| Read Performance | Fast (Direct $O(\log N)$ index pointer lookups) | Slower (Checks MemTable + Bloom Filters + SSTables) |
| Compaction | In-place page updates; fragmentation risk | Background merge compaction of SSTable levels |
| Best For | Read-heavy OLTP relational workloads | Write-heavy, time-series, log ingestion workloads |
Code Implementation Example
{
"storageEngine": "LSM-Tree (Log-Structured Merge-Tree)",
"components": ["MemTable (RAM)", "Write-Ahead Log (WAL)", "Bloom Filters", "SSTables (Disk)"],
"optimizationTarget": "High Sequential Write Throughput"
}Use B-Tree databases for read-heavy relational workloads, and LSM-Tree engines for high-throughput write ingestion.