Engineering Atlas › System Design Fundamentals

A tour of database families

15 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

Model, queries, layout

Every database answers two questions: what shape can I store, and which questions can I answer without reading everything? Database Selection gives a framework for choosing; this lesson explains why each family is fast at its sweet spot, which comes from how it lays out bytes.

The problem shape is "finding things fast", and it recurs outside databases: a code search tool builds an inverted index, a log pipeline appends segments and compacts them later.

Row stores on B-trees

Postgres and MySQL keep rows in fixed-size pages (8 KB in Postgres, 16 KB in InnoDB) indexed by B+ trees (Postgres docs). A lookup walks three or four levels, the upper ones cached, so a point read costs about one disk read, and updates modify pages in place. InnoDB stores rows inside the primary-key tree (a clustered index); Postgres keeps an unordered heap pointed to by separate indexes. See B-Trees.

Key-value stores

A key-value store gives up queries on anything but the key for predictable latency at any scale. In memory (Redis, Memcached, and Valkey, the BSD-licensed fork the Linux Foundation started from Redis 7.2.4 in 2024 after Redis changed its license (Linux Foundation)) the layout is a hash table. Distributed on disk, the key picks a partition whose replicas hold a B-tree or LSM tree; in DynamoDB each storage replica keeps a write-ahead log plus a B-tree (DynamoDB paper, ATC 2022). Every access must name a key; anything else is a scan.

Document stores

Document databases (MongoDB, Couchbase, Firestore) store a nested record, such as an order with its line items, as one unit, so reading the aggregate needs no joins. MongoDB's WiredTiger engine keeps documents in B-trees with secondary indexes, so the layout is close to a row store; the difference is the model. You choose between embedding (fast reads, duplicated writes) and referencing (joins in your code), and the 16 MiB document cap rules out unbounded embedded lists (MongoDB limits).

LSM-based stores: wide-column and time-series

Cassandra, ScyllaDB, HBase and Bigtable buffer writes in memory and a log, flush sorted immutable files, and merge them in the background. Writes become sequential; reads may check several files, bounded by bloom filters and compaction. Queries must follow the partition and clustering key. See LSM Trees and Wide Column Databases. Time-series databases add time-partitioned chunks and heavy compression of timestamps and values (Time-Series Databases).

Column stores for analytics

ClickHouse, BigQuery, Snowflake and Redshift store each column separately, sorted by a chosen key and compressed with dictionary, run-length or delta encoding. A query that sums one column over a billion rows reads only that column, often at a tenth of its raw size. Single-row updates are expensive because a row spans many files.

Search, graph and vector stores

Search engines (Elasticsearch, OpenSearch, on Lucene) keep an inverted index: for each term, a sorted list of documents containing it, in immutable segments merged in the background. Graph databases such as Neo4j store each node with direct pointers to its relationships, so an edge is a pointer hop (Graph Databases). Vector databases keep approximate nearest-neighbour indexes such as HNSW graphs (Vector Databases). Vector search is also becoming a feature of general stores rather than only a separate family: DynamoDB now offers vector indexes of up to 4,096 dimensions (AWS quotas), and Postgres has the pgvector extension.

Distributed SQL

Spanner, CockroachDB, YugabyteDB and TiDB split the key space into ranges, each replicated by consensus and usually stored in an LSM engine: Pebble in CockroachDB (CockroachDB docs), RocksDB under TiKV. You get cross-machine transactions at the price of consensus round trips per write.

Down the stack

Layer 1The contract

Each family promises a set of efficient queries and, implicitly, that everything outside the set costs a scan. A B-tree store promises point and range lookups on indexed columns in logarithmic I/O and in-place transactional updates. An LSM store promises high sustained write throughput and point reads that touch roughly one data block per lookup when bloom filters work, at the price of background compaction. A column store promises scans proportional to the columns touched, not the rows. An inverted index promises keyword lookups proportional to the matching postings.

Layer 2The mechanism

The RUM conjecture from Harvard's DASlab states the constraint (DASlab): an access method can minimise at most two of read overhead, update overhead and memory (space) overhead. B-trees pick reads and space; they pay on updates by rewriting a whole page to change one row. A 100-byte update in a 16 KB InnoDB page eventually writes 16 KB, a write amplification above 100 before counting the redo log or the doublewrite buffer, which writes every flushed page twice so a torn write can be repaired (MySQL docs). Postgres solves the same torn-page problem by adding a full-page image to its WAL the first time a page changes after each checkpoint (Postgres docs).

LSM engines pick updates and space. RocksDB's leveled compaction uses a level size multiplier of 10 and a 256 MB base level by default, so each level holds ten times the previous one. Since version 8.4 RocksDB sizes levels from the bottom up by default (level_compaction_dynamic_level_bytes): the last level's target is its actual size, levels too small to matter stay empty, and about 90% of the data sits in the last level (RocksDB wiki). A byte written is rewritten roughly ten times per level it moves down, giving write amplification in the tens, but those writes are large sequential merges. Reads check the memtable, then at most one file per level, using a bloom filter (about 10 bits per key for a 1% false positive rate) to skip files that cannot contain the key (RocksDB wiki).

Column stores pick reads for scans. ClickHouse's MergeTree stores data in parts sorted by the primary key, with a sparse index that has one entry per granule of 8,192 rows by default (ClickHouse docs), so the index for a billion rows fits in memory and a range query reads only the granules it needs.

Layer 3The machine

An NVMe SSD serves a random 4 KB read in about 80 to 100 microseconds and sequential reads at several GB/s. Inside, flash is programmed in pages of a few KB and erased in blocks of megabytes, so random small writes cause the drive's own garbage collection and wear. So write amplification is a real cost: it multiplies against the drive's rated writes per day.

Scanning one column of 8-byte integers streams contiguous 64-byte cache lines and lets SIMD process several values per instruction; the same scan in a row store drags every other column through the cache. An in-memory hash table skips the disk but pays for RAM, roughly an order of magnitude more per GB than SSD.

Why it's built this way

  1. Disks and SSDs read and write in blocks, not bytes, so every engine organises data into pages, files or segments.
  2. Random writes to blocks are slow and wear flash, so write-heavy engines buffer in memory and append sorted files, then compact them.
  3. Compaction and multi-file reads cost I/O, so LSM engines add bloom filters and level size ratios to bound read and write amplification.
  4. Analytical queries touch few columns of many rows, so analytic engines store and compress by column, giving up cheap single-row updates.
  5. No layout wins on reads, writes and space at once, so serious systems combine several stores and move data between them.

Diagram

flowchart TD
  Q["Dominant access pattern"] --> P["Point reads and transactions"]
  Q --> W["Heavy ingest, key-addressed"]
  Q --> A["Scans over few columns"]
  Q --> T["Keyword or similarity"]
  Q --> G["Multi-hop relationships"]
  P --> BT["B+ tree pages: relational, document"]
  W --> LSM["LSM tree: wide-column, time-series, KV"]
  A --> COL["Column files: analytics warehouse"]
  T --> INV["Inverted or ANN index: search, vector"]
  G --> ADJ["Adjacency records: graph"]

Worked example

Two teams share a cost model. Both have 1 billion records of 100 bytes (100 GB), 4 KB pages, B-tree fanout 200 and 200,000 pages of cache. The LSM option uses a 256 MB base level, ratio 10 and 1% bloom filters.

B-tree. 40 records fit per leaf, so there are 25 million leaves, then 125,000, 625, 4 and 1 nodes above: height 5. The top four levels total 125,630 pages and fit in cache, so a point read costs one disk read. Each update rewrites a 4 KB page.

LSM. Levels hold up to 256 MB, 2.56 GB, 25.6 GB and 256 GB, so 100 GB needs 4 levels. Write amplification is 2 (log plus flush) plus 10 for each of the 3 lower levels: 32. Each byte written becomes 32 bytes of device writes, or 3,200 bytes per 100-byte record, versus 4,096 for the B-tree. A point read costs 1 plus 3 × 0.01 = 1.03 reads.

IoT ingest team: 50,000 writes and 5,000 reads per second. B-tree device traffic: 50,000 × 4,096 + 5,000 × 4,096 = 225 MB/s. LSM: 50,000 × 3,200 + 5,000 × 1.03 × 4,096 = 181 MB/s. The LSM wins, and its writes are sequential, which matters more on flash than the totals suggest.

Catalogue team: 5,000 writes and 100,000 reads per second. B-tree: 20 MB/s + 410 MB/s = 430 MB/s. LSM: 16 MB/s + 422 MB/s = 438 MB/s. The B-tree wins narrowly; add range scans and the gap widens, because an LSM range scan merges several files.

The model ignores page coalescing and block caches, but it shows that "LSM for writes, B-tree for reads" is a crossover on a curve, not a rule.

In the wild

Trade-offs

Layout (families)StrengthsWeaknessesChoose when
B+ tree row store (relational, document)Fast point and range reads, in-place transactions, mature toolingWrite amplification on random updates, single-writer scalingSystem of record, OLTP, mixed queries
In-memory hash (Redis, Memcached)Sub-millisecond, simpleRAM cost, key-only access, durability limitsCaches, sessions, counters, leaderboards
LSM tree (wide-column, time-series, many KV)Sustained high write rates, sequential I/O, good compressionCompaction debt, read and space amplification, tombstonesIngest-heavy, key-addressed data
Column store (warehouse, OLAP)Scans of few columns over billions of rows, high compressionSlow point lookups and updatesAnalytics, dashboards, reporting
Inverted index (search)Keyword, fuzzy and faceted queriesNot transactional, reindexing costSearch over text, filtering by many fields
Adjacency records (graph)Deep traversals as pointer hopsHard to partition, weak at aggregatesFraud rings, recommendations, dependency graphs

Pitfalls in production

Leadership lens

Check yourself

  1. Why does a 100-byte update cost far more device writes in a B-tree than its size suggests?

    Show answer

    The engine writes whole pages, so changing 100 bytes eventually rewrites a 4 to 16 KB page, plus log records. Unless many updates hit the same page before it is flushed, write amplification is page size divided by record size.

  2. A team stores clickstream events in a row store and their daily report scans 3 of 60 columns over 2 billion rows. Why would a column store be much faster?

    Show answer

    The column store reads only the 3 columns, about 5% of the bytes before compression, and those columns compress well because similar values sit together. The row store reads every column of every row.

  3. Why do LSM engines need bloom filters, and what happens to reads without them?

    Show answer

    A key may be in any level, so a lookup would check every level's file for it. Bloom filters let the engine skip files that definitely lack the key, keeping a point read close to one disk read.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →