Storage and Retrieval

Fullscreen

---

Starting with the Simplest Storage Engine

A two-function bash key-value store: db_set appends key,value to a file; db_get greps for the last occurrence of a key.

• Writes are fast because appending to a file is efficient. Many real databases use a log internally, here "log" means an append-only sequence of records on disk (not human-readable application logs).
• Reads are terrible: O(n). db_get scans the whole file. Double the data, double the lookup time.
• An index solves this: an extra structure derived from the primary data that makes lookups fast.
• The fundamental trade-off: well-chosen indexes speed up reads but consume disk space and slow down writes (every write must also update the index). So databases don't index everything by default, you choose indexes based on query patterns.

---

Log-Structured Storage

Hash index (in-memory)

Keep an in-memory hash map: key → byte offset of the most recent value in the log.

Fullscreen

Fast (a read may need no disk I/O if the block is cached), but four problems:

• Old log entries are never freed → you can run out of disk.
• The hash map isn't persisted → slow restart (rebuild by scanning the log).
• The hash table must fit in memory (on-disk hash maps perform poorly: random I/O, expensive to grow, collision logic).
• Range queries are inefficient (must look up each key individually).

SSTables (Sorted String Tables)

Keep the key-value pairs sorted by key, each key appearing once.

• You no longer need every key in memory: group records into a few-KB blocks and keep a sparse index storing the first key of each block. To find handiwork, seek to the block starting at handbag (since handbag < handiwork < handsome) and scan that block.
• Blocks can be compressed, saving disk space and I/O bandwidth at a small CPU cost.

Building and merging SSTables (the LSM-tree)

A hybrid of an append-only log and a sorted file:

Fullscreen

1. Writes go to an in-memory ordered structure (memtable, red-black tree, skip list, or trie).
2. When the memtable exceeds a threshold (a few MB), flush it to disk as a new SSTable segment; keep serving writes into a fresh memtable.
3. Reads check the memtable, then the newest segment, then older ones, until found (or not).
4. A background compaction process merges segments (like mergesort), keeping only the most recent value per key.

• A write-ahead log (WAL) on disk records every write immediately, so the memtable can be rebuilt after a crash. It's discarded once its data is in an SSTable.
• Deletes append a tombstone; compaction uses it to discard older values, then drops the tombstone once merged into the oldest segment.
• This is the LSM-tree (Log-Structured Merge-tree), used by RocksDB, Cassandra, ScyllaDB, HBase, all inspired by Google's Bigtable (which coined "SSTable" and "memtable").
• Segments are immutable once written → simple crash recovery (just delete an unfinished SSTable), and they're well suited to object storage (SlateDB, Delta Lake), not just local disk.

Bloom filters

Reading a missing or long-untouched key is slow (must check many segments). A Bloom filter per segment gives a fast, probabilistic membership check:

• Hash each key to several bit positions; set those bits to 1.
• To test a key, hash it and check those bits. If any bit is 0, the key is definitely absent (skip the segment). If all bits are 1, it's probably present (a false positive is possible).
• Rule of thumb: ~10 bits per key → ~1% false-positive rate; every +5 bits/key cuts the rate tenfold.
• False positives are harmless here, you just do a little extra work checking the segment.

Compaction strategies

Embedded storage engines run in your process (a library, not a network service), reading/writing local files: RocksDB, SQLite, LMDB, DuckDB, KùzuDB. Common in mobile apps, and useful on the backend when data fits one machine, e.g., one embedded DB per tenant in a multitenant system.

---

B-Trees

The most widely used index structure (1970; "ubiquitous" by 1979). Standard in almost all relational DBs. Like SSTables, B-trees keep keys sorted (good for lookups and range queries), but the design philosophy is opposite.

• B-trees break the DB into fixed-size pages (traditionally 4 KiB; PostgreSQL 8 KiB, MySQL 16 KiB) and overwrite pages in place (vs LSM's immutable, append-only segments).
• Each page has a page number acting as an on-disk pointer. Pages form a tree.

Fullscreen

• Start at the root, follow child references whose key range contains your key, down to a leaf page (which holds values inline or references to them).
• Branching factor = number of child references per page (typically several hundred).
• Inserts: add to the right leaf; if full, split the page into two half-full pages and update the parent (splits can cascade up, even creating a new root). This keeps the tree balanced, depth O(log n). A 4-level tree of 4 KiB pages with branching factor 500 stores ~250 TB.

Making B-trees reliable

• Overwriting pages in place is risky: a crash mid-split can corrupt the tree (orphan pages), and hardware may produce a torn page (partial write).
• Solution: a write-ahead log (WAL) (a.k.a. journaling in filesystems), every modification is appended to the WAL before being applied to tree pages, so a crash can be recovered.
• B-trees buffer modified pages in memory for performance; the WAL plus an fsync flush guarantees durability.

B-tree variants

• Copy-on-write (LMDB): write modified pages to new locations and rewrite parent pointers, instead of a WAL, also helps with concurrency (snapshot isolation, Ch. 8).
• Key abbreviation in interior pages → higher branching factor, fewer levels.
• Sequential leaf layout and sibling pointers (left/right leaf links) speed up range scans.

---

Comparing B-Trees and LSM-Trees

Rule of thumb: LSM-trees win on write-heavy workloads; B-trees are faster for reads. But benchmarks are workload-sensitive, test with your own. Some engines blend both.

Key supporting ideas:

• Sequential vs random writes: disks (HDD and SSD) have higher sequential write throughput. On SSDs, flash is read/written per page (~4 KiB) but erased per block (~512 KiB); random writes leave blocks with mixed valid/invalid data, forcing garbage collection that costs bandwidth and wears the drive faster. Sequential writes (LSM) reduce both.
• Write amplification = bytes actually written to disk ÷ bytes of the logical write. High amplification limits write throughput on write-bound systems and wears SSDs. Measure over a long enough run that compaction kicks in (an empty LSM-tree has no compaction yet).
• Backpressure: under very high writes, if compaction can't keep up and the memtable fills, engines like RocksDB suspend reads/writes until it's flushed.
• LSM's lingering deleted data (until a tombstone propagates through all levels) can complicate compliance-driven deletion.

---

Multicolumn and Secondary Indexes

• Primary-key index: uniquely identifies a row/document/vertex; other records reference it by ID.
• Secondary index: built with CREATE INDEX to search by non-key columns. Indexed values aren't necessarily unique, so an entry maps to a list of row IDs (like a postings list) or is made unique by appending a row ID. Both B-trees and LSM storage can implement them.

Where the value lives

Fullscreen

• Clustered index, actual row stored in the index (InnoDB primary key; one per table in SQL Server).
• Heap file, index value is a reference to a row stored elsewhere in no particular order (PostgreSQL). Updating a row to a larger value may require moving it and updating indexes (or leaving a forwarding pointer).
• Covering index / index with included columns, stores some columns in the index so a query can be answered without touching the heap (the index "covers" the query). Faster reads, but more space and slower writes.

---

Keeping Everything in Memory

Disk's only advantages over RAM are durability and lower cost/GB, and the cost gap is shrinking. For datasets that fit in RAM, in-memory databases exist:

• Caches like Memcached tolerate data loss on restart.
• Durable in-memory DBs persist via a change log to disk, periodic snapshots, or replication, then reload on restart (disk used only as an append-only log; reads served from memory). Examples: VoltDB, SingleStore, Oracle TimesTen, RAMCloud; Redis/Couchbase offer weak (async) durability.
• Counterintuitive insight: their speed isn't from avoiding disk reads (a disk-based engine with enough RAM rarely hits disk anyway, thanks to OS page cache). It's from avoiding the overhead of encoding in-memory structures into a disk-writable form.
• They also enable data models hard to do on disk, e.g., Redis's priority queues and sets.

---

Data Storage for Analytics

Warehouses use SQL but their internals differ completely from OLTP. Vendors increasingly specialize in one or the other; even HTAP products are usually two engines behind one SQL interface.

Cloud data warehouses and the disaggregated lakehouse

• Cloud-only warehouses (BigQuery, Redshift, Snowflake) exploit object storage + serverless compute, decoupling storage from compute for independent scaling.
• Open-source analytics has broken apart into separable components:

Column-oriented storage

Fact tables can be 100+ columns wide, but a typical query reads only ~4-5. Row-oriented storage (OLTP, documents) keeps all of a row's values together, forcing the engine to load full rows. Column-oriented (columnar) storage keeps each column's values together, so a query reads only the columns it needs.

Fullscreen

• Relies on every column storing rows in the same order (the kth entry in each column = the kth row). Stored in blocks of thousands/millions of rows, often by timestamp range.
• Used almost everywhere in analytics: Snowflake, DuckDB, Pinot, Druid; formats Parquet/ORC/Lance/Nimble; in-memory Arrow, Pandas/NumPy. (Parquet even does columnar storage for document data via shredding/striping.)

Column compression:

• Columns repeat a lot → compress well. Bitmap encoding: for a column with few distinct values, store one bitmap per distinct value (one bit per row, 1 if the row has that value).
• Sparse bitmaps get run-length encoded (count consecutive 0s/1s). Roaring bitmaps pick whichever representation is most compact.
• Bitmaps make warehouse filters fast: WHERE product_sk IN (31,68,69) = bitwise OR of three bitmaps; WHERE a AND b = bitwise AND. (Works because columns share row order.)

Don't confuse column-oriented storage with the wide-column / column-family model (Bigtable, HBase, Accumulo), those are row-oriented despite the name.

Sort order: you can sort the whole table (by row) on chosen columns. Putting a low-cardinality, frequently-filtered column (e.g., date_key) first narrows scans and boosts compression (long runs of repeats → tiny run-length encoding). The effect is strongest on the first sort key.

Writing to columnar storage: writes are bulk imports (ETL). Inserting one row mid-table is expensive (rewrite compressed columns), so use an LSM-like approach: buffer writes in a row-oriented in-memory store, then merge into new column files in bulk. Queries combine on-disk columns + recent in-memory writes transparently.

Query execution: compilation vs vectorization

Scanning millions of rows, CPU time matters as much as disk. A naive row-by-row interpreter is too slow. Two fast approaches:

• Query compilation: generate code for the query and compile it to machine code (often via LLVM, like JVM JIT), then run it over column data in memory.
• Vectorized processing: interpret, but process batches of column values through built-in operators (e.g., an equality operator returns a bitmap). Chain operators (bitwise AND of two bitmaps).

Both exploit modern CPUs: sequential memory access (fewer cache misses), tight inner loops (keep the pipeline busy, avoid branch mispredicts), SIMD parallelism, and operating directly on compressed data.

Materialized views and data cubes

• A materialized view is an actual on-disk copy of a query's results (vs a virtual view, just a query shortcut expanded on the fly). It must be updated when the underlying data changes (more write work, faster reads); tools like Materialize specialize in this.
• A data cube / OLAP cube is a materialized grid of aggregates (SUM, COUNT, etc.) grouped by dimensions. With dates × products, each cell is the aggregate for that combination, and you can roll up along any dimension.
• Trade-off: cubes make precomputed queries very fast but are inflexible (can't answer questions about a dimension you didn't include, like "% of sales over $100" if price isn't a dimension). So warehouses keep raw data and use cubes only as a speed boost.

---

Multidimensional and Full-Text Indexes

B-trees/LSM-trees index one attribute. For multiple conditions at once:

• Concatenated index, combine fields into one key (e.g., (lastname, firstname)), like a phone book. Useful for lastname or lastname+firstname, but useless for firstname alone.
• Multidimensional index, query several columns simultaneously, essential for geospatial data (find all restaurants in a lat/long rectangle). A concatenated index can't do this; instead use space-filling curves + B-tree, or specialized R-trees / Bkd-trees (PostGIS uses R-trees). Also useful beyond maps: (red, green, blue) color search, (date, temperature) weather search.

Full-text search

Treat each possible term as a dimension; a document is 1 in dimensions for terms it contains. Searching "red apples" looks for documents with 1 in both red and apples.

Fullscreen

• The core structure is an inverted index: key = term, value = postings list (IDs of documents containing the term), optionally a sparse bitmap. Finding docs with both terms = bitwise AND of two bitmaps.
• Lucene (Elasticsearch, Solr) stores term → postings in SSTable-like sorted files, merged log-structured-style. PostgreSQL's GIN index also uses postings lists.
• n-grams (e.g., trigrams of "hello" = hel, ell, llo) enable arbitrary substring and even regex search (larger index).
• Typo tolerance: Lucene searches within an edit distance using a finite-state automaton (trie-like) transformed into a Levenshtein automaton.

Vector embeddings (semantic search)

Goes beyond synonyms/typos to meaning, key to retrieval-augmented generation (RAG). "How to close my account" should match a page titled "canceling your subscription."

• An embedding model (often an LLM) turns a document into a vector embedding (array of floats = a point in multidimensional space). Semantically similar inputs land near each other.
• Similarity is measured by cosine similarity (angle) or Euclidean distance (straight-line). Models exist for text (Word2Vec, BERT, GPT), and now multimodal (text + images).
• Querying needs a vector index (R-trees don't work in high dimensions):

Fullscreen

Implemented by Faiss and PostgreSQL's pgvector.

Two meanings of "vector": in vectorized processing it's a batch of values for fast CPU ops; in embeddings it's an array of floats locating a point in semantic space. Different concepts.

---

Real-world examples and analogies

• Log + index, a diary with a sticky-note index. Writing in a diary is fast (append to the end). Finding an entry means reading the whole thing, unless you keep sticky notes saying "March 3 → page 88." That's the in-memory hash index over an append-only log.
• SSTable sparse index, a dictionary's thumb tabs. You don't memorize every word's page; the thumb tabs ("Ha", "He") get you to the right block, then you scan a little. The keys are sorted, so you know where to look.
• LSM compaction, merging tidied piles. You jot notes onto fresh pages (segments) and periodically merge several piles into one tidy, sorted pile, throwing away superseded notes and crossed-out ones (tombstones).
• Bloom filter, a bouncer with a rough guest list. "Definitely not on the list" = skip the venue. "Might be on the list" = go check properly. Fast, and it never wrongly turns away a real guest (no false negatives).
• B-tree, a library's nested catalog. Floor directory → aisle sign → shelf label → the book. A few hops (3-4 levels) reach any of millions of items, and the structure rebalances as books are added.
• Sequential vs random writes, filling a notebook vs sticky notes everywhere. Writing page after page (sequential, LSM) is fast and tidy. Scribbling on scattered sticky notes (random, B-tree) means more flipping around, and on SSDs, more cleanup (garbage collection) and faster wear.
• Row vs column storage, a receipt vs a ledger column. A receipt (row) lists everything about one sale together, great when you want the whole sale. To answer "total quantity sold this year," you'd rather read just the quantity column straight down a ledger, ignoring 95 other columns.
• Bitmap encoding, attendance checkboxes. For "which class is each student in," keep one column of checkboxes per class; a query for "students in class A or B" is just OR-ing two checkbox columns, extremely fast.
• Data cube, a precomputed spreadsheet pivot table. Sales by date × product, with row/column totals already filled in. Instant answers for the dimensions you chose, useless for a question about a dimension you left out.
• Inverted index, a book's index. Look up a word, get the list of pages it appears on. "red AND apple" = intersect the two page lists.
• Vector embedding, a map of meaning. Documents become coordinates; "close my account" and "cancel subscription" land near each other even with no shared words, so you find by nearness, not exact match.

---

Cheat-sheet flashcards

Cover the answer and recall it.

• Two things every database must do? → Store data and give it back.
• Why is the bash-log db_get slow? → O(n) full scan; no index.
• The core index trade-off? → Faster reads, but more disk and slower writes.
• What does the in-memory hash index map? → Key → byte offset in the log.
• Two weaknesses of the hash index? → Must fit in RAM; no efficient range queries.
• What is an SSTable? → A file of key-value pairs sorted by key, each key once.
• What is a sparse index? → Stores only some keys (first key of each block).
• What is a memtable? → In-memory sorted structure buffering writes before flush.
• What is compaction? → Background merge of segments, dropping overwritten/deleted values.
• What is a tombstone? → A deletion marker that suppresses older values during compaction.
• What does LSM stand for? → Log-Structured Merge-tree.
• What does a Bloom filter tell you? → "Definitely absent" or "probably present" (false positives, no false negatives).
• Size-tiered vs leveled compaction? → Write-heavy vs read-heavy workloads.
• What is an embedded storage engine? → A library in your process (RocksDB, SQLite, DuckDB, LMDB).
• B-tree unit of storage? → Fixed-size page (4-16 KiB), overwritten in place.
• What is the branching factor? → Child references per B-tree page (often hundreds).
• B-tree depth for n keys? → O(log n) (kept balanced via splits).
• What is a WAL and why? → Write-ahead log; recover the tree/memtable after a crash.
• What is a torn page? → A partially written page after a crash.
• LSM vs B-tree rule of thumb? → LSM for writes, B-tree for reads.
• Sequential vs random writes, who does which? → LSM sequential, B-tree random.
• Why are random writes bad on SSDs? → Erase-per-block forces garbage collection → wear + lost bandwidth.
• What is write amplification? → Disk bytes written ÷ logical bytes written.
• Clustered index vs heap file? → Row stored in the index vs index points to a separate row store.
• What is a covering index? → Index stores extra columns so it can answer a query alone.
• Why are in-memory DBs fast (the real reason)? → Avoid encoding data into a disk format, not avoiding disk reads.
• Row vs column storage, which for OLAP? → Column-oriented.
• Why does columnar compress well? → Repeated values per column (bitmap + run-length encoding).
• Why sort by a low-cardinality column first? → Long runs → strong compression + narrower scans.
• Query compilation vs vectorization? → Generate machine code vs batch-process columns through built-in operators.
• Virtual view vs materialized view? → Query shortcut expanded on read vs stored copy of results.
• What is a data cube? → Precomputed grid of aggregates by dimension.
• Concatenated index weakness? → Can't query the second field alone.
• Index for geospatial range queries? → R-tree / Bkd-tree (or space-filling curve + B-tree).
• Core full-text structure? → Inverted index (term → postings list).
• What enables typo-tolerant search in Lucene? → Levenshtein automaton (edit distance).
• What is a vector embedding? → A float vector locating a document in semantic space.
• Two vector distance measures? → Cosine similarity, Euclidean distance.
• Three vector indexes? → Flat (exact), IVF (partitions/probes), HNSW (layered graphs).

---

Common interview questions

1. Compare LSM-trees and B-trees. When would you choose each? (Append-only immutable segments + compaction vs in-place page overwrites; LSM for write-heavy/sequential writes/lower amplification, B-tree for read-heavy/predictable reads/range queries.)
2. Walk through the write and read path of an LSM storage engine. (WAL + memtable; flush to SSTable; reads check memtable then segments newest-to-oldest; compaction; tombstones.)
3. What problem do Bloom filters solve, and what's a false positive? (Avoid scanning segments for absent keys; "all bits 1" can occur by coincidence, never a false negative.)
4. Why do disks (and SSDs) prefer sequential writes? How does this favor LSM-trees? (HDD seek time; SSD erase-per-block + garbage collection + wear; LSM writes whole segments sequentially.)
5. What is write amplification and why does it matter? (Disk bytes ÷ logical bytes; limits write throughput and wears SSDs; measure after compaction starts.)
6. Explain clustered index, heap file, and covering index. (Row in index; index → separate row store; index carries extra columns to answer queries alone.)
7. Why are in-memory databases fast, and what's the common misconception? (Not avoiding disk reads, OS caches anyway, but avoiding disk-encoding overhead.)
8. Why is column-oriented storage better for analytics? (Read only needed columns; strong compression; vectorization; queries touch few of many columns.)
9. How does columnar storage achieve compression, and how does sort order help? (Bitmap + run-length + roaring; sort low-cardinality column first for long runs and narrow scans.)
10. Query compilation vs vectorized execution, what's the difference? (Generate/compile machine code vs batch-process columns through prebuilt operators; both exploit cache locality, tight loops, SIMD, compressed data.)
11. What is a materialized view / data cube, and what's the trade-off? (Stored precomputed results/aggregates; fast reads, more write work, inflexible for unanticipated dimensions.)
12. How does full-text search work, and how does vector/semantic search differ? (Inverted index + postings lists + bitwise ops; embeddings + nearest-neighbor in vector space via Flat/IVF/HNSW.)

---

Key terms glossary

---

Forward links (where these ideas return)

• Durability, crash recovery, atomicity → Chapter 8
• Copy-on-write and snapshot isolation → Chapter 8
• Replication and sharding across machines → Chapters 6 and 7
• Maintaining materialized views (stream processing) → Chapter 12
• Separation of storage and compute (cloud native) → Chapter 1
• Stars/snowflakes and analytics schemas → Chapter 3