A B-tree is a balanced ordered search tree that groups many keys into a storage page. A log-structured merge tree, or LSM tree, is an ordered storage structure that buffers updates and merges sorted components in batches. Both can back a database index that supports exact-key lookups and key-range scans. In a quote store that ingests bursts of updates while serving reads, the layout affects when those operations compete for storage bandwidth.
Follow a page path or search sorted runs
In a B+ tree, a common database variant of the B-tree, separator keys in each internal page direct a lookup to the child covering the requested key. At the leaf, the reader finds the value or a reference to a row, depending on the layout. The many children per page keep the tree shallow. A range scan can seek to its first key and continue through neighbouring leaves. An insertion changes the target leaf and can split a full page, adding a separator to its parent. A split can propagate up to the root. These are changes to the logical page structure. The engine’s cache, logging and storage policy determine the actual writes. See the original B-tree paper and the PostgreSQL B-tree structure documentation.
In a modern LSM design, an update enters a memory buffer called a memtable, typically alongside an append to a write-ahead log for recovery. A flush writes an immutable sorted run to storage, commonly in sorted-table files (SSTables). Compaction merges selected runs or overlapping files and may discard versions that no reader needs. Reads reconcile versions across candidate sources. Key ranges and a Bloom filter can rule out files for an exact-key lookup. A positive filter result still needs verification. A range scan may merge several sorted streams as it goes. See the original LSM-tree paper, the RocksDB architecture overview and its tuning guide.
A deleted quote can still occupy storage
Suppose three fictional runs were flushed in the order shown by their run numbers, with one version per key per run. The latest read sees
ask-new at key 20, even though that key appears in two runs. It also sees last at 30. The newest entry for 10 is a tombstone, a deletion marker, so the read returns no value for that key.
A dash means the run has no entry for that key. The current read follows the newest visible entry in each column, while an older snapshot can still see a value that the tombstone hides today.
Dropping the tombstone while the oldest run still serves
10 would bring bid-old back in current reads. A compaction can physically discard the marker only when older values it would expose have been eliminated from the relevant read paths and the rewrite preserves every active snapshot’s result. In this example, a snapshot taken after run 2 but before run 3 must still see bid-old. With no such snapshots or any other need to preserve earlier views, compacting all three runs down to the two live values preserves the current result. See the LevelDB compaction notes and RocksDB’s snapshot description.Where the storage work shows up
| Measure | B-tree | LSM tree |
|---|---|---|
| Read amplification measures storage reads per logical query. | An exact lookup follows one index path. Cached pages can avoid device reads, and fetching a row by reference can add work. | An exact lookup can check multiple candidate sources. Filters and cache can avoid device reads, while scans can need to reconcile several runs. |
| Write amplification compares bytes written to storage with bytes submitted by the application. | Small changes can eventually write whole pages. Splits and recovery logging can add writes. | Flushing batches turns updates into sequential file writes. Compaction can rewrite the same data repeatedly, including unchanged values in overlapping files. |
| Space amplification compares allocated storage with the size of live data. | Partially filled pages take space. Some engines also retain older versions. | Overwritten values, tombstones and simultaneous compaction inputs and outputs can all occupy space. |
In a quote-store comparison, keep the durability settings and memory budget comparable and measure while ingestion and reads run together. Include the actual mix of point queries and scans, and check tail latency as well as throughput. A short write-only burst can end before the corresponding compaction work arrives. RocksDB’s tuning guide discusses these amplification measures and compaction backlog.
For a concrete B-tree use case, the SelfMadeQuant lesson builds a composite instrument-date key and a date index in SQLite, then queries a bounded price panel. Its preview is public and the full lesson requires membership. SQL and Persistent Data
Sources
- Rudolf Bayer and Edward McCreight (1972), Organization and Maintenance of Large Ordered Indexes, §§1–4.
- Patrick O’Neil, Edward Cheng, Dieter Gawlick and Elizabeth O’Neil (1996), The Log-Structured Merge-Tree (LSM-Tree), §§2–3.
- PostgreSQL documentation, B-Tree Structure and SQLite Database File Format, B-tree pages.
- LevelDB implementation notes, sorted tables and compactions.
- RocksDB Overview, architecture, reads and snapshots and RocksDB Tuning Guide, amplification and compaction.