Concept 11: Databases Deep-Dive — SQL vs NoSQL, Indexing, Transactions & Storage Engines

System Design Bible — Bonus File 11 Difficulty: ★★★★☆ Why this file exists: Files 04 and 08 assumed you already understood what a database is doing internally — indexes, transactions, ACID, storage engines. This file fills that foundational gap. Almost every system design answer includes "…and we store it in a database"; this file makes you able to say which database and why with authority.

Table of Contents#

0Prerequisites — What You Must Understand First#

Databases feel like magic until you understand the three physical realities they're fighting. Get these first.

0.1The disk vs. memory gulf (why database design is what it is)#

Everything a database does is shaped by one brutal fact from File 02's latency numbers: reading from RAM takes ~100 nanoseconds; reading from a spinning disk takes ~10 milliseconds — a 100,000× difference; even a fast SSD is ~16 microseconds, still ~150× slower than RAM. A database is fundamentally a program that stores more data than fits in RAM (that's the whole point — durable, large data lives on disk) and then tries desperately to avoid touching the disk, because every disk read is an eternity in CPU terms. This single tension explains indexes (data structures that find your row in 3–4 disk reads instead of scanning millions), the buffer pool / page cache (keep the hot subset of data in RAM), and the entire B-tree vs LSM-tree storage-engine debate (two different strategies for laying bytes on disk to minimize slow I/O). If you remember one thing entering this file: database engineering is the art of not touching the disk, and touching it sequentially when you must.

0.2Random I/O vs sequential I/O (the second physical fact)#

Not all disk access is equal. Reading bytes that are physically adjacent on disk (sequential I/O) is dramatically faster than jumping around to scattered locations (random I/O) — on a spinning disk because the read head must physically seek (~10 ms per seek), and even on SSDs because of how flash pages and controllers work. Sequential reads can be hundreds of times faster than random reads for the same volume of data. This is why appending to a log (always sequential) is a beloved pattern (Kafka in File 07, LSM-trees in §6, write-ahead logs in §3), and why a query that must fetch 10,000 scattered rows can be slower than one that scans 1,000,000 sequential ones. When you evaluate a storage design, always ask: is this access pattern sequential or random?

0.3A "page" / "block" is the unit of I/O#

Databases don't read one row at a time from disk — the disk hardware and OS work in fixed-size blocks (typically 4 KB) and databases in pages (often 8 KB or 16 KB). When you read a single 200-byte row, the database actually pulls the whole 8 KB page containing it into memory. This has a huge consequence: rows you access together should be stored together on the same page (locality), because then one page read serves many rows. Indexes, table layout, and clustering all revolve around packing related data into the fewest pages. Keep "the unit of I/O is a page, not a row" in mind — it explains why some queries are mysteriously cheap and others mysteriously expensive.

0.4What "a transaction" means before we formalize it#

A transaction is a group of one or more reads/writes that you want treated as a single indivisible unit: either all of them happen, or none of them do. The canonical example: transferring $100 from account A to account B is two writes — subtract 100 from A, add 100 to B. If the system crashes between them, you've destroyed $100 (A is debited, B never credited). A transaction wraps both writes so that a crash in the middle leaves the database as if neither happened. Everything in §3 (ACID) and §4 (isolation) is about making this guarantee real even under crashes and concurrent access. You don't need the formal properties yet — just hold the mental image of "all-or-nothing bundle of operations."

1Architectural Definition & "The Why"#

1.1The Plain Definition#

A database is a system for storing, retrieving, and managing data durably and efficiently, providing three things a plain file cannot: structured access (find/filter/aggregate data without reading all of it — via indexes and a query language), concurrency control (many clients reading and writing at once without corrupting each other's data — via transactions and locks), and durability + integrity (data survives crashes and stays internally consistent — via write-ahead logs and constraints).

A DBMS (Database Management System) — Postgres, MySQL, MongoDB, Cassandra — is the software that implements this. The two great families are relational (SQL) databases, which store data in tables of rows and columns with rigid schemas and rich querying, and non-relational (NoSQL) databases, which trade some of SQL's guarantees and query power for scale, flexibility, or specific data shapes.

1.2"The Why" — Why Not Just Files?#

Early programs stored data in flat files. This collapses the moment you have real requirements:

The why of the SQL/NoSQL split (§7) is the deeper story: for decades the relational model reigned because its guarantees (ACID, joins, flexible queries) are what applications need. But at internet scale (File 04), the very features that make relational databases powerful — strong consistency, joins, a single logical instance — became the things that don't scale horizontally. NoSQL databases were born (circa 2007–2010, Dynamo and Bigtable papers) by deliberately dropping some of those features (joins, multi-row ACID, rigid schema) in exchange for the horizontal scalability, availability, and write throughput that File 04 and File 08 are about. NoSQL is not "SQL but newer/better" — it's "SQL's guarantees, selectively sacrificed for scale." Understanding which guarantee each NoSQL type sacrifices is the whole game.

2The Recursive Sub-Concept Tree#

2.1Sub-Concept: The Relational Model (tables, rows, schema, keys)#

The relational model organizes data into tables (also called relations). A table has a fixed set of typed columns (e.g., users has id INT, email TEXT, created_at TIMESTAMP) and holds many rows (each row = one entity, one user). The column definitions are the schema — a rigid, enforced-in-advance contract: every row must have exactly these columns of these types, and the database rejects writes that violate it (schema-on-write). This rigidity is a feature — it guarantees data shape so the application never has to defend against a user row missing its email.

Two key concepts tie tables together:

2.2Sub-Concept: The JOIN (the relational superpower and scaling weakness)#

A join combines rows from two tables based on a related column, computed at query time. "Give me each order along with the name and email of the user who placed it" joins orders and users on orders.user_id = users.id. Joins are extraordinarily powerful: they let you store each fact once (users in one table, orders in another — no duplication) and assemble combinations on demand, so updating a user's email is a single-row write that instantly "updates" it everywhere it appears in query results.

But joins are exactly what breaks at scale (File 04). A join needs both tables reachable and, ideally, co-located; once you shard users across 10 machines and orders across 10 others, a join must gather rows from many machines (a cross-shard scatter-gather — File 04 §5.3), which is slow and doesn't scale. This is the crux of the SQL-vs-NoSQL trade: SQL lets you normalize and join (store once, assemble on read); NoSQL often forces you to denormalize (duplicate data so no join is needed) so reads hit one place (§8). Hold this tension — it recurs everywhere.

2.3Sub-Concept: Schema-on-Write vs Schema-on-Read#

2.4Sub-Concept: OLTP vs OLAP (two opposite workloads)#

A pervasive distinction that decides which database and design you pick:

The critical rule (echoing File 04 §5.3): do not run heavy OLAP queries against your OLTP database — a report scanning your entire orders table will lock and choke the transactional workload your users depend on. You keep them separate and feed the OLAP system from the OLTP system asynchronously (via CDC/ETL streaming, File 07). Mixing them is one of the most common real-world scaling mistakes.

3ACID vs BASE — The Transaction Guarantees#

3.1ACID (the relational guarantee)#

ACID is four properties that together define a "reliable transaction." They're the reason you can trust a relational database with money.

A — Atomicity. A transaction is all-or-nothing: every operation in it commits, or (on any failure/crash) none do — the database rolls back to the pre-transaction state. This is the $100-transfer guarantee from §0.4: a crash between the debit and credit leaves neither, never a half-transfer. Atomicity is implemented with a write-ahead log (WAL):

Sub-Concept: Write-Ahead Log (WAL). Before the database modifies the actual data pages on disk, it first appends a record of the intended change to a sequential log (and flushes that log to disk). Only after the change is safely in the log does it modify the data. Why this ordering? Because the log write is a fast sequential append (§0.2), and it's durable: if the database crashes mid-transaction, on restart it replays the log to either finish committed transactions (redo) or undo incomplete ones (undo), reconstructing a consistent state. The WAL is the mechanism behind both Atomicity and Durability — the same "log-before-apply, replay-on-recovery" pattern you saw as the metadata master's operation log in File 09 §4.4 and as the replicated log in File 08. One idea, everywhere.

C — Consistency. A transaction moves the database from one valid state to another valid state, never violating declared rules (constraints, foreign keys, uniqueness, triggers). If a transaction would leave a dangling foreign key or a duplicate unique value, the database rejects the whole transaction. (Note: this "C" — application-level invariants — is confusingly different from the "C" in CAP theorem, File 08, which is about all replicas agreeing. Two different C's; interviewers love this trap.)

I — Isolation. Concurrent transactions must not step on each other; the result of running them simultaneously should be as if they ran one after another (serially). This is the hardest and most nuanced property — in practice databases offer a spectrum of isolation levels trading strictness for performance, which is important enough to get its own section (§4).

D — Durability. Once a transaction is committed, it survives permanently — even an immediate power loss. The committed data is on durable storage (the WAL, then the data files, plus replication to other nodes, File 08). "Committed means it's really, truly saved" is the promise.

3.2BASE (the NoSQL alternative)#

Many distributed NoSQL databases (especially the AP systems of File 08) can't provide full ACID across a cluster cheaply — recall CAP: strong consistency costs availability during partitions, and coordinating ACID across many nodes costs latency. So they adopt BASE, a deliberately looser model whose acronym is a chemistry pun on ACID:

ACID vs BASE is not good vs bad — it's a trade you match to the data. Money, inventory, bookings → ACID (a wrong answer is catastrophic; you'll accept lower availability/scale to be correct). Likes, feed items, view counts, session data, product catalogs → BASE (being briefly stale is harmless; being available and scalable matters more). Real systems use both: ACID Postgres for orders/payments, BASE Cassandra/DynamoDB for the activity feed — in the same product. The skill is knowing which data goes where.

4Isolation Levels & Concurrency Anomalies#

Isolation (the "I" in ACID) is a dial, not a switch, because perfect isolation is expensive (it requires serializing conflicting transactions, which limits concurrency and throughput). So databases offer levels, each permitting certain anomalies in exchange for more concurrency. You must know the anomalies to know what each level protects against.

4.1The Anomalies (what goes wrong without isolation)#

4.2The Levels (weakest to strongest)#

4.3How Isolation Is Implemented: Locking vs MVCC#

5Indexing — How Databases Find Data Fast#

5.1The Problem an Index Solves#

Without an index, finding rows matching a condition (WHERE email = 'x@y.com') requires a full table scan — reading every row from disk and checking it. On 500M rows that's minutes and enormous I/O. An index is an auxiliary data structure that lets the database jump to matching rows in a handful of disk reads instead of scanning everything. It's the single most important tool for database performance, and "add an index" is the answer to a huge fraction of "the query is slow" problems.

The analogy: an index is the index at the back of a textbook. To find "mitochondria," you don't read all 900 pages (full scan); you flip to the alphabetical index (a sorted structure), find "mitochondria → p. 412," and jump straight there. The book's index is sorted and small; the content is large and unsorted. Same idea.

5.2What an Index Actually Is#

An index is a separate, sorted data structure (usually a B-tree, §6.1) mapping the indexed column's values → the locations of the matching rows (their primary keys or physical addresses). Because it's sorted, the database can binary-search it (or tree-walk it) in O(log N) — for 500M rows, ~30 comparisons / ~4 disk page reads instead of 500M. You create one explicitly: CREATE INDEX ON users(email). The primary key is automatically indexed.

5.3The Fundamental Trade-off: Reads vs Writes vs Space#

Indexes are not free — this trade is essential to state in interviews:

So indexing is a workload-driven decision: index the columns in your WHERE/JOIN/ORDER BY clauses, resist indexing rarely-queried columns, and remember that a write-heavy table wants fewer indexes while a read-heavy one can afford more.

5.4Types of Index (the ones worth naming)#

6Storage Engines: B-Tree vs LSM-Tree#

The storage engine is the component that decides how bytes are physically laid out on disk and read back. The two dominant designs make opposite trade-offs, and this is a favorite deep-dive question because it reveals whether you understand the disk-I/O realities of §0.

6.1B-Tree (the read-optimized classic)#

Sub-Concept: B-Tree. A B-tree is a balanced tree structure kept sorted on disk, where each node is one disk page (§0.3) holding many keys and pointers to child pages. It's shallow and wide (a node has hundreds of children), so even a billion keys live in a tree only ~4 levels deep — meaning any key is found in ~4 disk reads by walking root → branch → branch → leaf. Crucially, B-trees update data in place: to change a value, you find its page and overwrite it where it sits.

6.2LSM-Tree (the write-optimized challenger)#

Sub-Concept: LSM-Tree (Log-Structured Merge-Tree). An LSM-tree is built on a radically different idea: never do random writes; only ever append sequentially. Writes go first to an in-memory sorted structure called the memtable (fast, RAM). When the memtable fills, it's flushed to disk as an immutable sorted file (SSTable — Sorted String Table) in one big sequential write. Files are never modified after being written — updates and deletes are just new entries appended later (a delete writes a "tombstone" marker). A background process compaction periodically merges the many small SSTables into fewer larger ones, discarding superseded/deleted entries. A read may have to check the memtable plus several SSTables (newest first), accelerated by Bloom filters (File 02 §6.1 — "is this key possibly in this file?") so it skips files that definitely don't contain the key.

6.3The Decision#

Interview line: "If the workload is write-heavy (time-series, event ingestion, high-volume logging), lean LSM (Cassandra/RocksDB); if it's read-heavy or needs predictable low-latency point/range reads, lean B-tree (Postgres/MySQL). The core reason is that LSM turns all writes into fast sequential appends while B-trees do slower random in-place updates."

6.4Bonus: Row-Oriented vs Column-Oriented Storage (OLTP vs OLAP again)#

Orthogonal to B-tree/LSM is how you group a row's columns on disk:

7SQL vs NoSQL — The Real Decision#

7.1Why "SQL vs NoSQL" Is the Wrong Framing (and the right one)#

"NoSQL" is a terrible name — it lumps four completely different database types together whose only shared trait is "not a traditional relational table with SQL." The real decision isn't "SQL or NoSQL"; it's "which of these five tools fits my data shape and access pattern and scale?" Here they are, each with what it sacrifices and what it buys.

7.2Relational / SQL (Postgres, MySQL)#

7.3Key-Value stores (Redis, DynamoDB, Riak)#

7.4Document stores (MongoDB, Couchbase)#

7.5Wide-column stores (Cassandra, HBase, ScyllaDB, Bigtable)#

7.6Graph databases (Neo4j, Neptune)#

7.7A word on NewSQL (Spanner, CockroachDB, TiDB, Vitess)#

The newest category tries to have both: SQL's relational model + ACID transactions with NoSQL's horizontal scalability, by sharding automatically and using consensus (File 08's Raft/Paxos, Spanner's TrueTime) under the hood. This is increasingly the answer to "I need relational guarantees and to scale writes horizontally" — see File 08 §10.1 (Spanner). Worth naming; it dissolves the old "you must choose SQL or scale" dichotomy.

7.8The Decision Framework (say this in interviews)#

Don't recite "SQL good, NoSQL scalable." Reason from the data:

And almost every real system is polyglot persistence — several of these together, each holding the data it fits best (Postgres for orders + Redis for cache/sessions + Cassandra for the event feed + Elasticsearch for search).

8Normalization vs Denormalization#

8.1Normalization (store each fact once)#

Normalization is organizing relational data so that each piece of information is stored in exactly one place, with relationships expressed via foreign keys. Instead of copying a user's name into every one of their 10,000 orders, you store the user once in users and put a user_id reference in orders; queries join to assemble the combination.

8.2Denormalization (duplicate for read speed)#

Denormalization deliberately copies data so reads don't need joins — e.g., store the user's name inside each order row. Now "show this order with the buyer's name" is a single-row read, no join.

8.3The Rule of Thumb#

Normalize until it hurts (reads too slow / joins too costly), then denormalize until it works. Relational OLTP tends to start normalized (integrity first); scale and NoSQL push toward denormalization (read speed first). The trade is fundamentally read cost vs write/consistency cost, and it's the same tension as File 02's caching (a cache is a denormalized copy you must invalidate) and File 04's shard-key/locality decision. When you denormalize, you take on the job of keeping the copies in sync — often via the async event pipelines of File 07 (write once, fan out updates to all the denormalized copies).

9Interview Diagnostic Framework (Symptom → Solution)#

10Real-World Engineering Scenarios#

10.1Amazon — Polyglot Persistence & the Birth of DynamoDB#

10.2Discord — Cassandra/ScyllaDB (LSM) for the Message Firehose#

10.3A Typical SaaS — Postgres + Read Replicas + Redis, then shard#

11Interview Gotchas & Failure Modes#

11.1Classic Questions#

11.2Failure Modes & Mitigations#

12Whiteboard Cheat Sheet#

 PHYSICAL TRUTHS: RAM ~100ns vs disk ~10ms (100,000x) | sequential >> random I/O | I/O unit = 8KB page
 GOAL OF ALL DB DESIGN: avoid touching disk; when you must, touch it SEQUENTIALLY.

 ACID (relational): Atomic(all-or-nothing, WAL) Consistent(valid->valid, constraints; != CAP's C)
                    Isolated(concurrent = as-if-serial; a SPECTRUM) Durable(committed survives crash)
 BASE (NoSQL/AP):   Basically-Available, Soft-state, Eventually-consistent  (File 08 CAP)
 -> money/inventory=ACID ; feeds/counts/sessions=BASE ; real systems use BOTH.

 ISOLATION (weak->strong): ReadUncommitted < ReadCommitted(PG default) < RepeatableRead(MySQL) < Serializable
   anomalies: dirty read | non-repeatable read | phantom read | lost update
   impl: pessimistic LOCKING (deadlock risk) vs optimistic MVCC (snapshots; readers don't block writers)

 INDEX = sorted side structure -> O(log N) lookup vs full scan. Costs: slower writes + storage.
   clustered(1, physical order) | secondary(many) | composite(leftmost-prefix!) | covering | hash(eq-only)

 STORAGE ENGINE:
   B-TREE  -> read-optimized, random in-place writes, ~4 reads/key (Postgres,MySQL,Oracle)
   LSM-TREE-> write-optimized: memtable -> flush immutable SSTables -> compaction; Bloom filters on read
              (Cassandra,RocksDB,HBase). Writes = sequential appends = FAST.
   ROW storage (OLTP: whole-row reads) vs COLUMN storage (OLAP: scan few cols over billions; Snowflake/BQ)

 SQL vs NoSQL = pick the tool for data shape + access + scale + consistency:
   Relational(ACID,joins; DEFAULT) | Key-Value(lookup by key, huge scale) | Document(flexible, read-whole)
   Wide-Column(write firehose, LSM) | Graph(traverse relationships) | NewSQL(relational+ACID+horizontal)
   -> most real systems = POLYGLOT PERSISTENCE (several together).

 NORMALIZE (store once, join; integrity)  <-->  DENORMALIZE (duplicate, no join; read speed, update fan-out)
   "normalize till it hurts, denormalize till it works."
 OLTP (small fast point ops, your app DB)  vs  OLAP (huge scans/aggregates, warehouse) — NEVER mix them.

One-sentence summary for an interviewer:

"A database is a program engineered around the fact that disk is ~100,000× slower than RAM, so it uses indexes (sorted B-trees → O(log N) lookups instead of full scans, paid for in slower writes), transactions with ACID (atomic via a write-ahead log, isolated via MVCC/locking on a spectrum of levels) for correctness-critical data, or BASE/eventual consistency for scale; its storage engine is either a B-tree (read-optimized, random in-place writes — Postgres/MySQL) or an LSM-tree (write-optimized sequential appends + compaction — Cassandra/RocksDB); and 'SQL vs NoSQL' really means picking among relational, key-value, document, wide-column, graph, and NewSQL by data shape, access pattern, scale, and consistency needs — defaulting to relational and going polyglot, normalizing for integrity but denormalizing for read-speed at the cost of update fan-out."

End of Bonus File 11. See also File 12 (The System Design Interview Playbook) for how to apply* all of this under interview pressure.*