Chapter 2 taught you how applications model data. Chapter 3 flips the perspective: once you hand data to a database, how does the database store it, find it again, and keep query performance acceptable as the dataset grows? This lesson covers the core storage-engine ideas behind modern systems: append-only logs, hash indexes, SSTables, LSM-trees, B-trees, secondary indexes, in-memory databases, and the entirely different world of OLAP/data-warehouse storage with columnar formats.
Interview relevance: when someone asks "Why Cassandra over MySQL?" or "Why is ClickHouse fast for analytics?" the real answer lives in this chapter. Data-model discussions are incomplete unless you also understand the storage engine underneath.
At the most fundamental level, a database must do two things:
As an application developer, you usually do not implement storage engines yourself. But you do choose between them and tune them. That requires a rough mental model of what they do under the hood. The chapter's big split is this:
| Workload | Optimization target | Typical bottleneck | Typical storage style |
|---|---|---|---|
| OLTP | Low-latency point reads/writes | Disk seek time / write amplification / concurrency | B-trees, LSM-trees, log-structured KV stores |
| OLAP | Huge scans and aggregates | Disk and memory bandwidth | Column-oriented storage |
Kleppmann begins with a deliberately tiny key-value store implemented as two shell functions:
db_set () { echo "$1,$2" >> database; }
db_get () { grep "^$1," database | sed -e "s/^$1,//" | tail -n 1; }
This is profoundly important because it exposes the essence of many real systems.
db_set simply appends a key-value pair to a file. If a key is
updated, the new value is appended; the old one remains. To read, db_get scans
for all matching keys and keeps the last one.
The lesson: raw appends are great for writes, terrible for reads. Most storage engines are fundamentally trying to preserve the write-friendliness of append-only logs while adding metadata that avoids full scans on reads.
An index is an additional data structure derived from the primary data. It acts like a signpost so the storage engine can jump to relevant records instead of scanning blindly.
But an index is not free. Every index must be maintained on every write.
| Benefit | Cost |
|---|---|
| Faster reads | Slower writes |
| New query patterns | Extra storage |
| Less scanning | More metadata to keep consistent |
This is one of the central design laws of databases: good indexes speed up reads, but every index slows down writes. That is why databases do not usually index everything by default.
The first improvement over the shell-script database is to keep an in-memory hash map from
key -> byte offset in the log file. When a new key-value pair is appended, the
hash map is updated to point at the new offset. A read does one hash lookup, one file seek,
and one value read.
This is essentially what Bitcask (Riak's default storage engine) does.
Bitcask-style engines are excellent when you have:
Example: key = cat-video URL, value = play count. Many writes per key, but total key cardinality still manageable.
Since append-only logs never reclaim space by themselves, Bitcask-style engines split the log into segments. Once a segment reaches a certain size, it is frozen and a new segment becomes active.
Background compaction then:
Each segment keeps its own in-memory hash map. On lookup, the engine checks the newest segment first, then older ones until the key is found.
| Problem | Solution |
|---|---|
| CSV is slow/awkward | Use a binary format with explicit lengths. |
| Deletes | Append a tombstone record; compaction later removes older values. |
| Crash recovery | Persist snapshots of the hash maps or reconstruct them from segments. |
| Partial writes | Store checksums to detect truncated/corrupt records. |
| Concurrency | Often one writer thread, many reader threads. |
kitty00000 to kitty99999.
Takeaway: Bitcask-style hash indexes are ideal for exact-key, update-heavy workloads with a manageable number of distinct keys. They are not general-purpose indexing structures.
The key improvement over raw segmented logs is simple but powerful: require each segment file to be sorted by key. This creates a Sorted String Table (SSTable).
| Property | Unsorted log + hash index | SSTable |
|---|---|---|
| Exact lookup | Fast | Fast |
| Range scans | Poor | Excellent |
| Memory required for index | High (all keys) | Lower (sparse index) |
| Merging segments | Harder | Like mergesort; straightforward |
handbag and handsome, you can seek near them and scan to find
handiwork.
The trick is: sort in memory, not directly on disk.
This architecture is the core of LSM-trees (Log-Structured Merge-Trees), used by LevelDB, RocksDB, Cassandra, HBase, and inspired by Bigtable. Lucene uses a very similar segment-merge idea for search indexes.
| Optimization | Purpose |
|---|---|
| Bloom filters | Fast negative lookups: avoid touching many SSTables when a key does not exist. |
| Size-tiered compaction | Merge smaller newer SSTables into larger older ones. |
| Leveled compaction | Split key ranges into levels; compaction is more incremental and space-efficient. |
Mental model: an LSM-tree is a cascade of increasingly larger sorted files. New data accumulates in memory, gets flushed to disk, and is gradually merged downward in the background.
LSM-trees are increasingly popular, but the dominant indexing structure in mainstream databases remains the B-tree. Unlike log-structured engines, B-trees are page-oriented and use update-in-place semantics.
To look up key 251, for example, the engine starts at the root page, follows the
child pointer for the range 200..300, then continues downward until it reaches
the relevant leaf page.
Each page points to many children. This is the branching factor, typically several hundred. Because the tree is so wide, it stays shallow. A four-level B-tree with 4 KB pages and branching factor ~500 can store around 256 TB.
Update-in-place is inherently riskier than append-only. A multi-page update can leave the tree corrupted if the database crashes halfway through. Example: a page split writes two child pages and must also rewrite the parent. If the crash happens after some but not all writes, the tree may contain orphan pages or broken references.
The standard solution is a write-ahead log (WAL), also called a redo log:
B-trees also require careful concurrency control, usually with latches (lightweight locks), because concurrent threads may otherwise see the tree in an inconsistent intermediate state.
Mental model: a B-tree treats disk as rewritable fixed-size pages; an LSM-tree treats disk as append-only sorted files. This philosophical difference drives almost every performance tradeoff between them.
| Dimension | LSM-tree | B-tree |
|---|---|---|
| Write pattern | Mostly sequential appends + background merges | Random page overwrites |
| Read path | May consult memtable + multiple SSTables | Single tree path to leaf |
| Write throughput | Usually better, especially on write-heavy workloads | Usually lower |
| Read predictability | Can suffer due to compaction and multiple segments | Often more predictable |
| Space efficiency | Often better compression, less fragmentation | More fragmentation / partially empty pages |
| Strong transactional semantics | Harder in some designs due to duplicate keys across levels | Often easier; one key in one place fits lock/range semantics well |
No universal winner: the right choice depends on workload. LSM-trees often win on write-heavy ingestion. B-trees often win where read predictability, mature transactional behavior, or conventional relational semantics matter most. Always benchmark with your real workload.
So far the discussion has mostly been about key-value indexes, analogous to a primary key. But relational systems rely heavily on secondary indexes as well.
In a secondary index, the indexed key is not unique. Two common representations:
Both B-trees and log-structured indexes can be used as secondary indexes.
| Design | Description | Tradeoff |
|---|---|---|
| Heap file + indexes | Indexes point to rows stored elsewhere in no particular order. | Avoids duplication, but requires an extra hop on reads. |
| Clustered index | The full row is stored directly in the index. | Faster reads, more duplication/maintenance cost. |
| Covering index | Index stores only some extra columns, enough to answer certain queries. | Middle ground: covers some queries without full row duplication. |
InnoDB uses a clustered primary key index. SQL Server lets you choose one clustered index per table.
A concatenated index combines multiple columns into one composite key. Like a
phone book indexed by (lastname, firstname), it is good for prefix-based lookups
but useless for arbitrary permutations.
For truly multidimensional queries, such as geospatial range searches on
(latitude, longitude), you often need specialized indexes such as
R-trees or techniques like space-filling curves.
Multidimensional indexing is not just for maps. You can index by:
(date, temperature) for weather queries.(red, green, blue) for color-range search in ecommerce.Exact-match and range indexes cannot answer "similar word" questions. Full-text search requires different structures:
Lucene uses SSTable-like sorted files for its term dictionary, but the in-memory index is an automaton/trie-like structure rather than a sparse key list. It can be transformed into a Levenshtein automaton for fast edit-distance search.
Disk-based structures exist because disks are durable and cheap per GB, but awkward and slower than RAM. As RAM gets cheaper, many datasets are small enough to keep fully in memory.
Some systems are cache-only (Memcached), where data loss on restart is acceptable. Others aim for durability using:
Key point: an in-memory database can still write to disk and still be considered in-memory if the disk is used only for durability and all reads are served from memory.
Surprisingly, the main speedup is not merely "no disk reads." Even disk-based systems often serve hot data from the OS page cache. The bigger win is avoiding the overhead of encoding data into disk-centric structures.
In-memory systems can also expose richer native data structures, as Redis does with sets, sorted sets, and priority-queue-like abstractions.
Recent research explores the opposite of classic caching: keep the working set in memory, but evict cold records to disk when RAM is insufficient. The database manages this more efficiently than the OS because it works at record granularity rather than memory-page granularity.
The second half of the chapter changes gears completely. The storage structures that make OLTP fast are often not the ones you want for analytics.
| Property | OLTP | OLAP |
|---|---|---|
| Main reads | Small number of records by key | Aggregates over huge scans |
| Main writes | Random, low-latency user-driven writes | Bulk import / ETL / event ingestion |
| Users | End users/customers | Internal analysts |
| Data meaning | Latest state | History over time |
| Size | GB to TB | TB to PB |
OLTP workloads need low latency per request. OLAP workloads care about scanning and aggregating efficiently across very large datasets.
Large enterprises typically keep OLTP systems separate from analytics systems. The analytics side is the data warehouse:
This process is ETL (Extract-Transform-Load). The main benefit is isolation: analysts can run expensive ad hoc queries without risking the performance or availability of production OLTP systems.
Analytics tends to be more standardized in its data modeling than OLTP. A common design is the star schema:
In the grocery-retailer example, each row in
fact_sales represents a purchase event. Dimensions include product, store, date,
promotion, and customer.
A snowflake schema further normalizes the dimensions into subdimensions. It is more normalized but often less convenient for analysts than a simpler star schema.
Important distinction: OLTP typically optimizes for current state and transaction integrity; OLAP typically preserves raw historical events because future analyses are unpredictable.
In a fact table with 100+ columns and trillions of rows, a typical analytical query may need only 4 or 5 columns. That makes traditional row-oriented storage wasteful.
| Storage layout | Best for | Why |
|---|---|---|
| Row-oriented | OLTP | Entire record is loaded together; ideal when a request touches one row at a time. |
| Column-oriented | OLAP | Only the columns used by a query are read; massive savings on scan-heavy workloads. |
In a column store, each column is stored separately, but in the same row order. That means the 23rd value in every column belongs to the same logical row.
Column-oriented layouts naturally create repetitive sequences. One especially important technique is bitmap encoding:
n distinct values, create n bitmaps.If the bitmaps are sparse, run-length encoding makes them extremely compact.
Analytical predicates translate into bitwise operations:
WHERE product_sk IN (30, 68, 69) becomes bitmap OR.WHERE product_sk = 31 AND store_sk = 3 becomes bitmap AND.
Because all columns preserve row order, the kth bit in each bitmap corresponds to
the same row.
Column stores are not just about disk bandwidth. They also align well with modern CPUs:
This is called vectorized processing and is one of the reasons modern analytical databases are so fast.
Rows in a column store can be physically ordered by chosen sort keys, even though data is stored by column. This helps both scans and compression.
date_key is the first sort key, recent-date queries can scan only relevant
ranges.
product_sk is the second sort key, product-specific grouping/filtering
within a date becomes more efficient.
C-Store and Vertica exploit replication cleverly: since data must be replicated anyway, different replicas can be stored with different physical sort orders. Then different query types can use the replica whose ordering fits them best.
This is analogous to having multiple secondary indexes, but stronger: instead of pointers into one canonical row store, the full columnar data is materialized in different sort layouts.
Columnar compression and sorting make updates-in-place awkward. Inserting a row into the middle of sorted column files could force rewriting huge amounts of data.
The chapter's answer is elegant: reuse the earlier idea from LSM-trees.
Vertica uses this basic pattern.
If analysts repeatedly ask similar aggregate questions, recomputing them from raw data every time can be wasteful. A materialized view stores the actual query result on disk.
| Type | What it stores | Tradeoff |
|---|---|---|
| Virtual view | Only the query definition | No storage duplication, but recomputes on read |
| Materialized view | A physical copy of the query result | Much faster reads, but writes/refresh are more expensive |
A special case is the data cube (OLAP cube), which stores pre-aggregated values across multiple dimensions.
For example, a cube might precompute sales by:
This can make some queries extremely fast, such as "total sales per store yesterday." But cubes only help for dimensions that were preselected. If you later ask, "What fraction of sales came from items over $100?" and price was not a cube dimension, the cube cannot answer it.
Core tradeoff: materialized aggregates trade flexibility for speed. Raw event data stays the long-term source of truth; cubes and materialized views are accelerators for common questions.
| If your workload looks like... | Lean toward... | Why |
|---|---|---|
| Exact-key lookups, many updates per key, moderate key cardinality | Bitcask-style hash index | Very fast append-heavy exact lookups |
| Write-heavy KV store with range scans | LSM-tree | Sequential writes + sorted files + scalable compaction |
| General-purpose relational workload with mature transaction semantics | B-tree | Stable, predictable, fits locking and conventional SQL engines |
| Huge analytical scans over wide fact tables | Columnar OLAP engine | Read only the needed columns; compress aggressively |
| Low-latency hot dataset that fits in RAM | In-memory database | Avoid disk-centric overheads entirely |
When asked about storage choices in interviews, structure your answer like this:
Sample interview framing: "For the user-facing serving path I'd choose an LSM-tree-backed store because writes are heavy and range scans matter. For downstream analytics I would ETL into a separate columnar warehouse, because OLTP indexes are the wrong tool for full-table aggregations."
1. Why is the shell-script database fast on writes but slow on reads?
Sequential appends cheap; lookups scan whole file Compression overhead on reads Data is already sorted by key2. What is the biggest limitation of a Bitcask-style hash index?
Deletes are impossible All keys must fit RAM; range scans are weak Sequential writes are inefficient3. What turns sorted files into an LSM-tree?
Only adding a write-ahead log Memtable flushes to SSTables plus background compaction Page splits and child pointers4. Why do B-trees need a write-ahead log?
Crash-safe recovery for multi-page in-place updates To compress leaf pages To make reads faster than LSM-trees5. Why are LSM-trees often faster for writes?
They convert many random writes into sequential writes They never rewrite data They always read fewer structures than B-trees6. What is the main physical advantage of column-oriented storage for analytics?
Faster point lookups by primary key Only needed columns are read and parsed Cheaper random in-place updates7. Why do bitmap indexes work so well in warehouses?
Compact repeated values and fast bitwise filtering They preserve exact insertion order for OLTP writes They enforce unique constraints across dimensions8. When should you separate OLTP and OLAP systems?
Only when the OLTP system lacks SQL When scan-heavy analytics would hurt transactional latency Only in small companies with little dataUnderstand how DB stores data + finds it again → choose right engine for workload
db_set ⇒ append key,value to file ; writes cheap
db_get ⇒ scan whole file, keep last occurrence ; reads O(n)
Index ⇒ extra metadata for fast lookup ; reads faster → writes slower
In-memory hash map: key → byte offset in append-only log
Best for ⇒ many updates/key, exact-key lookups, manageable key cardinality
Segments ⇒ freeze old file, append to new file
Compaction ⇒ discard duplicate old values ; keep newest only
Tombstone ⇒ delete marker used during merge
Limits ⇒ all keys fit RAM ; range queries ×
SSTable ⇒ segment sorted by key ; key appears once per merged segment
Advantage ⇒ sparse index enough ; range scans easy ; merge like mergesort
Memtable ⇒ in-memory balanced tree holding recent writes
Write path: write → memtable + crash log ; flush memtable → SSTable ; background compaction merges levels
Bloom filter ⇒ fast "key absent" check
Compaction v/s Latency :- compaction good long-term ; can hurt p99
Fixed-size pages ; root/internal/leaf pages ; sorted key ranges
Branching factor ⇒ hundreds ; tree shallow
Write path: find leaf ; overwrite/update ; split page if full ; update parent
WAL ⇒ append redo log before page overwrite ; recover after crash
Latches ⇒ lightweight locks for concurrent access
LSM ⇒ better writes, sequential I/O, better compression ; reads may check multiple SSTables
B-tree ⇒ stronger read predictability, mature transactions, key exists in one place
Write amplification ⇒ one logical write causes multiple physical writes over time
No universal winner → benchmark real workload
Secondary index ⇒ non-unique key ; points to row IDs or appends row ID to key
Clustered index ⇒ row stored inside index
Covering index ⇒ enough columns inside index to answer query without heap lookup
Concatenated index ⇒ (a,b,c) as one key ; prefix lookups work
Multi-dimensional index ⇒ geospatial or multi-axis filtering
Disk awkward but durable + cheap ; RAM fast but volatile
In-memory DB can still write append-only log to disk for durability ; reads still from RAM
Speedup mostly from avoiding disk-centric data-structure overhead, not only from skipping disk reads
OLTP ⇒ few rows/query, user-facing, latest state, seek time bottleneck
OLAP ⇒ millions of rows/query, analyst-facing, historical events, bandwidth bottleneck
Data warehouse ⇒ separate read-only copy built via ETL
Star schema ⇒ central fact table + surrounding dimension tables
Store each column together, not each row together
Query touches few columns → read only those files
Bitmap encoding ⇒ one bitmap/value ; use OR / AND for filters
Vectorized processing ⇒ operate on compressed chunks in cache ; SIMD friendly
Sort rows by chosen keys → better scans + better compression
Writes hard in sorted compressed columns → use LSM-style in-memory write path then merge
Materialized view ⇒ stored query result ; faster reads, more expensive writes
Data cube ⇒ precomputed aggregates across dimensions ; very fast for known questions ; flexibility ×
Primary source: Kleppmann, M. (2017).
Designing Data-Intensive Applications, Chapter 3: “Storage and
Retrieval.” O'Reilly Media.
Recommended supplements: O'Neil et al. on LSM-Trees, Graefe on modern B-tree
techniques, and Abadi et al. on column-oriented DBMS design.
Questions? Ask your agent about any storage-engine choice, benchmark tradeoff, or how to answer an interview question like "Why Cassandra?" or "Why a warehouse instead of querying production directly?"