# Choosing a datastore

> Match storage to access patterns: when a relational database is enough, what key-value, document, wide-column, search, analytical and object stores are for, and how B-trees and LSM-trees shape performance.

System Design roadmap · Data at scale · 20 min read · https://levelcode.org/roadmaps/system-design/choosing-a-datastore

There are hundreds of databases, and their marketing pages all say "fast" and "scalable". Choosing well means ignoring that and asking two questions: **how will this data be written and read**, and **what will it cost to run**. This lesson explains the storage-engine designs underneath most databases, then walks through the main families, what each is genuinely good at, and how to combine them without losing track of the truth.

## Start from a relational database

For a new system, start with PostgreSQL (or MySQL) unless a requirement rules it out. That's not conservatism; it's arithmetic about what it gives you:

- **Flexible queries.** You don't need to know every access pattern in advance: joins, aggregates, and new indexes added later.
- **Transactions and constraints.** Uniqueness, foreign keys and multi-row atomic changes, enforced by the database rather than by every piece of code that writes.
- **Mature operations.** Backups, point-in-time recovery, replication, monitoring and managed offerings everywhere.
- **Range.** JSON columns cover semi-structured data; extensions add full-text search, geospatial indexes (PostGIS), time-series (TimescaleDB) and vectors (pgvector).

A well-indexed PostgreSQL instance on a large machine serves thousands of writes and tens of thousands of reads per second over terabytes of data. The reasons to look elsewhere are specific: write volume or data size beyond one machine, an access pattern relational engines handle poorly (full-text relevance ranking, scans over billions of rows for analytics), or a latency target only memory can meet.

## Under the hood: B-trees and LSM-trees

Most databases store data with one of two engine designs, and knowing which one a database uses predicts much of its behaviour. See [B-trees vs LSM-trees](https://levelcode.org/concepts/b-tree-vs-lsm-tree).

**B-trees** (PostgreSQL, MySQL InnoDB, SQL Server) keep data in fixed-size pages arranged as a balanced tree, and **update pages in place**. A lookup walks three or four levels from root to leaf. Reads are predictable; writes are random I/O to wherever the page lives, plus a write to the [write-ahead log](https://levelcode.org/concepts/write-ahead-log) for crash safety.

**LSM-trees** (Cassandra, RocksDB, ScyllaDB, LevelDB, and the storage under many newer databases) never update in place:

1. Writes go to the log and an in-memory sorted table (the *memtable*). That's all a write costs, so writes are fast and sequential.
2. When the memtable fills, it's flushed to disk as an immutable sorted file (an *SSTable*).
3. Background **compaction** merges SSTables, discarding overwritten and deleted values.

The price is paid on reads: a key might be in the memtable or any of several SSTables, newest first. To avoid opening files that can't contain the key, each SSTable keeps a [Bloom filter](https://levelcode.org/concepts/bloom-filters), a compact bit array that answers "definitely not here" or "possibly here".

> **Interactive: The Bloom filter on an SSTable.** Each SSTable has one. A key whose bits aren't all set is definitely absent, so the read skips that file. Fill the filter and probe absent names: false positives cost one wasted file read, but a false negative — skipping a file that has the key — can never happen. Try it: https://levelcode.org/labs/bloom-filter

| | B-tree | LSM-tree |
|---|---|---|
| Writes | Random page updates | Sequential appends; very high throughput |
| Reads | One tree walk | Memtable + several SSTables (Bloom filters help) |
| Space | Pages partly empty after splits | Compacted files are dense; old versions linger until compaction |
| Background work | Vacuum (PostgreSQL) | Compaction, which competes with foreground I/O |
| Good fit | General OLTP, read-heavy | Write-heavy: events, logs, time series, messaging |

## The main families

See [relational vs NoSQL](https://levelcode.org/concepts/sql-vs-nosql) for a one-page comparison.

**Key-value stores** — Redis, Memcached, DynamoDB, etcd. Get and put by key, nothing else (DynamoDB adds sort keys and simple queries). In-memory ones answer in under a millisecond; DynamoDB scales to almost any throughput with consistent single-digit-millisecond latency, if you design keys around your queries up front. Use them for caches, sessions, rate-limit counters, feature flags, and high-volume lookups by ID.

**Document databases** — MongoDB, Couchbase, Firestore. Store JSON-like documents, query by fields inside them, and keep related data nested in one document. They shine when an entity is naturally a tree read as a whole (a product with its variants and attributes) and its shape varies. They are weaker for many-to-many relationships, which need either references (and application-side joins) or duplication. PostgreSQL's `jsonb` covers many "we need flexible documents" cases.

**Wide-column stores** — Cassandra, ScyllaDB, Bigtable, HBase. Rows grouped into partitions by a partition key and sorted within the partition by a clustering key. Built for very high write rates, linear horizontal scaling and multi-region replication. The catch: you design one table per query, because there are no joins and querying by anything other than the key is expensive. Use them for messaging, activity feeds, time series and IoT data at large scale.

**Search engines** — Elasticsearch, OpenSearch, Typesense, Meilisearch. Build an [inverted index](https://levelcode.org/concepts/inverted-index) — each term mapped to the documents containing it — for full-text queries ranked by relevance, typo tolerance, facets and aggregations. They are not a system of record: updates are near-real-time rather than immediate, and you should be able to rebuild the index from your primary database.

**Analytical (columnar) stores** — ClickHouse, BigQuery, Snowflake, DuckDB. Store each column separately and compress it heavily, so "average order value by country for last year" scans only two columns across billions of rows in seconds. They are terrible at what OLTP databases do well: single-row updates and many small concurrent transactions. Feed them from your operational database rather than writing to them from the application.

**Object storage** — S3, Google Cloud Storage, Azure Blob. Files of any size by key, eleven nines of durability, very cheap per gigabyte, and no queries. Images, video, backups, exports and large blobs belong here, with metadata in a database. See [object storage](https://levelcode.org/concepts/object-storage).

**Graph databases** — Neo4j, Neptune. Model data as nodes and edges and query multi-hop relationships ("friends of friends who like X"). Genuinely useful for deep traversals over highly connected data; for one or two hops, a relational database with good indexes is usually enough.

## A decision table

| Requirement | First choice |
|---|---|
| General application data, transactions, ad-hoc queries | PostgreSQL / MySQL |
| Sub-millisecond lookups, caches, counters, sessions | Redis |
| Huge, predictable key-based throughput, serverless operations | DynamoDB |
| Very high write rates, multi-region, query-shaped tables | Cassandra / ScyllaDB |
| Full-text search with relevance and facets | Elasticsearch / OpenSearch (fed from the primary) |
| Analytics over billions of rows | ClickHouse / BigQuery / Snowflake (fed from the primary) |
| Files and large blobs | S3-compatible object storage |
| Coordination: leader election, config, locks | etcd / ZooKeeper (small data only) |

## Combining stores without losing the truth

Real systems use several stores: PostgreSQL for orders, Redis for sessions, Elasticsearch for product search, S3 for images, a warehouse for analytics. The discipline that keeps this sane:

- **One system of record per piece of data.** Orders live in PostgreSQL. The search index and the warehouse hold *derived* copies that can be rebuilt from it.
- **Propagate changes reliably.** Writing to the database and then to Elasticsearch from application code (a *dual write*) loses updates when the second write fails. Use the [transactional outbox](https://levelcode.org/concepts/transactional-outbox) or change data capture (Debezium reading the database's log) so every committed change reaches the derived stores eventually.
- **Expect derived stores to lag.** Design the UI for it: after saving, show the saved record from the primary rather than from search results.
- **Count the operational cost.** Each new datastore means backups, upgrades, monitoring, security patches and on-call knowledge. A second store must earn its keep.

> [!TIP]
> Ask "what happens if this store loses all its data?" For a derived store the answer should be "we rebuild it from the system of record". If the answer is "we lose customer data", it's a system of record, and needs backups, replication and restore drills like one.

## Practice

A second-hand marketplace needs storage for: (1) users, listings, orders and payments; (2) listing photos; (3) search over listing titles and descriptions with filters by price, category and location; (4) a "recently viewed" list per user, the last 50 listings, read on every page; (5) monthly reports on sales by category and region over three years of orders.

Choose a store for each, say which are systems of record, and explain how data gets into the derived stores.

**Solution**

1. **Users, listings, orders, payments → PostgreSQL**, the system of record. These need transactions (an order and its payment record), constraints (unique emails, foreign keys) and flexible queries. One primary with replicas comfortably handles a marketplace of this kind for a long time.
2. **Photos → object storage** (S3-compatible), uploaded directly by clients through presigned URLs and served through a CDN. PostgreSQL stores the object keys. The object store is the system of record for the image bytes.
3. **Search → Elasticsearch/OpenSearch**, a derived store. Full-text relevance plus filters and geo-distance is exactly what it does well. Changes reach it through an outbox table written in the same transaction as the listing change (or CDC on the listings table), consumed by an indexer. It can be rebuilt from PostgreSQL at any time. (For a small catalogue, PostgreSQL full-text search plus PostGIS would also be a reasonable start.)
4. **Recently viewed → Redis**, a list per user: `LPUSH`, then `LTRIM 0 49`, with a TTL of a few weeks. It's read on every page, so sub-millisecond reads matter, and losing it is an inconvenience, not data loss — so it isn't a system of record and doesn't need backups.
5. **Monthly reports → a columnar warehouse** (BigQuery, Snowflake or ClickHouse), loaded nightly or continuously from PostgreSQL via CDC. Scanning three years of orders by category and region would slow the production database; the warehouse does it in seconds. Derived, rebuildable from the source.

## Key takeaways

- Start with a relational database; move away only for a specific requirement it can't meet.
- B-trees update in place and suit read-heavy OLTP; LSM-trees append and compact, suiting write-heavy workloads, with Bloom filters to keep reads cheap.
- Key-value for lookups and caches, document for self-contained variable-shape entities, wide-column for massive write-heavy query-shaped data, search engines for relevance, columnar stores for analytics, object storage for files.
- Keep one system of record per piece of data; feed derived stores through an outbox or change data capture, never dual writes.
- Every additional datastore has an operational cost that must be justified.

## Quiz

1. Why do LSM-tree databases keep a Bloom filter per SSTable?

   A. To compress the data in the file
   B. To skip SSTables that definitely don't contain the key, avoiding wasted disk reads
   C. To guarantee every key appears in exactly one SSTable
   D. To sort keys within the file

   **Answer: B.** A key may live in any of several SSTables. The filter rules out most of them without touching disk; a false positive costs one unnecessary read, and false negatives never happen.

2. An app writes each product to PostgreSQL and then to Elasticsearch from the same request handler. What is the risk?

   A. None, as long as both writes are in the same function
   B. Elasticsearch will reject duplicate products
   C. If the second write fails or the process crashes between them, the search index silently misses the update
   D. PostgreSQL will lock the row until Elasticsearch confirms

   **Answer: C.** Dual writes aren't atomic. An outbox written in the same transaction, or change data capture from the database log, guarantees every committed change eventually reaches the index.

3. Which workload fits a columnar analytical store best?

   A. Updating one user's shipping address
   B. Average basket value per country per month across two billion orders
   C. Storing session tokens with a 30-minute expiry
   D. Serving profile photos

   **Answer: B.** Columnar stores scan a few columns across huge row counts very quickly. They're poor at single-row updates, and sessions and photos belong in Redis and object storage.

4. Your team wants MongoDB 'because the schema might change'. What should you check first?

   A. Whether PostgreSQL with jsonb columns and normal migrations would cover the flexibility needed while keeping transactions and joins
   B. Whether MongoDB is faster on a benchmark
   C. Whether the data fits in memory
   D. Whether the team prefers JavaScript

   **Answer: A.** Schema changes are routine in relational databases, and jsonb handles genuinely variable fields. A document store is worth it when entities are naturally self-contained documents, not as a hedge against migrations.