Data Models & Storage Engines

"Should we use SQL or NoSQL?" is the most common storage question in design reviews and interviews, and also the most badly posed. "NoSQL" is not one thing: a key-value store, a document database, a wide-column store and a graph database are as different from each other as each is from PostgreSQL. And underneath the data model sits a second choice that matters just as much for performance — the storage engine that lays the bytes on disk.

This page takes one piece of BoxOffice — events, venues, seats and orders — and stores it in each model, then opens the engine room: B-trees, LSM-trees and indexes.

The relational model

The relational model stores data as tables (relations) of rows with a fixed set of typed columns. Relationships are expressed by foreign keys, and queries combine tables with joins. The schema is declared up front and enforced on every write (schema-on-write)¹.

CREATE TABLE venues (
    id        BIGSERIAL PRIMARY KEY,
    name      TEXT NOT NULL,
    city      TEXT NOT NULL,
    capacity  INT  NOT NULL CHECK (capacity > 0)
);

CREATE TABLE events (
    id        BIGSERIAL PRIMARY KEY,
    venue_id  BIGINT NOT NULL REFERENCES venues(id),
    title     TEXT NOT NULL,
    starts_at TIMESTAMPTZ NOT NULL,
    on_sale_at TIMESTAMPTZ NOT NULL
);

CREATE TABLE seats (
    event_id  BIGINT NOT NULL REFERENCES events(id),
    seat_id   TEXT   NOT NULL,              -- 'A-12'
    section   TEXT   NOT NULL,
    price_cents INT  NOT NULL,
    status    TEXT   NOT NULL DEFAULT 'AVAILABLE'
              CHECK (status IN ('AVAILABLE', 'HELD', 'SOLD')),
    held_by   BIGINT,
    hold_expires_at TIMESTAMPTZ,
    version   INT    NOT NULL DEFAULT 0,
    PRIMARY KEY (event_id, seat_id)
);

CREATE TABLE orders (
    id          BIGSERIAL PRIMARY KEY,
    customer_id BIGINT NOT NULL,
    event_id    BIGINT NOT NULL REFERENCES events(id),
    total_cents INT    NOT NULL,
    status      TEXT   NOT NULL,
    created_at  TIMESTAMPTZ NOT NULL DEFAULT now()
);

CREATE TABLE tickets (
    order_id  BIGINT NOT NULL REFERENCES orders(id),
    event_id  BIGINT NOT NULL,
    seat_id   TEXT   NOT NULL,
    PRIMARY KEY (event_id, seat_id),        -- one ticket per seat, enforced by the database
    FOREIGN KEY (event_id, seat_id) REFERENCES seats(event_id, seat_id)
);

Three properties make the relational model the default for a system of record:

• Normalization — each fact is stored once (the venue's city lives in venues, not copied into every event), so an update cannot leave two copies disagreeing.
• Constraints — PRIMARY KEY (event_id, seat_id) on tickets makes double-selling a seat impossible, no matter how buggy the application code is.
• Declarative queries — you say what you want; the query planner decides how, using whatever indexes exist. New questions do not need new tables.

-- Revenue per city for shows in December, best first
SELECT v.city, SUM(o.total_cents) / 100.0 AS revenue
FROM orders o
JOIN events e ON e.id = o.event_id
JOIN venues v ON v.id = e.venue_id
WHERE o.status = 'PAID'
  AND e.starts_at >= '2026-12-01' AND e.starts_at < '2027-01-01'
GROUP BY v.city
ORDER BY revenue DESC;

The costs: rows that belong together (an event and its lineup and prices) are spread across tables and reassembled by joins; the schema must be migrated (with Flyway in Hands-on 1) before new fields appear; and scaling writes beyond one node needs partitioning, which breaks cross-partition joins and transactions (see Partitioning).

Document databases

A document database stores self-contained, nested documents — usually JSON or a binary form of it — addressed by a key. Everything you need to render an event page can live in one document:

{
  "_id": 42,
  "title": "Stadium Tour 2027",
  "venue": { "id": 7, "name": "Allianz Parque", "city": "São Paulo" },
  "startsAt": "2027-03-14T21:00:00-03:00",
  "lineup": ["Main act", "Opening act"],
  "priceTiers": [
    { "section": "Pista", "priceCents": 49000 },
    { "section": "Cadeira Superior", "priceCents": 29000 }
  ],
  "tags": ["pop", "stadium"]
}

• Locality: one read returns the whole page; no joins. Great for "load the aggregate by id".
• Flexible schema (schema-on-read): a festival can carry a stages array that a football game does not have.
• Weakness — many-to-many relationships: the venue is copied into every event. Renaming the venue means updating thousands of documents, or accepting stale copies. Queries that cut across documents ("all events at venue 7") need secondary indexes or a different collection.

Products: MongoDB, Couchbase, Google Firestore, Azure Cosmos DB, Amazon DocumentDB — and PostgreSQL itself with JSONB columns and GIN indexes, which is often enough.

Key-value stores

The simplest model: an opaque value looked up by a key — GET, PUT, DELETE, sometimes with a TTL. No queries by value, no joins, so the store can be extremely fast and easy to partition by key.

DynamoDB deserves a note because it is a common interview answer. It is a managed, partitioned key-value and document store: each item has a partition key (hashed to choose the partition) and an optional sort key (items with the same partition key are stored sorted, so range queries within a partition are cheap). You design the table around the queries — the opposite of normalization.

The design starts from the list of queries; a new query that does not fit the keys needs a global secondary index — or a new table.

Wide-column stores

Wide-column stores (Apache Cassandra, ScyllaDB, Google Bigtable, Apache HBase) organize rows into partitions by a partition key, and sort rows inside a partition by clustering columns. They are built for very high write throughput across many nodes, with tunable consistency (see Replication).

-- Query: "the last 50 scans at gate 3 of event 42" (anti-fraud at the stadium)
CREATE TABLE gate_scans_by_event (
    event_id   bigint,
    gate       int,
    scanned_at timestamp,
    ticket_id  uuid,
    result     text,
    PRIMARY KEY ((event_id, gate), scanned_at, ticket_id)
) WITH CLUSTERING ORDER BY (scanned_at DESC, ticket_id ASC);

SELECT * FROM gate_scans_by_event
WHERE event_id = 42 AND gate = 3
LIMIT 50;

The syntax looks like SQL, but the rules are different: you can only filter by the partition key (and then by clustering columns in order); there are no joins; each query gets its own denormalized table. In exchange, writes are appends to an LSM-tree (see below) and spread over every node — ideal for time series, event logs, IoT and messaging at large scale.

Graph databases

When the questions are about relationships — paths, neighbours, communities — a graph database stores nodes and edges as first-class citizens. Neo4j (query language Cypher), Amazon Neptune and the ISO standard query language GQL (2024) are examples.

MATCH (e:Event {id: 42})<-[:BOUGHT]-(f:Fan)-[:BOUGHT]->(other:Event)
WHERE other.startsAt > datetime()
RETURN other.title, count(f) AS fans
ORDER BY fans DESC
LIMIT 5;

In SQL the same query is a self-join of orders with itself; it works for one hop but grows painful for "friends of friends of friends" or fraud rings (cards, devices and accounts linked across many hops). Most systems never need a graph database; recommendation and fraud teams sometimes do.

Comparing the models

SQL or NoSQL? A decision guide

The guide below encodes the questions from the overview. Read it as "the default is relational; each arrow out of it needs a reason".

flowchart TD
    A["New data to store"] --> B{"Invariants across rows?<br/>money, stock, uniqueness"}
    B -->|yes| SQL["Relational database<br/>PostgreSQL / MySQL"]
    B -->|no| C{"Queries known in advance<br/>and mostly by key?"}
    C -->|no, ad hoc| SQL
    C -->|yes| D{"Scale beyond one node<br/>for writes or storage?"}
    D -->|no| SQL
    D -->|yes| E{"Shape of the data?"}
    E -->|"blob: images, PDFs"| OBJ["Object storage"]
    E -->|"key → value, TTL"| KV["Key-value<br/>Redis, DynamoDB"]
    E -->|"aggregate as JSON"| DOC["Document<br/>MongoDB, Firestore"]
    E -->|"time-ordered, huge writes"| WC["Wide-column<br/>Cassandra, Bigtable"]
    E -->|"multi-hop relationships"| GR["Graph<br/>Neo4j"]
    SQL --> F{"Outgrows one primary?"}
    F -->|"yes, need SQL + scale"| NEW["Distributed SQL<br/>Spanner, CockroachDB"]

And for the derived data, the question is the query, not the scale: full-text → search engine, aggregations over history → data warehouse, similarity by meaning → vector database.

Some myths to retire before an interview:

Storage engines: how bytes reach the disk

A database is, at its core, two operations: store this key and value and give me the value for this key (or this range of keys). How it lays the data on disk determines the cost of each. Two families dominate: B-trees (update pages in place) and LSM-trees (append, then merge)².

B-trees

A B-tree keeps keys sorted in fixed-size pages (8 KiB in PostgreSQL, 16 KiB in MySQL InnoDB). Each internal page holds hundreds of keys and pointers to child pages; leaves hold the rows or pointers to them. Lookups walk from the root to a leaf³.

flowchart TD
    R["root page<br/>… | 30 | 60 | …"] -->|"key 42"| I["internal page<br/>31 … 40 | 41 … 50 | …"]
    I -->|"key 42"| L["leaf page<br/>41, 42, 43 … → rows"]
    L -->|"update in place:<br/>rewrite the 8 KiB page"| D[("disk")]
    W["write-ahead log (WAL)<br/>append the change first"] --> D

The numbers explain why B-trees are everywhere. With 8 KiB pages and ~16 bytes per key + pointer, one page has a fan-out of ~500:

A billion-row table is 4 levels deep, and the top levels stay cached in memory, so a point lookup costs one or two disk reads. Writes, though, modify a page in place: changing a 100-byte row dirties a whole 8 KiB page that is later written back, and the change is also appended to the write-ahead log (WAL) for crash recovery. Used by PostgreSQL, MySQL InnoDB, SQL Server, Oracle, SQLite.

LSM-trees

A log-structured merge-tree (LSM-tree) never updates in place⁴. Writes go to the WAL and to an in-memory sorted table (the memtable); when it fills, it is flushed to disk as an immutable sorted file (an SSTable). Background compaction merges SSTables into larger, sorted levels and drops overwritten and deleted values.

flowchart LR
    W["write key=42"] --> WAL["WAL<br/>append"]
    W --> M["memtable<br/>in memory, sorted"]
    M -->|"full → flush"| L0["L0 SSTables"]
    L0 -->|"compaction"| L1["L1 (10× bigger)"]
    L1 -->|"compaction"| L2["L2 (10× bigger)"]
    R["read key=42"] --> M
    R -->|"bloom filter says<br/>'maybe here'"| L1

Writes are sequential appends — very fast, even on slow disks. Reads may have to check the memtable and several levels; Bloom filters (a compact probabilistic set per SSTable that answers "definitely not here" or "maybe here") skip most of them. Used by RocksDB (inside many systems), Cassandra, ScyllaDB, HBase, Bigtable, LevelDB, and CockroachDB's Pebble.

Write amplification

Write amplification is the number of bytes the engine writes to disk for each byte the application writes. It drives SSD wear, I/O cost and peak write throughput. The model below is a back-of-the-envelope intuition, not a benchmark: a B-tree that rewrites a whole 8 KiB page per random small update (plus the WAL), and a leveled LSM-tree with size ratio 10 where each record is rewritten about 5 times per level during compaction (plus the WAL and the flush).

Read the plot as intuition:

• For small records updated at random (counters, statuses, events), the B-tree pays for a whole page per tiny change, and the LSM-tree's sequential, batched writes win. That is why write-heavy stores (Cassandra, RocksDB) are LSM-based.
• For large records, the page cost is amortized and the LSM-tree's repeated compaction dominates. Real B-tree engines also batch many updates to the same page before writing it, which lowers their curve a lot for workloads with locality.
• More data means more LSM levels, so its write amplification grows slowly with the dataset.

Indexes

An index is an additional data structure — usually a B-tree — that maps column values to the rows that contain them, so the database finds rows without scanning the whole table. The primary key is always indexed; every other index is your decision, and each one speeds up reads and slows down writes (every INSERT/UPDATE must update every index on the table).

A composite index follows the leftmost-prefix rule: an index on (event_id, section, status) helps queries that filter by event_id, by event_id AND section, or by all three — but not by section alone, just as a phone book sorted by surname then first name does not help you find everyone named "Ana".

Reading EXPLAIN

EXPLAIN shows the plan the database chose; EXPLAIN ANALYZE also runs the query and reports real times. The output below is illustrative, for a seats table with 3 million rows (50 events of 60 k seats):

EXPLAIN ANALYZE
SELECT seat_id, price_cents FROM seats
WHERE event_id = 42 AND section = 'B' AND status = 'AVAILABLE';

-- Seq Scan on seats  (cost=0.00..71842.00 rows=310 width=12)
--                    (actual time=0.031..212.448 rows=287 loops=1)
--   Filter: ((event_id = 42) AND (section = 'B') AND (status = 'AVAILABLE'))
--   Rows Removed by Filter: 2999713
-- Execution Time: 212.502 ms

CREATE INDEX CONCURRENTLY seats_event_section_status_idx
    ON seats (event_id, section, status) INCLUDE (seat_id, price_cents);

-- Index Only Scan using seats_event_section_status_idx on seats
--                    (cost=0.43..18.10 rows=310 width=12)
--                    (actual time=0.025..0.391 rows=287 loops=1)
--   Index Cond: ((event_id = 42) AND (section = 'B') AND (status = 'AVAILABLE'))
-- Execution Time: 0.430 ms

Reading guide: Seq Scan with a large "Rows Removed by Filter" means a missing index; Index Scan walks the index and fetches rows from the table; Index Only Scan answers from the index alone; cost is the planner's estimate in arbitrary units, actual time is what happened. CONCURRENTLY builds the index without blocking writes — essential on a live table. Hands-on 6 does the same diagnosis on the catalog (box below).

-- Lab 6: indexes for the listing "upcoming events in a city, soonest first".
-- Walk events in starts_at order and stop after one page, instead of sorting 20,000 rows:
CREATE INDEX events_starts_at_idx ON catalog.events (starts_at, id);
-- Count/filter the events of a city's venues without reading the whole table:
CREATE INDEX events_venue_starts_at_idx ON catalog.events (venue_id, starts_at);
CREATE INDEX venues_city_idx ON catalog.venues (city);

How it connects

flowchart LR
    REL["relational model<br/>tables, joins, constraints"] --> GUIDE["SQL or NoSQL?<br/>access pattern first"]
    DOC["document"] --> GUIDE
    KV["key-value"] --> GUIDE
    WC["wide-column"] --> GUIDE
    GR["graph"] --> GUIDE
    IDX["indexes: composite order,<br/>EXPLAIN"] --> BT["B-tree<br/>read-optimized, in place"]
    BT -.-> REL
    LSM["LSM-tree<br/>write-optimized, compaction"] -.-> WC
    GUIDE --> TX["invariants<br/>→ Transactions"]
    GUIDE --> PART["known keys at scale<br/>→ Partitioning"]
    KV --> CACHE["in memory<br/>→ Caching, Redis"]

Palette components: sql (the default for data with invariants and ad hoc queries) · nosql (key-value, document, wide-column or graph — chosen by access pattern, keys derived from the queries) · cache (a key-value store in memory) · vectordb (an ANN index is one more index type). Scenarios: monolith, sharding. Continues in: Transactions, Partitioning, Caching — Redis, Estimation — numbers, Hands-on 6 (indexes and EXPLAIN).