Path 1 · lesson 1 of 8
Storage engines: B-tree versus LSM tree
Why Postgres updates pages in place and Cassandra only ever appends: what each design costs on writes, reads and disk, measured on real Postgres 18 and Cassandra 5.0.
What you will learn
- Explain how a B-tree finds a row in a handful of page reads, and why its height grows so slowly
- Explain why a page-based engine writes far more to its log than the bytes you changed
- Trace a write through an LSM tree: commit log, memtable, flush, SSTable, compaction
- Predict when an LSM read touches one file and when it must merge many
- Name the read, write and space costs each design trades, and the workloads each one suits
Before you start
The concept
Every database has to answer the same question before it can do anything else: when a row changes, where do the new bytes go? There are two families of answer, and almost every engine you will meet belongs to one of them.
Neither is better. Each makes one operation cheap by making another one expensive, and the costs have names. Read amplification is how many places a read has to look. Write amplification is how many bytes the engine writes for each byte you change. Space amplification is how much disk the data takes compared with its live size. A B-tree keeps reads cheap and pays on writes. An LSM tree makes writes cheap and pays on reads and, between merges, on space.
| B-tree (Postgres) | LSM tree (Cassandra) | |
|---|---|---|
| Where a change goes | Into the page that holds the row, in place | Into memory, then a new file; old files are never touched |
| A point read | Root to leaf: one page per level | Newest data first; possibly several files |
| A write | Random: whichever page holds the row | Sequential: append to the commit log, flush in order |
| Old versions | Cleaned up by VACUUM (Postgres) or in place | Cleaned up by compaction |
| Typical fit | Transactions, updates, range queries, many secondary indexes | Heavy writes, time series, append-mostly data |
Why it exists
Both designs exist because disks are much better at some kinds of work than others. Writing one large sequential block is cheap. Updating many small scattered blocks costs more, on spinning disks dramatically, on SSDs still measurably. A B-tree accepts scattered writes in exchange for being able to find any key in very few reads. The LSM tree was designed the other way round: in the 1996 paper that introduced it, O'Neil and colleagues aimed it at workloads with a high rate of inserts, where a B-tree's per-insert random I/O was the bottleneck.
That is why the choice matters for system design and not only to database authors. A service that ingests a firehose of events and rarely updates them pushes a B-tree towards its worst case. A service that updates the same rows constantly and reads them back by key and range pushes an LSM tree towards its worst case. Knowing which design sits under your database tells you which of your queries will hurt as the data grows.
How it works inside
A B-tree in Postgres: pages, levels and fan-out
Postgres stores tables and indexes in 8 kB pages. Its B-tree index is, in the words of its documentation, a multi-level tree where "each leaf page contains tuples that point to table rows" and "each internal page contains tuples that point to the next level down". A lookup starts at the root and follows one pointer per level until it reaches a leaf, then fetches the row from the table page the leaf points to.
The lab loads 1,000,000 orders into a table with a bigint primary key and asks Postgres how big the result is.
Database outputTable and index size for 1,000,000 rows
Real database output--- 1. Sizes: 1,000,000 rows table_size | index_size | index_pages ------------+------------+------------- 57 MB | 21 MB | 2745
The interesting number is not the size but the height. The pageinspect extension can read the index metapage, which records the level of the root. Level 0 is the leaf level.
Database outputHow tall the B-tree is
Real database output--- 2. How tall is the B-tree? (level 0 = leaf; a root at level 2 means three levels)
root_level | fastroot
------------+----------
2 | 412Three levels for a million rows is the consequence of fan-out. Each internal page holds hundreds of pointers, so each level multiplies the number of reachable leaves by hundreds. Going from a million rows to a billion adds roughly one more level, not a thousand times more work. This is the property that makes a B-tree lookup cost almost the same on a small table and a huge one.
Here is what one lookup actually reads. EXPLAIN (ANALYZE, BUFFERS) counts the pages the query touched in Postgres's shared buffer cache. The lab runs a warm-up query first, because the first lookup in a new connection also reads and caches the index metapage.
Query planOne primary-key lookup on the million-row table
Real database outputIndex Scan using orders_pkey on orders (actual rows=1.00 loops=1) Index Cond: (id = 734512) Index Searches: 1 Buffers: shared hit=4
hit means each page was already in memory.Query planThe same lookup asking only for the key: an index-only scan
Real database outputIndex Only Scan using orders_pkey on orders (actual rows=1.00 loops=1) Index Cond: (id = 734512) Heap Fetches: 0 Index Searches: 1 Buffers: shared hit=4
Heap Fetches: 0 means the table was never read. Postgres checked the visibility map page instead, to confirm the row is visible to everyone without visiting the table.Query planA 100-row table for comparison
Real database outputIndex Scan using tiny_pkey on tiny (actual rows=1.00 loops=1) Index Cond: (id = 50) Index Searches: 1 Buffers: shared hit=2
When a leaf page fills up, Postgres splits it into two and adds a pointer to the parent, which may split in turn; when the root itself splits, the tree gains a level. Postgres implements Lehman and Yao's high-concurrency B-tree algorithm, which adds a right-link and a high key to every page so that readers can detect a concurrent split and follow the right-link, without holding read locks on the pages above. Index pages are packed to a fillfactor of 90% when the index is built, leaving room for inserts before the first splits.
What "in place" really costs: the write-ahead log
Changing a page in place is dangerous: a crash halfway through writing an 8 kB page can leave it half old and half new. Postgres protects against that with its write-ahead log (WAL): every change is described in the log, and the log is flushed before the change counts as committed. And because the row-level description is not enough to repair a torn page, Postgres also writes the entire page to the WAL the first time the page is modified after a checkpoint (the full_page_writes setting, on by default).
The lab measures that cost. It takes a checkpoint, updates the total of 100,000 rows (every tenth row, so the changes are spread across the whole table), and reads how far the WAL advanced.
Database outputWAL written by 100,000 updates right after a checkpoint
Real database output--- 5. Updates in place: WAL written by updating 100,000 rows (10% of the table), right after a checkpoint wal_written | bytes_of_values_changed -------------+------------------------- 99 MB | 781 kB --- 5b. What that WAL is made of: full-page images versus the change records themselves full_page_images | change_records ------------------+---------------- 77 MB | 21 MB
pg_walinspect splits it: 77 MB are full-page images, every heap and index page touched for the first time since the checkpoint, copied whole.Database outputThe same update again, with no checkpoint in between
Real database output--- 5d. The same update again straight away, with no checkpoint in between wal_written | full_page_images -------------+------------------ 23 MB | 7816 bytes
Why still 23 MB? Because in Postgres an update is not really in place at row level: it writes a new version of the whole row and leaves the old one for VACUUM (that is MVCC, covered in the Postgres path). The lab shows none of these updates could stay on the same page as a heap-only (HOT) update, so each also wrote a new entry into the primary key index:
Database outputWere the updates heap-only?
Real database output rows_updated | hot_updates
--------------+-------------
100000 | 0An LSM tree in Cassandra: commit log, memtable, SSTables
Cassandra's write path never seeks. A write is appended to the commit log for durability and inserted into the memtable, a sorted structure in memory. When the memtable reaches its limit it is flushed to disk as an SSTable (sorted string table), and from then on, as the documentation puts it, SSTables "are immutable, and never written to again". Each SSTable is a small set of files: the data, an index from partition keys to positions in the data, and a Bloom filter that can say quickly that a key is definitely not in this file.
Because files are never rewritten, an update to a row does not replace the old value: it writes a newer one, with a newer timestamp, into a newer SSTable. The lab writes new totals for the same 20,000 orders in five rounds, flushing after each round, with automatic compaction switched off so that you can see the files pile up.
Database outputFive rounds of writes, each flushed
Real database output--- 1. After five rounds of writes, each followed by a flush (autocompaction off) SSTable count: 5 Old SSTable count: 0 Space used (live): 706212 Number of partitions (estimate): 200 --- 2. Files on disk for the table: each SSTable is a set of immutable files nb-1-big-Data.db nb-2-big-Data.db nb-3-big-Data.db nb-4-big-Data.db nb-5-big-Data.db
Reads: newest first, and when that is not enough
A read now has to find the newest value of a row that exists in five files. Cassandra's tracing shows what it actually did. First, a read of one row by its full primary key:
Read traceRead one row, traced
Real database outputAcquiring sstable references Merging memtable contents Partition index found for sstable 5, size = 0 Read 1 live rows and 0 tombstone cells
That is a deliberate optimisation. For a query that names exact rows (no ranges, counters or collections), Cassandra sorts the SSTables by their newest timestamp and reads them in that order, "in the hope of only having to query the 1 or 2 most recent", stopping as soon as it holds values newer than anything an older file can contain. Every round overwrote the row, so the newest file had the answer.
A read of the whole partition (all 100 orders of one customer) cannot stop early: it has to merge the partition from every file that holds part of it.
Read traceRead a whole partition, traced
Real database outputAcquiring sstable references Skipped 0/5 non-slice-intersecting sstables, included 0 due to tombstones Partition index found for sstable 1, size = 0 Partition index found for sstable 2, size = 0 Partition index found for sstable 3, size = 0 Partition index found for sstable 4, size = 0 Key cache hit for sstable 5, size = 0 Merged data from memtables and 5 sstables Read 100 live rows and 0 tombstone cells
Asking for fewer rows does not change the kind of read. LIMIT 1 over the partition returns one row, but it is still a slice, so it still merges every file:
Read traceRead the newest row of the partition with LIMIT 1, traced
Real database outputAcquiring sstable references Skipped 0/5 non-slice-intersecting sstables, included 0 due to tombstones Key cache hit for sstable 1, size = 0 Key cache hit for sstable 2, size = 0 Key cache hit for sstable 3, size = 0 Key cache hit for sstable 4, size = 0 Key cache hit for sstable 5, size = 0 Merged data from memtables and 5 sstables Read 1 live rows and 0 tombstone cells
Compaction: paying the bill
Compaction merges SSTables into fewer, larger ones, keeping only the newest version of each value and, eventually, dropping deleted data. The lab triggers it by hand and repeats the partition read.
Database outputAfter a major compaction
Real database output--- 5. Compact: merge the five SSTables into one SSTable count: 1 Old SSTable count: 0 Space used (live): 150216
Read traceThe same partition read after compaction
Real database outputAcquiring sstable references Skipped 0/1 non-slice-intersecting sstables, included 0 due to tombstones Key cache hit for sstable 6, size = 0 Merged data from memtables and 1 sstables Read 100 live rows and 0 tombstone cells
Compaction is where an LSM tree pays its write amplification: the same data is read and rewritten each time it is merged. How often, and into what shape, is the compaction strategy. Cassandra 5.0's default is size-tiered (STCS), and its documentation recommends the newer Unified Compaction Strategy (UCS) for new workloads; leveled compaction (LCS) suits read-heavy or update-heavy tables, and time-window compaction (TWCS) suits mostly immutable time series with a TTL. For leveled compaction, the RocksDB documentation puts write amplification at "often larger than 10".
Architecture
Drawing diagram…
Two side-by-side flowcharts. In Postgres an update writes a WAL record, possibly with a full page image, and modifies the page in shared buffers, which is later written back to the same place in the data file. In Cassandra a write goes to an append-only commit log and a sorted memtable; the memtable is flushed into a new immutable SSTable, and compaction later merges SSTables into a new one and deletes the old files.
flowchart LR
subgraph PG["Postgres: B-tree, pages changed in place"]
direction TB
W1["UPDATE a row"] --> WAL1["WAL record, plus a full page image on the first change after a checkpoint"]
W1 --> BUF["Page in shared buffers modified in place"]
BUF --> DISK1["Same 8 kB page written back to its place in the file"]
end
subgraph CA["Cassandra: LSM tree, files never changed"]
direction TB
W2["Write a row"] --> CL["Commit log, append only"]
W2 --> MT["Memtable, sorted in memory"]
MT -->|flush| S1["New immutable SSTable"]
S1 -->|compaction| S2["Merged SSTable, old files deleted"]
end- In Postgres the page is the unit of everything: reading, caching, writing and crash protection. That is what makes the full-page image necessary and the lookup so cheap.
- In Cassandra the file is the unit, and files only ever get created and deleted. Nothing on disk is modified, which is why writes are sequential and why reads and disk space depend on how many files exist.
- Both write a log first for durability. The difference is what happens afterwards: Postgres writes the changed page back where it was, Cassandra writes the data again later, during flush and every compaction.
Step by step
Drawing diagram…
Sequence diagram. A client writes a row; the node appends it to the commit log and inserts it into the memtable, then acknowledges. Later the memtable is flushed into a new immutable SSTable. A read of one row checks the memtable and then SSTables newest first, stopping early. A read of a whole partition merges every SSTable that holds part of it. Compaction later merges the files.
sequenceDiagram participant C as Client participant N as Cassandra node participant M as Memtable participant L as Commit log participant S as SSTables on disk C->>N: Write total for order 7 of customer 42 N->>L: Append the mutation N->>M: Insert into the sorted memtable N-->>C: Acknowledged Note over M,S: Memtable full or flushed M->>S: Write as a new immutable SSTable C->>N: Read order 7 of customer 42 N->>M: Look in the memtable N->>S: Newest SSTable first, stop once the answer cannot be older C->>N: Read every order of customer 42 N->>S: Merge the partition from every SSTable that holds it Note over S: Compaction later merges the files into one
- The acknowledgement comes after the memory insert and the log append. With the default periodic sync, the log itself reaches disk within ten seconds.
- The point read and the partition read ask for overlapping data but cost very differently: one file against five in the lab. Query shape matters as much as data size in an LSM tree.
- Compaction is not on the request path, but it competes for the same disk and CPU. When it falls behind, files pile up and every partition read gets slower.
In a real system
Choose by the shape of the workload, not by the brand. A payments ledger or an orders service updates rows, needs transactions across tables, runs range queries and joins, and wants several secondary indexes: that is B-tree territory, and Postgres or MySQL are the usual answers. A metrics pipeline, an activity feed or a message history writes far more than it reads, rarely updates, and reads by a known key and time range: that is where an LSM engine like Cassandra shines.
- Heavy updates in Postgres: leave room on the page (a table fillfactor below 100) so updates can stay on the same page as heap-only updates, and avoid indexing columns that change often. Both reduce the WAL and index work you measured above.
- Checkpoint spacing: full-page images are written once per page per checkpoint, so less frequent checkpoints mean fewer of them, at the price of longer crash recovery (
checkpoint_timeout, default 5 minutes, andmax_wal_size, default 1 GB). - Cassandra reads: query by the full primary key whenever you can, keep partitions bounded, and watch SSTables-per-read. A partition spread over many files is slow to read even when each file is small.
- Compaction headroom: an LSM node needs spare disk for compaction to write its output before deleting its input, and spare I/O so that compaction keeps up with writes.
Wrong, then right
A fleet of 50,000 devices reports its state every few seconds into Cassandra. The dashboard shows each device's latest state. The first design stores every report and asks for the newest one.
Incorrect implementation
-- One partition per device, every report kept, newest first.CREATE TABLE telemetry.device_state ( device_id uuid, reported_at timestamp, status text, battery int, PRIMARY KEY (device_id, reported_at)) WITH CLUSTERING ORDER BY (reported_at DESC);-- The dashboard: the latest report of one device.SELECT status, batteryFROM telemetry.device_stateWHERE device_id = ?LIMIT 1;Why it is written this way
- Every report is a new row in the same partition, so one device's partition grows without limit and is spread across every SSTable flushed since the device started reporting.
LIMIT 1with a descending clustering order looks like a point read, but it is a slice: Cassandra cannot use the newest-first shortcut for it and has to consult every SSTable that holds part of the partition. The lab traced exactly this: one row returned, five SSTables merged.
Why it fails
- Reading "the latest row" of a partition is a slice query, the second kind of read in the lab: it merges the partition from every SSTable that holds it. The longer the device has reported, the more files that is between compactions.
- The partition never stops growing. Large partitions are slow to compact and slow to read, and a few chatty devices end up dominating the work of the nodes that own them.
- Nothing fails in testing, where each device has a handful of reports in one or two SSTables. The cost appears months later, in production, as rising read latency.
Corrected implementation
-- The latest state: one row per device, overwritten on every report.CREATE TABLE telemetry.device_latest ( device_id uuid PRIMARY KEY, reported_at timestamp, status text, battery int);-- History, if it is needed: bounded partitions, one per device per day.CREATE TABLE telemetry.device_history ( device_id uuid, day date, reported_at timestamp, status text, battery int, PRIMARY KEY ((device_id, day), reported_at)) WITH CLUSTERING ORDER BY (reported_at DESC);-- The dashboard: a read by the full primary key.SELECT status, battery FROM telemetry.device_latest WHERE device_id = ?;Why it is written this way
- The dashboard now names exactly one row, so the read takes the newest-first path from the lab and usually opens one SSTable however many reports there have been.
- Every report is written twice, once to each table. In an LSM engine that second write is cheap, and it is the usual price of modelling one table per query.
- History partitions are bounded by
(device_id, day), so no partition grows forever.
Trade-offs
- Two writes per report instead of one, and two tables to keep consistent. Cassandra will not do it in one transaction; a failed second write needs a retry.
- Overwriting the latest row still leaves older versions in older SSTables until compaction, so space amplification remains; it simply no longer slows the dashboard read.
- Questions the tables were not designed for, such as every device whose battery is below 10%, are not answerable efficiently from either table. That is the cost of designing tables from queries, covered in the data modelling lesson.
Configuration
The settings that decide how much each design writes and how its files are managed. Defaults are for PostgreSQL 18 and Cassandra 5.0.
fillfactor (Postgres table)Default 100
- What it does
- How full INSERT packs each table page. The remaining space is kept for updated row versions on the same page.
- When to change it
- Lower it (for example to 80 or 90) on heavily updated tables so that updates can be heap-only and avoid new index entries. Leave 100 for tables that are rarely updated.
fillfactor (Postgres B-tree index)Default 90
- What it does
- How full leaf pages are packed when the index is built and when it grows at the right-hand end.
- When to change it
- Rarely worth changing. Lower values delay page splits for random inserts at the cost of a bigger index.
full_page_writes (Postgres)Default on
- What it does
- Write the whole page to the WAL on its first change after each checkpoint, so a torn page can be repaired after a crash.
- When to change it
- Leave it on. The documentation warns that turning it off can lead to unrecoverable or silent data corruption after a failure.
checkpoint_timeout / max_wal_size (Postgres)Default 5min / 1GB
- What it does
- How often checkpoints happen, by time or by WAL volume.
- When to change it
- Raising them means fewer full-page images and less write amplification, at the cost of longer crash recovery.
commitlog_sync / commitlog_sync_period (Cassandra)Default periodic / 10000ms
- What it does
- Acknowledge writes before the commit log is synced, and sync it on this period.
- When to change it
- Durability within the window comes from replication. Use
batchif a single node must not lose acknowledged writes.
compaction class (Cassandra table)Default SizeTieredCompactionStrategy
- What it does
- How SSTables are merged: by similar size (STCS), into levels (LCS), by time window (TWCS), or the unified strategy (UCS).
- When to change it
- Pick by workload: UCS is the documented recommendation for new tables, LCS for read-heavy or update-heavy ones, TWCS for TTL'd time series.
Hands-on exercise
Measure both designs yourself
Run the lab against real Postgres 18 and Cassandra 5.0, and reproduce the tree height, the pages per lookup, the WAL cost of updates, and the SSTables a read has to merge before and after compaction.
Steps · 0 of 5 done
What you should see
Three index levels and 4 pages per lookup on a million rows (2 on a 100-row table); 99 MB of WAL for 781 kB of changed values right after a checkpoint, 77 MB of it full-page images, and 23 MB with almost no full-page images when repeated. In Cassandra, five SSTables after five flushes, a one-row read that opens only the newest SSTable, a partition read and a LIMIT 1 read that both merge five, and one SSTable at 150 kB instead of 706 kB after compaction. With fillfactor 80, most updates become heap-only and the WAL shrinks; your exact numbers will differ from ours.
What can go wrong
Reading LSM write speed as free
- Symptom
- Write latency is excellent for weeks, then read latency and disk usage climb while writes look unchanged.
- Cause
- The write cost was deferred to compaction, and compaction has fallen behind the write rate: SSTables per read and space used both grow.
- Fix
- Watch pending compactions and SSTables-per-read alongside write latency, leave disk and I/O headroom for compaction, and choose a compaction strategy for the workload.
Blaming the disk for a WAL spike after every checkpoint
- Symptom
- WAL volume and replication traffic jump right after each checkpoint, then fall.
- Cause
- Full-page images: each page's first change after a checkpoint is logged whole.
- Fix
- Confirm with
pg_get_wal_stats(pg_walinspect) that the spike is full-page images, then consider spacing checkpoints further apart. Do not turnfull_page_writesoff.
Indexing every column of an update-heavy Postgres table
- Symptom
- Updates get slower and the WAL grows as indexes are added, although reads are fine.
- Cause
- Updates that change an indexed column, or that cannot stay on the same page, must add an entry to every index.
- Fix
- Index for the queries you run, leave page space with a lower fillfactor, and check the HOT update ratio in
pg_stat_user_tables.
Modelling "latest value" as a slice of a growing partition
- Symptom
- A Cassandra query with
LIMIT 1gets slower month after month. - Cause
- It is a slice read over a partition spread across many SSTables, so it cannot take the newest-first shortcut.
- Fix
- Keep a separate table keyed by exactly what the query names, as in the corrected design above.
How to troubleshoot
A Postgres lookup is slower than its plan suggests
Check
EXPLAIN (ANALYZE, BUFFERS) <query>
- How to read it
shared hitpages came from memory,readpages from disk or the OS cache. A point lookup should touch a handful of pages; many more means the plan is not the one you think.
WAL volume is much larger than the data being changed
Check
SELECT * FROM pg_get_wal_stats('<start_lsn>', '<end_lsn>'); (extension pg_walinspect)- How to read it
- Compare
fpi_sizewithrecord_sizeper resource manager. Mostly full-page images means checkpoint spacing; mostly heap and index records means many new row versions and index entries.
Cassandra reads of one table are slow and getting slower
Check
nodetool tablehistograms <keyspace> <table> and nodetool tablestats <keyspace>.<table>
- How to read it
- SSTables per read in the high percentiles, and a growing SSTable count, mean reads are merging many files: look at compaction progress and at whether the queries are slices of large partitions.
You need to know which files one Cassandra read touched
Check
cqlsh> TRACING ON; then run the query
- How to read it
- Each "Partition index found for sstable N" is a file opened, and "Merged data from memtables and N sstables" is the total. One file for a point read is the healthy case.
Key takeaways
- A B-tree changes pages in place: lookups cost one page per level, and three levels already cover a million rows.
- In-place changes need a write-ahead log, and the first change to each page after a checkpoint logs the whole page: 99 MB of WAL for 781 kB of values in the lab.
- An LSM tree never edits a file: writes are appends and flushes, and old versions wait in older files for compaction.
- LSM reads by full key can stop at the newest file; slice and partition reads must merge every file that holds the partition.
- Each design pays somewhere: B-trees on writes, LSM trees on reads and space until compaction runs. Choose by which cost your workload can afford.
Practical check
Small scenarios, one decision each. Pick what you would do, then read why.
Scenario 1 of 3
An analytics service ingests 40,000 events a second. Events are never updated, are read back by device and time range for dashboards, and are deleted after 30 days. The team is choosing between Postgres and Cassandra.
Which choice and table design fit best?
Scenario 2 of 3
After a deploy, a Postgres primary writes about 3 GB of WAL in the minute after each checkpoint and much less for the rest of the cycle, although traffic is steady. Replicas fall behind for a minute every five minutes.
What explains the pattern, and what is a sound first change?
Scenario 3 of 3
A Cassandra table stores user settings with PRIMARY KEY (user_id, setting_name). Settings are overwritten often. Reading one setting with WHERE user_id = ? AND setting_name = ? is fast, but the settings page, which reads all settings of a user, slowed from 2 ms to 40 ms over a month. Autocompaction was disabled during a migration and never re-enabled.
Why is only the settings page slow?
References
References: PostgreSQL 18 documentation: B-Tree implementation (structure, page splits, deduplication) ↗ · PostgreSQL source, src/backend/access/nbtree/README (Lehman and Yao, right-links and high keys) ↗ · PostgreSQL 18 documentation: WAL configuration (full_page_writes, checkpoint_timeout, max_wal_size) ↗ · PostgreSQL 18 documentation: CREATE TABLE (table fillfactor) ↗ · PostgreSQL 18 documentation: CREATE INDEX (B-tree fillfactor, deduplicate_items) ↗ · PostgreSQL 18 documentation: pageinspect and pg_walinspect ↗ · Apache Cassandra 5.0 documentation: Storage engine (commit log, memtables, SSTables) ↗ · Apache Cassandra 5.0 documentation: Compaction overview (STCS, LCS, TWCS, UCS) ↗ · Apache Cassandra 5.0 source: SinglePartitionReadCommand (reading SSTables in timestamp order) ↗ · O'Neil, Cheng, Gawlick and O'Neil: The log-structured merge-tree (LSM-tree), Acta Informatica 33, 1996 ↗ · Lehman and Yao: Efficient locking for concurrent operations on B-trees, ACM TODS, 1981 ↗ · RocksDB wiki: Leveled compaction (write amplification) ↗ · Report a problem