Comparisons and explanations · Intermediate

B-trees versus LSM trees

Compare B-tree and LSM storage designs through ordered access, buffering, compaction, tombstones and read/write/space amplification.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. The timing and placement of changes differ
  2. Trace one key update
  3. Compare three kinds of amplification
  4. Understand the lifetime of deletion markers
  5. Compaction backlog can reach foreground requests
  6. Choose a concrete configuration for the workload
  7. Ask Logeia about this articleCheck your understanding

The timing and placement of changes differ

A B-tree maintains ordered keys in a multiway tree supporting lookup and range access. Database implementations commonly organize nodes as pages, find a target page for modification, and split when required. A representative LSM design buffers changes in memory, flushes sorted files, and merges files later. Neither label specifies one immutable implementation. Logging, caches, compression, and memory management vary across products. The central comparison asks when changes are incorporated and which operations pay the associated cost. This is more informative than assuming that one structure always writes sequentially or that the other never buffers modifications before reaching persistent storage.

Trace one key update

Consider changing key k from one to two. A B-tree model locates the corresponding page entry for modification. In an LSM, the new version can enter memory or a newer file while an older version remains elsewhere. A read locates the required sources and determines the newest applicable value. Removing old versions during merging requires attention to whether any supported reader still needs them. Multiple internal versions do not necessarily mean that the application receives duplicate logical rows. Keep the physical retention model separate from the API’s result contract. That distinction matters when investigating both unexpectedly large storage and apparently correct reads.

Compare three kinds of amplification

Write amplification relates device-level writes to logical application writes. LSM compaction can rewrite data several times. Reads may consult several candidate files, with filters and indexes reducing some of that work. Old versions and concurrent input/output files can require temporary space during compaction. B-trees have their own costs from page splits, logging, free space, and cache behavior. Fast initial insertion into memory alone does not establish better sustained device traffic or tail latency. Compare read, write, and space amplification together, because a tuning change that improves one axis can increase pressure on another and alter behavior only after prolonged operation.

Understand the lifetime of deletion markers

An LSM commonly represents deletion with a tombstone so that a value in an older file does not reappear. Observing logical deletion does not imply immediate erasure from every storage location. Compaction rules, older readers, and backups can retain information. Logical invisibility, space reclamation, and physical information erasure are separate requirements. A B-tree deletion likewise need not shrink its containing file immediately by the row’s size. For capacity planning or sensitive-data deletion, inspect the product’s actual reclamation and retention procedures. A storage-structure comparison alone cannot establish a complete deletion or sanitization guarantee across replicas, snapshots, and archives.

Compaction backlog can reach foreground requests

If writes arrive faster than compaction can keep up, growing file counts and pending work can increase read costs or lead to write stalls. Background processing is not unrelated to user-visible delay: it competes for CPU, I/O, and storage space with foreground work. A short test inserting into an empty database does not reproduce the state after extended updates and deletions. Observe the transition toward steady state along with compaction volume, stall duration, and slower response percentiles. A setting that reduces background work now can defer rather than eliminate the cost. Evaluate whether it changes sustained capacity or merely postpones when the accumulated work becomes visible.

Choose a concrete configuration for the workload

Small random reads, large range scans, append-heavy ingestion, and repeated overwrites can favor different cost allocations. Align data size and distribution, memory, durability, compression, and read/write mix before measuring. Comparing a PostgreSQL B-tree index with RocksDB’s LSM does not by itself establish the superiority of either complete database product; an index and a storage engine have different responsibilities. This article compares mechanisms without claiming a measured performance advantage. The final decision requires the specific configuration and guarantees the application needs. A structure name provides useful hypotheses, but it cannot replace sustained tests of correct completed work under representative conditions.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Understand the systems behind the web · STEP 12

Choose a learning path