Your service writes ten times more than it reads. Which storage engine would you pick, and why?

An LSM-tree. Writes go to a log and a memory table, then are flushed as sorted files in sequential writes, so they are cheap. Reads are slower because they may check several files, which filters and compaction reduce. The trade-off is read cost and background compaction work against write speed. Be ready to add that compaction rewrites data, so the engine writes more bytes than the application sent (write amplification). The gain is mostly sequential instead of random I/O, not always fewer bytes.

What is a write-ahead log and how does it make a write durable?

The engine appends each change to a log on disk and flushes it before acknowledging the write, then updates the real structure later. After a crash it replays the log to rebuild what was in memory. The trade-off is one extra sequential write per change, which is cheap.

Why not just index every column?

Every index must be updated on every insert, update and delete, and it takes space and memory. Too many indexes slow writes and may confuse the planner. Index the columns used in your real queries, in the right order for composite indexes. The trade-off is read speed against write cost.

A query on a large table is slow. How do you find out why and fix it?

Look at the query plan to see whether it scans the whole table or uses an index. If it scans, add an index on the filtered or sorted columns, in the right order, and check the plan again. Consider a covering index if the query needs only a few columns. The trade-off is a slower write path and more storage.

What is compaction in an LSM-tree and what problems can it cause?

Compaction merges sorted files into larger ones, removes deleted and overwritten values, and reduces how many files a read must check. It uses disk and CPU in the background, and can cause latency spikes or write stalls if it falls behind. The trade-off is read speed and space against background I/O.

Storage Internals and Indexing

Why storage internals matter, and when to care

Every database sits on a storage engine that decides how data is laid out on disk, how an update is made safe, and how a lookup finds a row. Two designs dominate: the B-tree, which updates pages in place, and the LSM-tree (log-structured merge-tree), which appends writes and merges them later. Knowing the difference explains why one database is fast at reads and another at writes, and how an index helps.

It gives you two things interviewers always ask about:

Performance: which engine and which indexes fit a workload that is read-heavy, write-heavy or mixed.
Durability: how a write survives a crash, through a write-ahead log.

Care about this when:

You choose a database for a write-heavy or read-heavy service and must justify it.
A query is slow and you need to decide which index to add.
You must explain how data survives a crash.

Skip it, or use something else, when:

The data is small enough to fit in memory and any database is fine.
A managed database already makes the choice, and the workload is ordinary.

Try it

Run a workload against each engine and compare the disk work. Then crash it.

Storage Internals and Indexing

Step 1 of 14 · Press Space to play, arrow keys to step

EngineWorkload

Initial state. A B-tree keeps keys sorted in pages on disk and updates pages in place. Every change is logged first.

tick:: 0
write I/O:: 0
read I/O:: 0
merge I/O:: 0
lost writes:: 0

1 tick = one step of the simulation.

Speed

Things to try:

Run B-tree with the mixed workload. Every write rewrites a page in place, and every read walks the same few pages.
Switch to LSM-tree on write-heavy and compare write I/O. Then run read-heavy and see reads check more files.
Choose Crash after 5 writes with both engines and watch the log bring the data back.

What to watch:

The I/O numbers are relative units, not milliseconds. A log append and a page write each count as one unit, so the sequential versus random difference is explained by the captions rather than priced in.
Compare the total at the end, not only write I/O. The LSM-tree moves cost into the merge I/O counter, so its write I/O alone flatters it.
The B-tree is simplified: each write is charged a page write, whereas a real engine may keep the page in memory for a while and write it later. The LSM-tree has no per-file filters, so its reads look worse here than the table above suggests.
Before you press play, predict which engine will have the lower total on each workload, then check.

Storage engine designs

Design	How it works	Good when	Weakness
B-tree	Sorted pages in a tree. A write finds the page and updates it in place	Read-heavy and mixed workloads, range scans	Random writes, and pages that split
LSM-tree	Writes go to memory, then flush as sorted files that are merged in the background	Write-heavy workloads, time series, logs	Reads may check several files, and compaction uses I/O
Hash index	A hash table maps keys to locations	Exact-match lookups only	No range queries, and in simple designs the table of keys must fit in memory
Column store	Each column is stored together	Analytics that scan a few columns	Slow for single-row updates
Append-only log	Data is only added at the end	Event streams	Needs another structure to look up by key

Terms used here:

Page: the fixed-size block (often a few kilobytes) that a B-tree reads and writes.
Memory table (memtable): the sorted in-memory buffer where an LSM-tree holds recent writes.
Checkpoint: a point up to which changes are known to be safely on disk, so older log records are not needed.
Filter: a small structure, usually a Bloom filter, that says a key is definitely not in a file, so the file can be skipped.
Query plan: the database's chosen way to run a query, such as a table scan or an index lookup.

B-tree vs LSM-tree

B-tree: a read costs the depth of the tree, a handful of pages. The depth grows only slowly as the table grows. A write is a random disk write, and a page may need to split. Most relational databases use it.
LSM-tree: a write is an append to a log and an insert in memory, which is cheap. The cost moves to reads, which may check the memory table and several files, and to compaction, which merges files in the background. Many NoSQL and time-series stores use it.

Neither is better. Pick by the workload, then remember both use the same safety idea: the write-ahead log.

The cost shows up as amplification, meaning extra work for each byte the application writes or reads:

Write amplification: compaction rewrites data several times, and a B-tree rewrites a whole page for a small change. For illustration, a row of 100 bytes might cause a page of several kilobytes to be rewritten.
Read amplification: an LSM-tree read may check the memory table and several files, while a B-tree read walks one page per level.
Space amplification: old versions stay on disk until compaction removes them, and a B-tree leaves pages part empty after splits.

An LSM-tree usually turns random writes into sequential ones, but it does not always write fewer bytes in total.

How a write survives a crash

The engine first appends the change to the write-ahead log (WAL) on disk and waits for it to be flushed.
Only then does it tell the client the write succeeded.
It updates the page (B-tree) or the memory table (LSM) afterwards, which may sit in memory for a while.
After a crash, the engine replays the log from the last checkpoint and repairs or rebuilds whatever was in memory.
Old log records are trimmed after a checkpoint (B-tree) or after a flush (LSM).

This is why the log is written sequentially and first: appending is fast and its order tells the engine what to replay. "Flushed" means the operating system was told to force the bytes to the disk (an fsync), not just to hold them in a buffer. A write acknowledged before that point can be lost in a power cut.

How indexes help

An index is an extra sorted structure that maps a column's values to rows, so a query does not scan the table.

A primary index orders the table itself in some engines. InnoDB (MySQL) stores the table in primary-key order, while PostgreSQL keeps rows in a separate heap and treats the primary key as an ordinary index.
A secondary index is a separate structure on another column. It speeds up reads but adds work to every write, because each index must be updated.
A composite index on several columns helps queries that filter on the leading columns, in that order.
A covering index contains every column a query needs, so the table is not read at all.

Add indexes for the queries you really run, and no more.

Storage design vs the alternatives

Concern	B-tree engine	LSM-tree engine	Plain files with a scan
Point reads	Fast and steady	Fast with filters	Slow
Heavy writes	Slower	Fast	Fast to append
Range scans	Fast	Good	Slow
Background work	Little	Compaction	None
Predictable latency	Mostly (page splits and checkpoints can still stall)	Spikes during compaction	Poor
Best for	General databases	Write-heavy stores	Small data

Choose a B-tree as the default, and an LSM-tree when writes dominate.

Avoiding a new single point of failure

The storage engine is on one machine, so durability beyond that machine needs replication: copy the log to other nodes before acknowledging, or to a standby. Keep the log on reliable disks, take backups, and test restores. You accept a slower write when it waits for another copy. If the copy is made asynchronously, the write is acknowledged sooner, but a crash of the primary can lose the latest writes that had not yet arrived.

Common mistakes

Indexing every column. Each index slows every write and uses space.
Wrong column order in a composite index. It helps only for queries using its leading columns.
Skipping the log flush for speed. A crash can then lose acknowledged writes.
Choosing an LSM-tree for a read-heavy workload without checking read amplification.
Ignoring compaction. It competes for I/O and can cause latency spikes.
Never testing recovery. A backup you have never restored is a hope, not a plan.

How to talk about storage internals in an interview

State the workload first: reads versus writes, point lookups versus ranges.
Name the engine type and its cost: B-tree for steady reads, LSM-tree for heavy writes.
Explain the write-ahead log as the reason a write is durable.
Add indexes for the main queries and name the trade-off: faster reads cost slower writes and more space.

Where you meet storage engines and indexes in real systems

PostgreSQL and MySQL's InnoDB use B-trees. Cassandra, RocksDB and many time-series databases use LSM-trees. Here are three drawn out, the first with SQL you can run, then more examples.

Example 1: Adding an index and checking the query plan

An index turns a full scan into a lookup, and the query plan shows which one the database chose. Open the example below to see the picture and the SQL.

Config: an index and its query planSetup 1 table and 2 indexesCode no code changes

Without an index the database reads every row. With one it walks a few pages of the index and goes straight to the matching rows.

CREATE TABLE users (
  id         bigserial PRIMARY KEY,   -- the primary key gets a B-tree index automatically
  email      text NOT NULL,
  country    text NOT NULL,
  created_at timestamptz NOT NULL DEFAULT now()
);

-- 20,000 sample rows so the planner has something to choose between.
INSERT INTO users (email, country)
SELECT 'user' || g || '@example.com', (ARRAY['IN','US','DE','BR'])[1 + g % 4]
FROM generate_series(1, 20000) AS g;
ANALYZE users;

-- Without an index on email, this query scans the whole table (Seq Scan).
EXPLAIN SELECT * FROM users WHERE email = 'user777@example.com';

-- A B-tree index on email turns the lookup into an index scan.
CREATE INDEX users_email ON users (email);
EXPLAIN SELECT * FROM users WHERE email = 'user777@example.com';

-- A composite index helps queries filtering on country, then sorting or filtering by created_at.
-- The leading column is country, so a query on created_at alone will not use it well.
CREATE INDEX users_country_created ON users (country, created_at);
EXPLAIN SELECT id FROM users WHERE country = 'IN' ORDER BY created_at LIMIT 10;

-- Every index must be updated by every write. Drop the ones you do not use.

The PostgreSQL SQL was run against a real PostgreSQL 16 server: the first plan was a sequential scan and, after the index, an index scan. The MySQL SQL was run against a real MySQL 8 server. Names and sizes are examples. The MySQL table is tiny, and on a table that small the optimiser may choose a full scan, so load many more rows before expecting to see the index in the plan.

Example 2: Reading an LSM-tree

A read checks the newest data first, then older files, and gives up early when a small filter says the key is not in a file.

A read checks the memory table first, then each file from newest to oldest. A filter per file lets the engine skip files that cannot hold the key.

Example 3: Compaction

Files pile up as data is flushed. Compaction merges several into one larger file, so reads have fewer places to look.

Four small files hold overlapping keys. Merging them leaves one larger sorted file, so a read checks one place instead of four.

More real-world scenarios

4. Relational databases

In MySQL InnoDB the table itself is a B-tree ordered by the primary key, and secondary indexes are further B-trees. In PostgreSQL the rows sit in an unordered heap and every index, including the primary key, is a separate B-tree that points into it. Either way, an index lookup walks the tree, and a range query follows leaf pages in order.

5. Time-series and metrics

Data arrives constantly and is rarely changed. An LSM-tree absorbs the writes, and old data can be dropped by deleting whole files when data is grouped by time window or partition, so no row-by-row delete is needed.

6. Message logs

Brokers append records to the end of a log file and index offsets sparsely, which is the simplest and fastest storage layout.

7. Embedded storage

Many applications embed an LSM-tree library to store local state, because writes are fast and files are easy to ship.

8. Analytics warehouses

Columns are stored together and compressed, so a query touching three columns of a hundred reads only those.

9. Search engines

Documents are indexed into immutable segments that are merged later, which is the same idea as an LSM-tree.

10. Caches with persistence

A cache can write each change to an append-only log and rebuild itself by replaying it after a restart.

Tools and managed services

Kind	Name	Notes
B-tree databases	PostgreSQL, MySQL (InnoDB)	General purpose, strong range queries
LSM-tree databases	Apache Cassandra, RocksDB, LevelDB	Write-heavy workloads
Embedded	SQLite, RocksDB	Storage inside an application
Managed	Amazon RDS, Amazon Aurora, Google Cloud SQL, Azure Database	Hosted relational databases
Managed	Amazon DynamoDB	Hosted key-value store

The takeaway

Whenever a design depends on how fast data can be written or found, ask which storage engine it uses, and remember that every write is first made safe in a log. Three ideas to take away: pick the engine by the workload (steady reads suit a B-tree, heavy writes suit an LSM-tree), pay for every index on every write, and treat durability as the log being flushed before the acknowledgement.

Storage Internals and Indexing

Key takeaways

Why storage internals matter, and when to care

Try it

Storage Internals and Indexing

Storage engine designs

B-tree vs LSM-tree

How a write survives a crash

How indexes help

Storage design vs the alternatives

Avoiding a new single point of failure

Common mistakes

How to talk about storage internals in an interview

Where you meet storage engines and indexes in real systems

Example 1: Adding an index and checking the query plan

Example 2: Reading an LSM-tree

Example 3: Compaction

More real-world scenarios

4. Relational databases

5. Time-series and metrics

6. Message logs

7. Embedded storage

8. Analytics warehouses

9. Search engines

10. Caches with persistence

Tools and managed services

The takeaway

Interview questions