Database Design

Every application that stores data runs into the same questions: how should the data be organised, how can many users read and change it at once without corrupting it, what happens when a machine crashes, and how does the system grow beyond one server? This section answers them in depth — from normalization and SQL execution, through transactions and storage engines, to replication, distributed transactions and NoSQL data models, and finally to running databases in production.

New to databases? The Database Crash Course covers tables, SQL, relationships, indexes and transactions in a single page. Read it first, then return here for the internals and the scaling concerns.

Guides

Suggested reading order

The guides build on one another. Each later topic assumes the guarantees described by the earlier ones:

flowchart LR
    M["Modeling &<br/>normalization"] --> I["Indexing &<br/>query execution"]
    I --> T["Transactions &<br/>concurrency"]
    T --> S["Storage engines<br/>& recovery"]
    S --> D["Distributed &<br/>NoSQL (sub-hub)"]
    D --> R["Replication &<br/>consensus"]
    D --> DT["Distributed<br/>transactions"]
    D --> N["NoSQL data<br/>models"]
    S --> O["Operations &<br/>monitoring"]
    M --> ORM["ORMs &<br/>data access"]
    M --> SE["Schema evolution<br/>& migrations"]

Why a Database

Consider an online store that keeps its products in a file:

[
  {"id": 1, "name": "Laptop", "price": 999, "stock": 50},
  {"id": 2, "name": "Mouse",  "price": 29,  "stock": 200}
]

This works until the questions a database exists to answer arrive:

Core Principles

• Model for integrity first. Normalization removes redundant copies so that an update cannot leave the data contradicting itself. Denormalize deliberately, for measured performance needs.
• Indexes trade write cost for read speed. A B+ tree index turns a full scan into a logarithmic lookup, but every index is maintained on every relevant write and occupies cache.
• Transactions make concurrency tractable. Atomicity, consistency, isolation and durability let many clients use shared data without corrupting it. Weaker isolation levels are faster but admit specific, documented anomalies.
• The planner decides how a query runs. SQL describes the result; the optimizer chooses the access paths and join order from statistics. EXPLAIN ANALYZE shows what it chose and whether its estimates were right.
• Distribution forces trade-offs. Replication and partitioning add capacity and resilience, but during a network partition a system must choose between consistency and availability, and even without one, stronger consistency costs latency.
• Choose the data model by access pattern. Relational, document, key-value, wide-column, graph, time-series and vector stores each make different queries cheap. Start relational unless a specific pattern or scale requirement says otherwise.

Glossary

References

Books

• Kleppmann, M. Designing Data-Intensive Applications (O’Reilly, 2017; a revised second edition co-authored with Chris Riccomini followed). The standard overview of storage, replication, partitioning, transactions and stream processing.
• Petrov, A. Database Internals (O’Reilly, 2019). Storage engines and distributed-systems algorithms in detail.
• Karwin, B. SQL Antipatterns (Pragmatic Bookshelf; 2nd edition 2022). Common schema and query mistakes and their fixes.
• Winand, M. SQL Performance Explained, also available free as Use The Index, Luke. Indexing from the developer’s side.
• Ramakrishnan, R. and Gehrke, J. Database Management Systems (3rd edition, 2003). A thorough university textbook.

Courses, documentation and papers

• CMU Database Group — recorded lectures from Andy Pavlo’s introductory and advanced database systems courses.
• PostgreSQL documentation — particularly the chapters on indexes, EXPLAIN, concurrency control and the planner’s statistics.
• Jepsen analyses — independent tests of distributed databases’ consistency claims.
• The Morning Paper — summaries of database and systems papers (archive; publication ended in 2021).
• Proceedings of SIGMOD, VLDB and CIDR for current research.

Practice

• PostgreSQL Exercises — graded SQL practice against a sample schema.
• SQL Murder Mystery — learn SQL by solving a case.

Build-your-own projects

Building a small database is the most direct way to understand one. A progression, each step building on the last:

1. Log-structured key-value store — an append-only log plus an in-memory hash index; add compaction and crash recovery.
2. B+ tree — insertion with node splits, deletion, and range scans over linked leaves, backed by fixed-size pages and a buffer pool.
3. Query engine — parse a subset of SQL, build an iterator-model operator tree (scan, filter, project, nested-loop and hash join), and add a simple cost-based choice between plans.
4. Transactions — write-ahead logging with redo recovery, then two-phase locking or MVCC for isolation.
5. Replicated key-value store — Raft leader election and log replication across three nodes (MIT’s distributed-systems labs follow this path).

CMU’s educational database, BusTub, provides a skeleton for steps 2–4.

See Also

• Database Crash Course — the fast introduction to tables and SQL.
• AWS — managed relational, key-value and serverless database services.
• Docker — running databases in containers for local development.
• Cybersecurity — access control, encryption and SQL injection.
• Networking — the protocols beneath distributed databases.