Skip to content
Tutorials Center
My learning

Topics

Lesson 41 of 65 ยท Core Algorithms and Data Structures for Design

LSM Trees and B-Trees

Understand the storage engines behind databases: B-trees for fast reads, LSM trees for fast writes, write-ahead logs, compaction and amplification, with runnable Python models.

Every database must answer two questions on disk: how do I find a record quickly, and how do I absorb writes quickly? Disks (even SSDs) are very slow compared with memory, and they are much faster when reading and writing sequentially than when jumping around at random. Two data structures dominate storage engines because they handle this reality in opposite ways:

  • B-trees update data in place on disk and are optimized for reads. PostgreSQL, MySQL (InnoDB) and most relational databases use them.
  • LSM trees (log-structured merge trees) only append and merge in the background and are optimized for writes. Cassandra, RocksDB, LevelDB, HBase and many time-series databases use them.

Knowing the difference helps you choose a database for a write-heavy or read-heavy design and explain why it behaves as it does.

B-trees

A B-tree is a balanced tree whose nodes are sized to match a disk page (often 4 to 16 KB). Each node holds many keys (hundreds), so the tree is very shallow. To find a key you start at the root, pick the child whose range contains the key, and repeat until a leaf holds the record.

Because the fan-out is huge, depth stays tiny. With around 500 keys per node, three levels address 500 ร— 500 ร— 500 = 125 million records, and four levels more than 60 billion. The top levels fit in memory, so a lookup usually costs one or two disk reads.

Python How deep is a B-tree?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

B-tree strengths and costs:

  • Reads are fast and predictable, including range scans, since leaf pages are linked in key order.
  • Writes update a page in place. If a page is full, it splits, which may ripple upward. Random in-place writes are slower on disk than sequential appends.
  • Crash safety needs a write-ahead log (WAL): before changing a page, the change is appended to a sequential log, so after a crash the database can replay it. Every write is therefore written at least twice (log and page).
  • Fragmentation and space overhead: pages are often only partly full.

LSM trees

An LSM tree turns random writes into sequential ones:

  1. Write goes to the WAL (for durability) and to an in-memory sorted structure called the memtable.
  2. When the memtable is full, it is flushed to disk as an immutable sorted file, an SSTable (sorted string table).
  3. Reads check the memtable, then SSTables from newest to oldest, returning the first match.
  4. In the background, compaction merges SSTables, drops overwritten values and removes deleted keys.

Deletes cannot remove data from immutable files, so a delete writes a tombstone marker that hides older values until compaction removes both.

flowchart LR
  W[Write] --> WAL[(WAL on disk)]
  W --> M[Memtable in memory]
  M -->|flush when full| S1[SSTable L0]
  S1 -->|compaction| S2[SSTable L1]
  S2 -->|compaction| S3[SSTable L2]
  R[Read] --> M
  R --> S1
  R --> S2
  R --> S3

Writes land in memory and the log; background compaction keeps files sorted and merged.

Python A miniature LSM tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that a read for an old key checked several files before finding it. After compaction, one file remains and the read touches just one. That is the core LSM trade-off.

Amplification: the cost model

Storage engines are compared by three kinds of amplification:

  • Write amplification: bytes physically written per byte the application wrote. B-trees write the log and the page (and sometimes split pages); LSM trees rewrite data every time it is compacted into a lower level.
  • Read amplification: disk reads per lookup. B-trees do one or two; LSM trees may check several levels.
  • Space amplification: disk used versus actual data size. LSM trees hold obsolete versions until compaction; B-trees waste space in half-empty pages.
B-tree LSM tree
Write pattern Random, in place Sequential appends and merges
Write throughput Good Excellent
Point read Excellent (1-2 I/Os) Good (needs Bloom filters, see next lesson)
Range scan Excellent Good, but must merge across files
Write amplification Moderate Can be high (compaction)
Latency Predictable Can spike during compaction
Typical engines InnoDB, PostgreSQL, SQLite RocksDB, Cassandra, HBase, LevelDB

LSM read performance relies on Bloom filters: a tiny per-file structure that says "this key is definitely not in this file", so most files are skipped without a disk read. That is the topic of the next lesson.

Python Counting write amplification

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

These are textbook estimates, not benchmarks, but they show why tuning matters: size ratios, compaction strategy (leveled versus size-tiered) and memtable size shift the trade-off between write amplification and read cost.

Choosing in a design

  • Mostly point reads and joins, moderate writes, need transactions: a B-tree relational database.
  • Very high write rate (logs, metrics, time series, messages, IoT) and key-based reads: an LSM-based store.
  • Analytics scanning millions of rows over a few columns: neither: use a column store (Parquet, ClickHouse, BigQuery) that stores each column contiguously and compresses well.
  • Full text search: an inverted index (Lucene, Elasticsearch), which is itself a segment-based design similar to LSM.

Indexes in your relational database are B-trees too (see SQL vs NoSQL and Storage Types and Sharding and Partitioning for how they scale out).

When a design interview mentions "write-heavy" or "append-only", say "LSM-based store such as Cassandra or RocksDB", then explain memtable, SSTables, compaction and Bloom filters in two sentences each.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why are B-trees very shallow in practice?

    Nodes match disk page size and hold many keys, so a few levels can address billions of records.
  2. 2. What does an LSM tree do with a write?

    LSM trees convert random writes into sequential ones using a WAL, a memtable and immutable SSTables.
  3. 3. What is a tombstone?

    Immutable files cannot be edited, so deletes are written as markers and removed physically during compaction.
  4. 4. Which workload best suits an LSM-based store?

    LSM trees excel at heavy write ingest. Analytics scans suit column stores, and joins suit relational B-tree databases.

Summary

  • B-trees update pages in place, are shallow and give fast, predictable reads and range scans.
  • LSM trees append to a log and memtable, flush sorted SSTables and merge them by compaction, favoring writes.
  • Deletes in LSM trees use tombstones; compaction removes old versions and reduces read cost.
  • Compare engines by write, read and space amplification.
  • Choose by workload: B-tree for read-heavy transactional data, LSM for write-heavy ingestion, column stores for analytics.

Next: Bloom Filters