DDIA Ch 3 — Notes & Questions

Chapter 3: Storage and Retrieval — Study Notes

How databases store the data you give them, and how they find it again when you
ask. As an application developer, this knowledge helps you pick the right storage
engine and reason about tuning parameters — even if you never build a database
yourself.

Two big themes run through the chapter: 1. OLTP vs. OLAP — two fundamentally different
workloads that demand different storage engines. 2. On the OLTP side, two schools of index
design: log-structured (append-only) vs. update-in-place (B-trees).

1. Data Structures That Power Your Database

The simplest database: an append-only log

The most basic key-value store is an append-only log — every write is appended to
the end of a file; reads scan for the latest value of a key.
Writes are O(1) and fast (sequential), but a naive read is O(n) — terrible at scale. You
need an index to make reads fast.
Key trade-off: an index speeds up reads but slows down writes and uses extra space.
Every index is overhead on writes. Well-chosen indexes speed up reads; you can’t
index everything for free.

Hash Indexes (Bitcask)

Keep an in-memory hash map mapping each key → byte offset in the data file.
Reads do one hash lookup + one disk seek (often served from the filesystem cache,
so no disk I/O).
Well suited to workloads with many writes per key but a small set of distinct keys
(e.g., a counter for cat-video play counts) — all keys must fit in RAM.

Managing disk space — segments + compaction: - Break the log into fixed-size
segments; close a segment when it hits a size threshold and write to a new one. -
Compaction = throw away duplicate keys in the log, keeping only the most recent value per
key. - Merging = combine several compacted segments into one. Done in a background
thread; old segments keep serving reads/writes until the merge completes, then are
atomically swapped and deleted. - Each segment has its own in-memory hash table;
lookups check the most recent segment first, then older ones. Merging keeps the number of
segments small.

Real-world implementation details: - File format: binary (length-prefixed strings) beats

CSV — faster, simpler, no escaping. - Deleting records: append a special deletion marker
called a tombstone; merging then discards prior values for that key. - Crash recovery: in-
memory hash maps are lost on restart. Bitcask stores snapshots of each segment’s hash
map on disk for fast reload (vs. re-reading whole segments). - Partially written records:
checksums detect and skip corrupted records from a mid-write crash. - Concurrency
control: typically one writer thread (writes are strictly sequential); immutable segments can
be read by many threads concurrently.

Why append-only is good (counterintuitive but powerful): - Sequential writes are much
faster than random writes (huge on spinning disks, still beneficial on SSDs). - Crash
recovery and concurrency are simpler — no risk of a half-overwritten value spliced from old
+ new data. - Merging avoids data-file fragmentation.

Limitations of hash indexes: - The hash table must fit in memory. On-disk hash maps
perform poorly (random I/O, costly to grow, fiddly collision handling). - Range queries are
inefficient — you must look up each key individually; can’t scan a key range.

2. SSTables and LSM-Trees

SSTables (Sorted String Tables)

Same as log segments, but the sequence of key-value pairs is sorted by key, and
each key appears once per merged segment.
Advantages over hash-indexed log segments:
1. Merging is simple & efficient even when files exceed memory — uses a
mergesort-style approach (read inputs side by side, copy lowest key). When a
key appears in multiple segments, keep the value from the most recent segment.
2. No need for a full in-memory index. A sparse index (one key per few KB of
file) suffices — find the key range, jump to the nearest known offset, and scan a
short distance.
 3. Compression of blocks — group records into a block, compress it, and point
the sparse index at the start of each compressed block. Saves disk space and
I/O bandwidth.

Constructing and maintaining SSTables

Writes go to an in-memory balanced tree (red-black or AVL tree), called a memtable

— accepts inserts in any order, reads back sorted.
When the memtable exceeds a threshold (a few MB), write it out to disk as a new
SSTable segment (efficient, already sorted). New writes go to a fresh memtable.
Reads: check memtable → most recent on-disk segment → older segments, in order.
A background process periodically merges and compacts segments.
Crash safety: keep a separate unsorted write-ahead log on disk that every write is
appended to; used only to restore the memtable after a crash. Discard the log once its
memtable is flushed.

LSM-Trees (Log-Structured Merge-Trees)

The scheme above is the LSM-tree, named by Patrick O’Neil et al. (1996), building on
log-structured filesystems.
Used in LevelDB, RocksDB (embeddable libraries), Cassandra, HBase (inspired by
Google’s Bigtable, which coined “SSTable” and “memtable”), and Lucene
(Elasticsearch/Solr full-text term dictionary).
Full-text indexing analogy: key = a term (word), value = the postings list (IDs of
documents containing the word), stored in SSTable-like sorted files.

Performance optimizations: - Bloom filters — a memory-efficient probabilistic set

membership structure. Tells you when a key definitely does not exist, avoiding wasted disk
reads for nonexistent keys (a known LSM weakness, since a missing key forces checking all
segments). - Compaction strategies: - Size-tiered: newer/smaller SSTables successively
merged into older/larger ones (HBase; Cassandra supports it). - Leveled: key range split
into smaller SSTables, older data moved into separate “levels”; more incremental, less disk
space (LevelDB, RocksDB; Cassandra supports it). - Rule of thumb: the basic idea — a
cascade of background-merged SSTables — works well even when the dataset far exceeds
memory, supports efficient range queries (sorted data), and sustains very high write
throughput (sequential writes).

3. B-Trees
 The most widely used indexing structure — standard in nearly all relational DBs and
many non-relational ones. Introduced 1970, called “ubiquitous” by 1979.
Like SSTables, B-trees keep keys sorted (good for lookups and range queries), but
the design philosophy is very different.

Structure

Break the database into fixed-size pages/blocks (traditionally 4 KB), read/write one
page at a time — matches the disk’s block layout.
Each page has an on-disk address, so pages can reference each other (like pointers
on disk), forming a tree.
One root page; each page holds keys + references to child pages; each child covers a
continuous key range. Look up a key by following references down to a leaf page
(holds values inline or references to them).
Branching factor = number of child references per page; typically several hundred.
Updates: find the leaf page, change in place, write the page back.
Inserts: find the page whose range covers the key; if no room, split the page into two
half-full pages and update the parent.
This keeps the tree balanced: depth is O(log n). Most DBs fit in 3–4 levels (a 4-level
tree of 4 KB pages, branching factor 500, holds ~256 TB).

Making B-trees reliable

Core operation is overwriting a page in place — sharply contrasts with append-only

LSM-trees. Risky: a multi-page operation (e.g., a split touching child + parent) can
leave a corrupted index (orphan page) if the DB crashes mid-write.
Write-ahead log (WAL, aka redo log): an append-only file every modification is
written to before being applied to tree pages. Used to restore consistency after a
crash.
Concurrency: in-place updates require careful control via latches (lightweight locks)
to prevent threads seeing inconsistent state. (LSM-trees are simpler here —
background merges + atomic segment swaps.)

B-tree optimizations

Copy-on-write (e.g., LMDB): write modified page to a new location, create a new
version of parent pages pointing to it — avoids the WAL and helps concurrency
control.
Abbreviate keys in interior pages (only need enough to act as range boundaries) →
higher branching factor, fewer levels (this is the B+ tree variant).
 Lay out leaf pages sequentially on disk to speed up range scans (hard to maintain
as the tree grows; LSM-trees do this more easily).
Add sibling pointers between leaf pages so range scans don’t return to parents.
Fractal trees borrow log-structured ideas to reduce disk seeks.

4. Comparing B-Trees and LSM-Trees

Rule of thumb: LSM-trees are typically faster for writes; B-trees are typically
faster for reads. But benchmarks are workload-sensitive — test with your own
workload.

LSM reads are slower because they may check the memtable plus several SSTables at
different compaction stages.

Advantages of LSM-trees

Lower write amplification (often): B-trees write data at least twice (WAL + page),
write whole pages even for tiny changes, and may double-write pages to survive
power failures.
Write amplification = one logical write causing multiple physical disk writes over
the DB’s lifetime. Critical on SSDs, which wear out after limited overwrites; also a
direct throughput cost in write-heavy apps (less disk bandwidth left for new
writes).
Sustain higher write throughput — sequentially write compact SSTables rather than
overwriting scattered pages (especially big on magnetic disks).
Better compression / smaller files — not page-oriented, periodically rewrite to
remove fragmentation (B-trees leave unused space in split/partly-full pages). Leveled
compaction has especially low storage overhead.

Downsides of LSM-trees

Compaction can interfere with ongoing reads/writes. Average impact is small, but
high-percentile (tail) response times can spike when a query waits on an expensive
compaction. B-trees are more predictable.
At high write throughput, disk bandwidth is shared between initial writes and
compaction. If compaction can’t keep up, unmerged segments pile up → disk fills,
reads slow (more segments to check). SSTable engines usually don’t throttle
incoming writes, so you need explicit monitoring.
 Each key exists in exactly one place in a B-tree (LSM may have multiple copies
across segments). This makes B-trees attractive for strong transactional semantics
— range locks can attach directly to the tree.

Bottom line: B-trees are mature and reliably good; log-structured indexes are increasingly
popular in new datastores. No easy rule — test empirically.

5. Other Indexing Structures

Primary vs. secondary indexes

Primary key index: uniquely identifies one row/document/vertex; other records

reference it by ID.
Secondary indexes: created via CREATE INDEX ; crucial for efficient joins. Keys are not
unique — handled either by making each value a list of row IDs (postings list) or by
appending a row ID to the key. Both B-trees and LSM-trees work as secondary
indexes.

Storing values within the index

The index value can be either the actual row, or a reference to it.
Heap file: rows stored in no particular order, separate from indexes. Avoids duplicating
data across multiple secondary indexes (each just points to the heap location). In-
place updates work if the new value isn’t larger; if larger, move the row and either
update all indexes or leave a forwarding pointer.
Clustered index: stores the row data directly within the index (extra hop to heap file
avoided). E.g., MySQL InnoDB primary key is always clustered; secondary indexes
reference the primary key.
Covering index / index with included columns: a compromise — stores some
columns in the index so certain queries can be answered from the index alone (the
index “covers” the query).
Trade-off: clustered/covering indexes speed up reads but cost storage and add write
overhead + consistency effort.

Multi-column indexes

Concatenated index: combines fields by appending one column to another (e.g.,

(lastname, firstname) ). Like a phone book — can query by lastname or (lastname,

firstname) , but useless for firstname alone.

 Multi-dimensional indexes: generalize to querying several columns at once —
important for geospatial data (e.g., 2D range query on latitude + longitude). A
standard B-tree/LSM can only constrain one dimension at a time.
Options: translate N dimensions into one number via a space-filling curve + B-
tree, or use specialized R-trees (e.g., PostGIS via PostgreSQL’s GiST).
Not just for geography — also useful for (red, green, blue) color search or
(date, temperature) weather queries (e.g., HyperDex).

Full-text search and fuzzy indexes

Handle similar (not exact) keys — misspellings, synonyms, grammatical variations,

proximity.
Lucene searches within an edit distance (Levenshtein distance). Its in-memory term-
dictionary index is a finite state automaton (trie-like), transformable into a
Levenshtein automaton for efficient fuzzy search. Beyond this lies document
classification / ML.

Keeping everything in memory

Disks are tolerated for two reasons: durability and lower cost per GB than RAM. As
RAM gets cheaper, many datasets fit entirely in memory → in-memory databases.
Caching-only (data loss on restart OK): Memcached.
Durable in-memory DBs: achieve durability via battery-backed RAM, writing a
change log to disk, periodic snapshots, or replication. Examples: VoltDB, MemSQL,
Oracle TimesTen (relational); RAMCloud (durable key-value); Redis, Couchbase (weak
async durability).
Counterintuitive insight: the speed advantage is not from avoiding disk reads (a
disk-based engine with enough RAM rarely reads disk anyway, thanks to OS caching).
It comes from avoiding the overhead of encoding in-memory structures into a
disk-writable form.
In-memory DBs also enable data models hard to do on disk (e.g., Redis priority
queues, sets).
Anti-caching: extend in-memory DBs beyond RAM size by evicting LRU data to disk
(like OS virtual memory, but at record granularity). Indexes still must fit in memory.
NVM (non-volatile memory) may reshape engine design in future.

6. Transaction Processing or Analytics?

OLTP vs. OLAP

OLTP (Online Transaction Processing): interactive, user-facing; low-latency

reads/writes; look up a small number of records by key. “Transaction” = a logical group
of reads/writes (does not necessarily imply ACID).
OLAP (Online Analytic Processing): scan huge numbers of records, read few
columns, compute aggregates (count, sum, avg) for business intelligence. Used by
internal analysts.

Property OLTP OLAP

Few records per query, by Aggregate over many

Read pattern
key records

Random-access, low- Bulk import (ETL) or event

Write pattern
latency (user input) stream

Internal analyst / decision

Used by End user via web app
support

Latest state (current point

Data represents History of events over time
in time)

Dataset size GB to TB TB to PB

Bottleneck Disk seek time Disk bandwidth

Data Warehousing

A data warehouse is a separate, read-only database optimized for analytics, so heavy

ad-hoc queries don’t harm critical OLTP systems. It holds a copy of data from all the
company’s OLTP systems.
ETL (Extract–Transform–Load): data is extracted (periodic dump or continuous
stream), transformed into an analysis-friendly schema, cleaned, and loaded into the
warehouse.
Common in large enterprises, rare in small ones (small data fits in a conventional SQL
DB or spreadsheet).
Divergence: warehouses and OLTP DBs both expose SQL, but internals differ —
vendors increasingly build separate storage/query engines under a shared SQL
interface. Vendors: Teradata, Vertica, SAP HANA, ParAccel (Amazon Redshift is
hosted ParAccel); SQL-on-Hadoop: Hive, Spark SQL, Impala, Presto, Drill (some
based on Google Dremel).
Stars and Snowflakes: Schemas for Analytics

Star schema (dimensional modeling): a central fact table where each row is an
event (e.g., a sale), surrounded by dimension tables (the
who/what/where/when/how/why). Fact-table columns are either attributes (price, cost)
or foreign keys to dimensions. Fact tables get huge (tens of PB at big retailers).
Snowflake schema: dimensions further broken into subdimensions (more
normalized). Star schemas are usually preferred — simpler for analysts.
Tables are often very wide — fact tables 100+ columns, dimension tables full of
metadata.

7. Column-Oriented Storage

Problem: fact tables are 100+ columns wide, but a typical analytic query touches only
4–5 columns and many rows. Row-oriented storage forces loading entire wide rows
from disk just to discard most columns.
Column-oriented storage: store all values from each column together (e.g., each
column in its own file) instead of all values from each row together. A query reads only
the columns it needs. Relies on each column file storing rows in the same order so
the kth entry in every column = the kth row.
Applies to non-relational data too (e.g., Parquet, a columnar format based on Dremel).

Column Compression

Column data is often repetitive → compresses well, reducing disk bandwidth demand.
Bitmap encoding: for a column with n distinct values, create n bitmaps (one per
value), one bit per row (1 = row has that value). Effective when distinct values are
few relative to rows (e.g., 100k products among billions of sales).
When bitmaps are sparse (large n), apply run-length encoding for very compact
storage.
Bitmap indexes make WHERE col IN (...) (bitwise OR of bitmaps) and WHERE a AND b

(bitwise AND) extremely fast — works because columns share row order.
Note: Cassandra/HBase “column families” (from Bigtable) are not truly column-
oriented — they store all columns of a row together and don’t use column
compression; the model is mostly row-oriented.

Memory bandwidth and vectorized processing

 Beyond disk→memory bandwidth, analytic DBs optimize memory→CPU-cache
bandwidth, avoid branch mispredictions/pipeline stalls, and use SIMD instructions.
Vectorized processing: operate on chunks of compressed column data that fit in the
L1 cache in tight loops (no per-record function calls). Compression lets more rows fit
in cache; operators (bitwise AND/OR) run directly on compressed chunks.

Sort Order in Column Storage

You can impose a sort order (like an SSTable) as an indexing mechanism — but the
whole row must be sorted together (sorting columns independently would break row
reconstruction).
The admin picks the sort columns based on common queries (e.g., date_key first if
queries filter by date; product_sk second to group same-product sales).
Sorting also aids compression: the first sort key gets long runs of repeated values
(run-length-encodable to a few KB even with billions of rows). The effect weakens for
second/third sort keys.
Several sort orders (C-Store / Vertica): since data is replicated for fault tolerance
anyway, store each replica sorted differently — pick the best-fitting copy per query.
Similar in spirit to multiple secondary indexes, but a column store holds values directly
(no pointers).

Writing to Column-Oriented Storage

Compression + sorting make writes harder — can’t update in place; inserting a row
mid-sort could require rewriting all column files (rows are identified by position, so all
columns must update consistently).
Solution: LSM-trees again. Writes go to an in-memory store (sorted), then are
merged with on-disk column files in bulk. Queries combine on-disk columns + recent
in-memory writes; the query optimizer hides this from the analyst.

Aggregation: Data Cubes and Materialized Views

Materialized view: an actual copy of a query’s results written to disk (vs. a virtual
view, just a query shortcut expanded on the fly). Caches frequently-used aggregates
so raw data isn’t re-crunched each time.
Must be updated when underlying data changes → makes writes more expensive;
rarely used in OLTP, more sensible in read-heavy warehouses.
Data cube / OLAP cube: a grid of aggregates grouped by several dimensions; each
cell = aggregate (e.g., SUM) for a dimension combination. Summarizing along an axis
reduces a dimension.
 Advantage: precomputed → some queries become very fast (e.g., total sales
per store, no row scanning).
Disadvantage: less flexible than raw data (can’t query a dimension that isn’t in
the cube, e.g., “sales of items over $100” if price isn’t a dimension). Keep raw
data; use cubes only as a performance boost.

Key Takeaways

Two workloads, two engine designs: OLTP (key lookups, seek-time bound, user-
facing) vs. OLAP (big scans, bandwidth bound, analyst-facing). The right storage
engine depends entirely on which you’re serving.
Indexes trade write speed for read speed — every index you add slows writes and
costs space; choose them deliberately.
Two OLTP schools: log-structured (append-only, never modify in place — Bitcask,
LSM-trees, LevelDB, Cassandra, HBase, Lucene) and update-in-place (B-trees, the
relational standard).
The core LSM insight: turn random writes into sequential writes, enabling high write
throughput on both disks and SSDs.
LSM vs. B-tree rule of thumb: LSM faster for writes (lower write amplification,
sequential writes, better compression); B-trees faster and more predictable for reads
(one copy per key, lower tail latency, easy range locks for transactions). Always
benchmark your own workload.
Watch write amplification — one logical write → many physical writes; matters for
throughput and SSD wear. Monitor LSM compaction so it doesn’t fall behind incoming
writes.
Index variety: secondary indexes (postings lists or appended row IDs), heap files
vs. clustered vs. covering indexes, concatenated and multi-dimensional (R-tree)
indexes, and fuzzy/full-text (Levenshtein automata) indexes.
In-memory DBs win not by skipping disk reads (the OS caches anyway) but by
avoiding the cost of converting in-memory structures to a disk format.
Data warehouses isolate analytics from OLTP via ETL; typically modeled as star
schemas (central fact table + dimension tables).
Column-oriented storage is the key analytics optimization: read only needed
columns, compress hard (bitmap + run-length encoding), exploit sort order and
vectorized/SIMD processing; use LSM-style buffering for writes and data
cubes/materialized views to precompute hot aggregates.
Chapter 3: Storage and Retrieval - Assessment
Questions

Section 1: Conceptual/Reasoning Questions

Question 1

Explain why LSM-trees generally achieve higher write throughput than B-trees, but may
exhibit worse read performance. What is the fundamental trade-off at play, and how does
this relate to the RUM Conjecture (Read, Update, Memory overhead)?

Question 2

Why does an append-only log design provide better crash recovery guarantees than an
update-in-place design? Describe at least three specific failure modes that in-place updates
must handle that append-only logs avoid.

Question 3

The chapter states that the performance advantage of in-memory databases is “not due to
the fact that they don’t need to read from disk.” Explain why this counterintuitive claim is
true, and what the actual source of their performance advantage is.

Question 4

Explain why column-oriented storage is well-suited for analytical (OLAP) workloads but
poorly suited for transactional (OLTP) workloads. What specific properties of each workload
type drive this distinction?

Question 5
Why do hash indexes require that all keys fit in memory, and why is it difficult to build a
performant on-disk hash map? Contrast this with how SSTables overcome these limitations
using a sparse in-memory index.

Question 6

Explain the concept of “write amplification” and why it matters differently for SSDs versus
magnetic hard drives. How does write amplification manifest differently in B-trees versus
LSM-trees?

Section 2: Scenario-Based Problems

Question 7

You are building an analytics system that ingests 1 TB/day of time-series sensor data
(timestamped readings from 10,000 IoT devices) and runs aggregate queries spanning
weeks of data (e.g., “average temperature per device per hour for the last 30 days”). Design
the storage approach, justifying your choices between: - Row-oriented vs. column-oriented
storage - Sort order for the columns - Compression strategy - Whether to use materialized
views or data cubes

Question 8

Your team maintains a key-value store using an LSM-tree engine (similar to RocksDB).
Users report that read latencies spike unpredictably to 200ms at the 99th percentile, even
though average latency is 2ms. The database has been running for several months with
high write throughput. Diagnose the likely root causes and propose solutions.

Question 9

You are designing a storage engine for a URL shortener service. The workload has these
characteristics: - 100 million distinct short URLs (keys) - Values are the original long URLs
(average 200 bytes) - Write pattern: 10,000 new URLs created per second - Read pattern:
100,000 lookups per second, heavily skewed toward recent URLs - Keys are never updated,
but may be deleted after expiration
Evaluate whether a Bitcask-style hash index, an LSM-tree, or a B-tree is most appropriate.
Justify your choice.

Question 10

A retail company has a data warehouse with a star schema. The fact table (fact_sales) has
50 billion rows and 120 columns. Analysts primarily run queries that: - Filter by date range
and store location - Aggregate quantity and revenue columns - Occasionally join with
dim_product (200,000 rows) and dim_store (5,000 rows)

The current row-oriented storage takes 45 minutes per query. Propose a column-oriented
storage design that would improve performance. Address sort order, compression, and how
writes to the fact table would be handled.

Question 11

You have a social media application where users can search for other users by geographic
proximity (latitude/longitude) AND by interest tags simultaneously. Standard B-tree indexes
exist on latitude and longitude separately but queries are slow. Propose an indexing strategy
and explain why a standard single-dimensional index is insufficient for this use case.

Section 3: Mathematical/Quantitative Questions

Question 12

A B-tree has a branching factor of 500 and uses 4 KB pages.

a. How many keys can be stored in a 4-level B-tree (including the root)?
b. If each leaf page is 70% full on average due to page splits, how much total disk space
does the index occupy for 1 billion keys?
c. What is the maximum number of disk reads needed to look up any key, assuming no
caching?

Question 13
Consider an LSM-tree with leveled compaction where: - Level 0 holds at most 4 SSTables of
64 MB each - Each subsequent level is 10x the size of the previous level - The size ratio
between levels is 10

a. What is the maximum data capacity of a 5-level LSM-tree (levels 0 through 4)?
b. If you write 1 GB of data, estimate the worst-case total write amplification across all
levels.
c. How many SSTables might need to be checked for a point read in the worst case
(without Bloom filters)?

Question 14

A Bloom filter is configured with: - m = 10 bits per element - k = 7 hash functions - n = 1

million elements inserted

a. Calculate the theoretical false positive rate using the formula: (1 - e(-kn/m))k
b. If the LSM-tree has 5 levels and each level has a Bloom filter with this false positive
rate, what is the expected number of unnecessary disk reads per lookup for a non-
existent key?
c. How would you reduce the false positive rate by a factor of 10, and what is the
memory cost?

Question 15

In a column-oriented data warehouse: - A column has 100 million rows - The column
contains product_sk values with 100,000 distinct values - Using bitmap encoding with run-
length encoding

a. What is the uncompressed size of the bitmap index (all bitmaps combined)?
b. If the data is sorted by product_sk, estimate the compressed size assuming perfect
run-length encoding (each run stored as a count + value in 4 bytes).
c. Compare this to storing the raw column as 4-byte integers.

Section 4: Compare & Contrast Questions

Question 16
Compare hash indexes (Bitcask-style), SSTables/LSM-trees, and B-trees across the
following dimensions. For each, state which approach is best and worst, with brief
justification:

Dimension Hash Index LSM-Tree B-Tree

Write throughput

Point read latency

Range query efficiency

Space efficiency

Crash recovery complexity

Predictability of latency

Question 17

Compare size-tiered compaction and leveled compaction strategies for LSM-trees across: -
Write amplification - Space amplification - Read amplification - Suitability for write-heavy
vs. read-heavy workloads

Provide specific examples of systems that use each strategy.

Question 18

Compare OLTP and OLAP systems across the following dimensions, and explain how each
dimension drives different storage engine design decisions: - Read pattern - Write pattern -
Dataset size - Bottleneck (disk seek vs. disk bandwidth) - Typical indexing approach - Data
model / schema design

Question 19

Compare clustered indexes, non-clustered (heap file) indexes, and covering indexes. For
each, explain: - How data is physically stored - The trade-off between read and write
performance - A use case where each is most appropriate
Section 5: Diagram/Trace Questions

Question 20

Trace the complete lifecycle of writing key “foo” with value “bar” to an LSM-tree-based
storage engine. Describe each step from the initial write request through eventual
compaction, including: 1. What happens in memory 2. What gets written to the write-ahead
log (WAL) 3. When and how the memtable is flushed to disk as an SSTable 4. How
compaction merges multiple SSTables 5. What happens during a subsequent read of key
“foo”

Draw or describe the state of the system after each step.

Question 21

Trace what happens when you insert key 42 into a B-tree where the target leaf page is
already full (capacity = 4 keys). The leaf currently contains keys [35, 37, 39, 41] and the
parent page has references with boundaries […, 30, 45, …]. Show: 1. The page split
operation 2. How the parent page is updated 3. What gets written to the write-ahead log 4.
How concurrent readers see a consistent state during the split

Answer Key

Answer 1

The fundamental trade-off is between write optimization and read optimization:

Why LSM-trees have better write throughput: - Writes go to an in-memory memtable

(fast, no disk I/O for the write itself) - When flushed, data is written sequentially as sorted
SSTable files - Sequential writes are 10-100x faster than random writes on HDDs and faster
on SSDs - No need to seek to a specific page location for each write

Why B-trees have better read performance: - Each key exists in exactly one place in the
index - Lookup requires traversing O(log n) pages (typically 3-4 disk reads) - With caching,
often only 1-2 disk reads needed
Why LSM-tree reads can be slower: - Must check memtable, then potentially multiple
SSTable levels - In the worst case, must check every SSTable at every level - Data for the
same key may exist in multiple places (only the newest is valid) - Bloom filters mitigate this
but add memory overhead

RUM Conjecture connection: You cannot simultaneously optimize Read, Update (write),
and Memory overhead. LSM-trees optimize for Updates (writes) at the expense of Reads. B-
trees optimize for Reads at the expense of Updates. Hash indexes optimize for both Reads
and Updates but at the expense of Memory (all keys must fit in RAM).

Answer 2

Crash recovery advantages of append-only logs:

1. No torn writes to existing data: With in-place updates, a crash during a page write
can leave the page in a corrupted state (partially old, partially new data). Append-only
logs never modify existing data, so previously written data remains intact.

2. No orphan pages from multi-page operations: B-tree page splits require writing 2-3
pages atomically. If a crash occurs after writing one split page but before updating the
parent, the tree becomes structurally inconsistent with orphan pages. Append-only
logs don’t have this problem.

3. Simple recovery protocol: Recovery simply means reading the log from the last
known good checkpoint. With in-place updates, you need a write-ahead log (WAL) and
potentially complex ARIES-style recovery protocols.

4. No fragmentation corruption: In-place updates can cause fragmentation where free-

space lists become corrupted. Append-only logs with compaction avoid this entirely.

5. Immutability enables concurrency: Append-only segment files can be read by

multiple threads without locks. In-place updates require latches to prevent readers
from seeing partially-written pages.

Answer 3

The counterintuitive truth: Even disk-based storage engines may never read from disk for
warm data because the operating system caches recently-used disk blocks in memory
(page cache). So both disk-based and in-memory databases may serve reads entirely from
RAM.

The actual performance advantage of in-memory databases comes from: 1. Avoiding

encoding/decoding overhead: Disk-based engines must encode in-memory data
structures into a format suitable for disk (page-aligned, serialized). In-memory databases
can use native in-memory data structures (pointers, trees, hash tables) without this
translation cost. 2. Supporting complex data structures easily: Redis can offer priority
queues, sets, sorted sets, etc. These would be complex to implement efficiently in a page-
oriented, disk-friendly format. 3. No page management overhead: No need to manage
fixed-size pages, handle page splits, or track free space within pages.

Answer 4

Column-oriented for OLAP: - Analytical queries access few columns (4-5 out of 100+) but
scan millions/billions of rows - Column storage reads only the needed columns, avoiding
loading 95+ irrelevant columns - Columns compress extremely well (same data type, many
repeated values) - Enables vectorized processing (tight loops over homogeneous data in
CPU cache) - Bitmap indexes enable fast AND/OR operations across columns

Poorly suited for OLTP because: - OLTP queries access full rows (all columns) for a few
records - Inserting a row requires writing to every column file (100+ files) - Column storage
cannot update in place; must use LSM-tree-style buffering - Each point lookup must
reassemble a row from separate column files

OLTP workload properties that drive row-storage: - Access entire records by key (one
seek, one read) - Insert/update entire records atomically - Low-latency requirements (disk
seeks, not bandwidth, are the bottleneck)

Answer 5

Why hash indexes require in-memory keys: - Hash tables require O(1) random access by
hash bucket. On disk, each lookup would require a random disk seek, making it far slower
than a tree structure. - Growing a hash table on disk requires rehashing (copying all entries),
which is extremely expensive. - Hash collisions require following chains of pointers, each
potentially causing a disk seek.
How SSTables overcome this with a sparse index: - Keys are stored sorted on disk. A
sparse in-memory index stores offsets for every Nth key (e.g., one per few KB). - To find a
key, binary search the sparse index to find the bracketing entries, then scan a small range
on disk. - Memory required: only O(data_size / block_size) entries, not O(number_of_keys).
- Example: 1 TB of data with 4 KB blocks needs ~250 million index entries, much smaller
than storing all keys. - Additionally, SSTables support efficient range queries (just scan the
sorted file), which hash indexes cannot.

Answer 6

Write amplification = ratio of total bytes written to disk vs. bytes written by the application.

In B-trees: - Every write goes to the WAL (1x) and to the page (1x) = at minimum 2x
amplification - Full 4 KB page rewritten even for a tiny change (e.g., 100 bytes modified =
40x amplification for that page) - Page splits cause additional writes (split page + parent
update) - Some engines write pages twice for torn-write protection (doublewrite buffer) -
Typical B-tree write amplification: 10-30x

In LSM-trees: - Initial write to WAL + memtable flush = 1x + 1x base - Each compaction

level rewrites data: with 10 levels and size ratio 10, worst case ~10x per level - Total worst-
case write amplification with leveled compaction: ~10-30x (varies by strategy) - But each
write is sequential (much faster per byte on both HDD and SSD)

Why it matters differently: - SSDs: Limited write endurance (program/erase cycles).

Higher write amplification directly reduces SSD lifespan. Also, SSDs must erase large blocks
before rewriting, adding internal amplification. - HDDs: Write amplification mainly impacts
throughput (bandwidth is finite), but random writes are far worse than sequential. LSM-trees’
sequential writes are 10-100x faster than B-trees’ random writes, partially offsetting their
amplification.

Answer 7

Recommended design:

Column-oriented storage – Queries access only a few columns (timestamp, device_id,

temperature) out of potentially many sensor attributes. Column storage avoids reading
irrelevant columns across billions of rows.
Sort order: - Primary sort key: timestamp (date_key) – queries filter by time range, so
sorting by time allows scanning only relevant time periods - Secondary sort key: device_id –
groups same-device readings together within a time period, enabling efficient per-device
aggregation

Compression: - First sort column (date) will have extremely long runs of repeated values
(all readings in the same second/minute share a date) – use run-length encoding - device_id
as second sort key will also have good runs – bitmap encoding with RLE - Numeric sensor
values: delta encoding (adjacent readings from same device will be similar) - Estimated
compression: 10-20x for sorted columns

Materialized views / data cubes: - Pre-compute hourly averages per device as a

materialized view (most common query pattern) - Data cube dimensions: (time_hour,
device_id) with aggregated metrics - This reduces the 30-day query from scanning ~30
billion rows to ~7.2 million pre-aggregated rows - Keep raw data for ad-hoc queries not
covered by the cube

Write handling: - Use LSM-tree approach: buffer incoming writes in memory, periodically
merge with column files on disk - Batch writes in time-sorted chunks before flushing (natural
for time-series) - 1 TB/day = ~12 MB/s sustained write throughput, manageable with periodic
bulk flushes

Answer 8

Likely root causes:

1. Compaction falling behind: High write throughput has caused many unmerged
SSTables to accumulate. Reads must check more SSTables, and occasional
compaction I/O contends with read I/O.

2. Compaction interference: When a large compaction job runs, it consumes disk

bandwidth, causing concurrent reads to wait. This manifests as latency spikes at high
percentiles.

3. Space amplification: Multiple versions of the same key exist across levels before
compaction merges them, increasing data scanned per read.

Solutions:
 1. Monitor compaction debt: Track the number of SSTables per level. If L0 SSTables
exceed the configured maximum, compaction is falling behind. Increase compaction
thread count or reduce write rate.

2. Rate-limit compaction I/O: Configure compaction I/O rate limits to prevent it from
monopolizing disk bandwidth, trading slower compaction for more predictable read
latency.

3. Tune Bloom filters: Increase Bloom filter bits per key (e.g., from 10 to 14 bits) to
reduce false positive rate, avoiding unnecessary disk reads.

4. Switch compaction strategy: If using size-tiered compaction, consider switching to

leveled compaction for more predictable read performance (fewer SSTables to check
per read).

5. Add read caching: A block cache can absorb reads for hot data, avoiding SSTables
entirely.

6. Consider compaction priority scheduling: Use I/O priority classes to give reads
higher priority than background compaction.

Answer 9

Best choice: Bitcask-style hash index

Justification:

Key count fits in memory: 100M keys x ~20 bytes (short URL + offset) = ~2 GB in-
memory hash map. Feasible for modern servers.
Write pattern is append-only: New URLs are created but never updated. This maps
perfectly to Bitcask’s append-only log with hash index.
Point lookups only: URL shorteners never need range queries. Hash indexes provide
O(1) lookups.
High read throughput: Single disk seek (or memory-mapped cache hit) per lookup.
Much faster than LSM-tree which may check multiple levels.
Skew toward recent URLs: Hot URLs will be in the OS page cache from the most
recent segment files.
Deletions via tombstones: Expired URLs can be removed during segment
compaction.
Why NOT LSM-tree: - Write amplification from compaction is unnecessary overhead for
append-only workload - Multiple SSTables may need checking per read (slower than hash
O(1)) - Sorted order provides no benefit (no range queries needed)

Why NOT B-tree: - Random writes for each insertion (slower than sequential append) -
Page splits add unnecessary overhead - WAL + page write = 2x write amplification for every
insert - Tree traversal (3-4 reads) is slower than hash (1 read) for point lookups

Answer 10

Column-oriented storage design:

Physical layout: - Store each of the 120 columns in a separate file - Each column file
contains 50 billion values in the same row order

Sort order: - Primary sort: date_key (queries filter by date range; scanning last month =
~1/12 of data) - Secondary sort: store_sk (queries filter by location; groups same-store sales
together) - This ensures the two most common filter dimensions have the best data locality

Compression: - date_key (primary sort): Run-length encoding achieves extreme

compression (e.g., all sales on one day form a single run – possibly millions of entries
compressed to a few bytes) - store_sk (secondary sort): Bitmap encoding with RLE (5,000
distinct values, sorted grouping creates long runs) - quantity, revenue: Dictionary encoding +
delta/frame-of-reference encoding - Expected overall compression: 10-20x (from ~2.4 TB
raw to ~150-250 GB compressed)

Write handling: - Use LSM-tree approach: incoming writes buffer in a row-oriented in-
memory store - Periodically (e.g., hourly or when buffer reaches threshold), sort new records
and merge-write into column files - Queries automatically check both the in-memory buffer
and on-disk columns

Performance improvement: - A query accessing 3 columns reads 3/120 = 2.5% of data

(vs. 100% in row storage) - Date-sorted storage means scanning 1 month = 1/12 of column
files - Net reduction: ~0.025 * 0.083 * compression_ratio = reading ~0.02% of original data -
Estimated query time improvement: from 45 minutes to under 1 minute

Answer 11
Why standard single-dimensional indexes fail: - A B-tree on latitude can narrow results to
a latitude band, but then must scan all longitudes within that band (or vice versa) -
Combining two independent indexes via bitmap intersection helps but is still suboptimal –
you retrieve many false positives that match one dimension but not the other - Adding
interest tags as a third dimension makes it even worse

Proposed indexing strategy:

1. Geospatial component: Use an R-tree or a space-filling curve (e.g., geohash, Hilbert

curve) to convert 2D (lat, lng) into a single sortable dimension that preserves proximity.
This enables efficient spatial range queries.

2. Multi-dimensional approach: Use a compound index with geohash prefix + interest

tag. This allows queries like “all users with interest ‘hiking’ within geohash prefix ‘dp3t’”
to be answered with a single index scan.

3. Alternative: HyperDex-style multi-dimensional indexing that partitions the key

space across multiple dimensions simultaneously, allowing queries to narrow down by
both location and attributes in a single pass.

The key insight is that multi-dimensional queries require indexes that understand spatial
relationships between dimensions rather than treating each dimension independently.

Answer 12

(a) Keys in a 4-level B-tree: - Level 0 (root): 1 page with up to 500 keys and 501 child
pointers - Level 1: 501 pages with up to 500 keys each - Level 2: 501 * 501 = 251,001 pages
- Level 3 (leaves): 501^3 = 125,751,501 pages

Total keys (all at leaves for a B+ tree): 501^3 * 500 = 62,875,750,500 (approximately 63
billion keys)

Alternatively, total keys across all pages: 500 * (1 + 501 + 501^2 + 501^3) = 500 *
126,003,003 = approximately 63 billion keys

The chapter’s simpler approximation: 500^4 = 62.5 billion key references traversable, storing
up to approximately 256 TB with 4 KB pages.

(b) Disk space at 70% utilization: - For 1 billion keys in leaf pages: 1B / (500 * 0.7) = 1B /
350 = ~2,857,143 leaf pages - Internal pages: ~2,857,143 / 350 = ~8,163 at level above,
~23 above that, 1 root - Total pages: ~2,865,330 - Total disk space: ~2,865,330 * 4 KB =
~11.2 GB

(c) Maximum disk reads: 4 reads (one per level: root -> level 1 -> level 2 -> leaf). In
practice, the root and often level 1 are cached in memory, so typically 1-2 actual disk reads.

Answer 13

(a) Maximum capacity of 5-level LSM-tree (levels 0-4): - Level 0: 4 * 64 MB = 256 MB -

Level 1: 256 MB * 10 = 2.56 GB (or starting from a base, but typically Level 1 = 10x L0
capacity) - Level 2: 25.6 GB - Level 3: 256 GB - Level 4: 2.56 TB

Total: ~2.56 TB + 256 GB + 25.6 GB + 2.56 GB + 256 MB approximately equals 2.84 TB

(b) Write amplification for 1 GB of data:

In leveled compaction, data at each level is rewritten when it is compacted into the next
level. The amplification per level is approximately equal to the size ratio (10) because
merging one SSTable from level L into level L+1 may require rewriting up to 10 SSTables at
level L+1 that overlap with its key range.

L0 -> L1: ~10x (merge with overlapping L1 SSTables)

L1 -> L2: ~10x
L2 -> L3: ~10x
L3 -> L4: ~10x

Worst-case total write amplification: ~10 * 4 = 40x (data is rewritten 10 times at each of 4
level transitions). Plus the initial write (WAL + L0 flush) = 2x. Grand total: ~42x.

For 1 GB of application writes: approximately 42 GB total disk writes in the worst case.

(c) SSTables to check for a point read (without Bloom filters): - Level 0: up to 4
SSTables (overlapping key ranges) - Level 1: 1 SSTable (non-overlapping within a level) -
Level 2: 1 SSTable - Level 3: 1 SSTable - Level 4: 1 SSTable

Total worst case: 4 + 1 + 1 + 1 + 1 = 8 SSTables, plus the memtable = 9 locations to check.

Answer 14
(a) False positive rate:

Formula: P(false positive) = (1 - e(-kn/m))k

Here m = 10 bits/element * 1,000,000 elements = 10,000,000 bits total, n = 1,000,000, k = 7.

P = (1 - e^(-7 * 1,000,000 / 10,000,000))^7 P = (1 - e(-0.7))7 P = (1 - 0.4966)^7 P =

(0.5034)^7 P = approximately 0.0082 (about 0.82%)

(b) Expected unnecessary disk reads:

For a non-existent key, every level’s Bloom filter is checked. A false positive at any level
triggers an unnecessary disk read.

Expected unnecessary reads = 5 * 0.0082 = 0.041

On average, about 1 in 24 lookups for non-existent keys will cause one unnecessary disk
read. (More precisely: expected number = sum of P per level = 5 * 0.0082 = 0.041.)

(c) Reducing false positive rate by 10x:

Target: P approximately equals 0.00082.

The false positive rate approximately halves for each additional bit per element. To reduce
by 10x (approximately 2^3.3), add about 3-4 bits per element.

New configuration: ~13-14 bits per element (up from 10).

Memory cost: 14 bits * 1,000,000 = 14 Mbit = 1.75 MB per level, compared to 1.25 MB
previously. Total increase across 5 levels: from 6.25 MB to 8.75 MB (an additional 2.5 MB of
memory).

This is an excellent trade-off: 2.5 MB of extra memory eliminates ~90% of unnecessary disk
reads.

Answer 16

Dimension Hash Index LSM-Tree B-Tree

Write throughput Best – O(1) append Good – sequential Worst –

to log, sequential writes to random I/O for
 Dimension Hash Index LSM-Tree B-Tree
memtable/SSTables page updates
+ WAL

Good – O(log
Worst – may check
Best – single O(1) n) tree
Point read latency memtable +
hash lookup traversal, 2-4
multiple SSTables
reads

Good – sorted Best – sorted

Range query Worst – impossible
SSTables support leaf pages with
efficiency (no ordering)
efficient scans sibling pointers

Moderate –
Best – compaction
Worst – all keys in page
removes duplicates,
Space efficiency memory + log fragmentation,
compressed
fragmentation ~70% page
SSTables
utilization

Moderate – rebuild Simple – WAL for Moderate –

Crash recovery hash map from log memtable, WAL replay to
complexity (slow) or use SSTables fix partially-
snapshots immutable written pages

Good –
Worst –
consistent tree
Predictability of Best – consistent compaction causes
depth, no
latency O(1) lookups periodic latency
background
spikes
compaction

Answer 17

Size-tiered compaction (used by HBase, Cassandra option): - Write amplification: Lower

– SSTables merge only when enough same-size tables accumulate - Space amplification:
Higher – multiple copies of same key can exist across different-sized tiers simultaneously;
may need 2x space during compaction - Read amplification: Higher – many overlapping
SSTables may exist per tier, requiring checking more files - Best for: Write-heavy workloads
where write throughput is critical and temporary space overhead is acceptable
Leveled compaction (used by LevelDB, RocksDB, Cassandra option): - Write
amplification: Higher – each level transition rewrites data ~10x due to merge with existing
level - Space amplification: Lower – each key exists in at most 2 places (one per level
being compacted); ~10% overhead - Read amplification: Lower – non-overlapping
SSTables within each level means at most 1 SSTable per level to check - Best for: Read-
heavy workloads or space-constrained environments where predictable read performance
matters

Summary trade-off: Size-tiered optimizes for write throughput at the cost of space and read
efficiency. Leveled optimizes for read performance and space at the cost of write
amplification.

Answer 18

Dimension OLTP OLAP Design Implication

Small Aggregate
OLTP: B-tree/LSM index for key
number of over
Read pattern lookup. OLAP: Sequential scan,
records by millions/billions
column storage
key of records

Random,
Bulk import OLTP: Fast random writes
low-
Write pattern (ETL) or event needed. OLAP: Batch writes OK,
latency,
streams optimize for read
user-driven

OLAP requires compression and

Dataset size GB to TB TB to PB
efficient encoding at scale

OLTP: Minimize seeks (index to

Disk seek Disk exact page). OLAP: Maximize
Bottleneck
time bandwidth throughput (column compression,
sequential reads)

B-trees, Sparse
OLTP: Precise lookup indexes.
LSM-trees, indexes, sort
Indexing OLAP: Broad filtering
hash order, bitmap
mechanisms
indexes indexes
 Dimension OLTP OLAP Design Implication

Normalized Star/snowflake
OLAP: Optimized for joins along
(3NF), schema,
Schema dimension tables, wide fact
application- denormalized
tables
specific fact tables

Key insight: The fundamental difference is that OLTP is latency-sensitive with small
working sets, while OLAP is throughput-sensitive with large working sets. This drives
completely different storage engine architectures.

Answer 19

Clustered index (e.g., InnoDB primary key): - Storage: Row data is stored directly within
the index leaf pages, sorted by the clustering key. No separate heap file. - Trade-off: Reads
by primary key are fastest (no extra hop to heap file). But secondary indexes must store the
primary key (not a direct pointer), requiring a second lookup. Writes must insert into sorted
position. - Best for: Tables primarily accessed by primary key; when row data is needed
immediately upon lookup.

Non-clustered / heap file index: - Storage: Index leaf pages store pointers (file offset) to
rows in a separate heap file. Heap file has no particular order. - Trade-off: Multiple
secondary indexes can share one heap file (no data duplication). Writes are fast (append to
heap). But reads require an extra I/O hop from index to heap. Updates that grow a record
may require forwarding pointers. - Best for: Tables with many secondary indexes where
avoiding data duplication is important.

Covering index (index with included columns): - Storage: Index leaf pages store the
indexed column(s) plus additional “included” columns, but not the full row. - Trade-off:
Queries that only need the included columns are answered entirely from the index (no heap
access). But the index is larger and writes must update both the index and any included
columns. - Best for: Specific high-frequency queries that always access the same small set
of columns (e.g., SELECT email FROM users WHERE username = ?).

Answer 20

Step-by-step trace of writing key=“foo”, value=“bar” to an LSM-tree engine:

Step 1: Write-Ahead Log (WAL) - The write (foo -> bar) is immediately appended to an on-
disk WAL file (sequential write) - Purpose: durability guarantee – if the process crashes
before memtable flush, the write can be recovered - State: WAL contains “PUT foo bar” entry

Step 2: Memtable Insert - The key-value pair is inserted into the in-memory memtable (a
balanced tree structure, e.g., red-black tree) - The key “foo” is placed in sorted position
among other keys - State: Memtable = {…, “foo” -> “bar”, …} (sorted by key) - The write is
now acknowledged to the client

Step 3: Memtable Flush (when threshold reached, e.g., 4 MB) - When the memtable
exceeds its size threshold, it is written to disk as a new SSTable file - The SSTable is written
sequentially (already sorted from the tree structure) - A sparse index for this SSTable is
created (offsets for every Nth key) - The corresponding WAL entries are discarded - A new
empty memtable is created for incoming writes - State: Disk has SSTable-1 containing
sorted entries including “foo” -> “bar”

Step 4: Compaction (background process) - Over time, multiple SSTables accumulate at

Level 0 - Compaction merges overlapping SSTables into a new, larger SSTable - Merge
uses multiway merge sort: reads all input SSTables in parallel, outputs sorted - For duplicate
keys across SSTables, keeps only the newest value - Old SSTables are deleted after
successful merge - State: “foo” -> “bar” now lives in a compacted SSTable at a deeper level

Step 5: Reading key “foo” 1. Check memtable (O(log n) tree lookup) – if found, return
immediately 2. Check Bloom filter for most recent SSTable – if negative, skip it 3. If Bloom
filter says “maybe,” search the sparse index for bracketing keys, then scan the data block 4.
Repeat for older SSTables until found 5. Return the most recent value encountered

Answer 21

Initial state: - Leaf page P1: [35, 37, 39, 41] (full, capacity = 4) - Parent page: […, ref(P1),
45, ref(P2), …] - Key 42 should go in P1 (between boundary 30 and 45)

Step 1: Write to WAL - Before modifying any pages, write the intended operation to the
write-ahead log: “INSERT key=42 into page P1 -> SPLIT” - This ensures recovery is
possible if crash occurs mid-operation

Step 2: Page Split - P1 is full, so split it into two pages: - P1 (left): [35, 37] (first half) - P3
(right, new page): [39, 41, 42] (second half, including new key) - Split point chosen to
balance the pages (here: after key 37)
Step 3: Parent Page Update - Parent page must be updated to include the new child
reference: - Before: […, 30, ref(P1), 45, ref(P2), …] - After: […, 30, ref(P1), 39, ref(P3), 45,
ref(P2), …] - The new boundary key “39” indicates: keys < 39 go to P1, keys >= 39 go to P3

Step 4: Pages Written to Disk Three pages are written (in order protected by WAL): 1. New
page P3: [39, 41, 42] 2. Modified page P1: [35, 37] 3. Modified parent page with new
reference to P3

Step 5: Concurrent Reader Consistency - With latches (locks): The pages involved in
the split are protected by lightweight locks. Readers must acquire a shared latch before
reading; the writer holds an exclusive latch during the split. Readers block briefly. - With
copy-on-write (LMDB approach): The split creates entirely new page versions. A new root
path is constructed pointing to the new pages. Readers continue using the old pages until
the new root is atomically installed. No blocking required. - WAL ensures: If the system
crashes after writing P3 but before updating the parent, recovery replays the WAL to
complete the split.

Final state:

Parent: [..., 30, ref(P1), 39, ref(P3), 45, ref(P2), ...]

P1: [35, 37]
P3: [39, 41, 42]