Learn how databases work: the best books in order
This curriculum is designed for expert-level engineers who want to achieve deep, internals-level mastery of how databases are built — from the physical layout of data on disk to the algorithms that power indexes, transactions, and query engines. The four stages move from foundational storage structures, through concurrency and transaction theory, into distributed systems concerns, and finally into the cutting-edge research and implementation details that define modern database design.
Storage Structures & Core Internals
ExpertDeeply understand how data is physically stored, how B-trees and LSM-trees work, how buffer pools and disk I/O are managed, and how storage engines are architected from the ground up.
▸ Study plan for this stage
Pace: 12–14 weeks, ~40–50 pages/day (mix of dense technical content and review cycles)
- B-tree and LSM-tree data structures: node organization, insertion/deletion, balancing, and search complexity trade-offs
- Storage engine architecture: write-ahead logging (WAL), memtables, SSTables, compaction strategies, and the lifecycle of data from write to disk
- Buffer pool management: page replacement policies (LRU, clock), pinning/unpinning, dirty page handling, and I/O scheduling
- Disk I/O fundamentals: sequential vs. random access patterns, block-level operations, and how storage engines optimize for disk characteristics
- Index structures beyond B-trees: hash indexes, bitmap indexes, and their trade-offs in different workload scenarios
- Transaction processing foundations: ACID properties, isolation levels, concurrency control mechanisms, and recovery protocols
- Crash recovery and durability: redo/undo logging, checkpoint strategies, and ensuring consistency after failures
- Cost models and performance tuning: understanding query execution costs, I/O patterns, and how to reason about storage engine design decisions
- How do B-trees and LSM-trees differ in their approach to balancing write and read performance, and what are the trade-offs of each?
- Explain the role of the buffer pool in a storage engine and describe at least two page replacement policies and when each is appropriate.
- What is write-ahead logging (WAL) and why is it critical for durability and crash recovery?
- How do compaction strategies in LSM-trees (e.g., leveled vs. tiered) affect write amplification, space amplification, and read performance?
- Describe the lifecycle of a data write in a modern storage engine, from the application layer through to persistent disk storage.
- What are the four ACID properties and how do different isolation levels (READ UNCOMMITTED, READ COMMITTED, REPEATABLE READ, SERIALIZABLE) trade off consistency and concurrency?
- How do redo and undo logs work together to ensure crash recovery and transaction atomicity?
- Given a workload profile (e.g., write-heavy, read-heavy, mixed), how would you reason about which storage structure (B-tree, LSM-tree, hash index) is most suitable?
- Implement a simplified B-tree (insertion, deletion, search) in a language of your choice; measure and document the I/O patterns for different tree heights and node sizes.
- Build a toy LSM-tree with at least two levels (memtable and L0 SSTables); implement a basic compaction strategy and measure write amplification.
- Simulate a buffer pool with multiple page replacement policies (LRU, clock); run synthetic workloads and compare hit rates and eviction patterns.
- Trace through a write operation in a real database (e.g., SQLite, RocksDB) using a debugger or logging; document the path from SQL to disk I/O.
- Design and implement a simple write-ahead log; test crash recovery by simulating a failure mid-transaction and verifying that the log can restore consistency.
- Create a cost model calculator: given a query plan, estimate the number of I/O operations for different storage structures and compare predicted vs. actual performance.
- Analyze real-world compaction logs from RocksDB or LevelDB; identify patterns in space/write amplification and propose optimizations.
- Implement a basic two-phase locking (2PL) concurrency control mechanism; test it under concurrent transactions and verify isolation level guarantees.
Next up: This stage equips you with the low-level architectural knowledge and hands-on intuition to understand how databases optimize for real-world workloads; the next stage will build on this foundation to explore distributed systems, replication, and how these storage principles scale across multiple machines.
The ideal starting point for this curriculum: a focused, modern deep-dive into storage engine internals, B-trees, LSM-trees, and distributed database components. It establishes the precise vocabulary and mental models needed for everything that follows.
Gray's foundational text defines the canonical concepts of logging, recovery, locking, and buffer management at an engineering depth that no other book matches. Read it second to ground the storage-layer intuitions from Petrov in rigorous theory.
Query Processing & Execution Engines
ExpertUnderstand how a database parses, plans, optimizes, and executes queries — including join algorithms, cost models, and vectorized execution — and how these layers interact with the storage engine below.
▸ Study plan for this stage
Pace: 6–8 weeks, ~40–50 pages/day (with deeper dives into algorithm sections)
- Query parsing and translation: converting SQL text into an internal query representation (parse trees, logical operators)
- Query optimization: cost-based optimization, selectivity estimation, and the role of statistics in choosing execution plans
- Join algorithms: nested-loop, sort-merge, and hash joins; when and why each is chosen based on cost models
- Query execution engines: iterator (pull-based) vs. vectorized (push-based) execution models and their tradeoffs
- Cost models and cardinality estimation: how databases predict row counts and resource consumption to drive plan selection
- Interaction between query execution and storage: how execution engines leverage indexes, buffer management, and disk I/O patterns
- Plan caching and adaptive execution: reusing plans and adjusting execution based on runtime statistics
- Distributed query processing: query distribution, data movement, and coordination in multi-node systems
- Explain the difference between nested-loop, sort-merge, and hash join algorithms. Under what conditions would a query optimizer choose each one?
- How does a cost-based query optimizer use cardinality estimates and cost models to select an execution plan? What happens when estimates are wrong?
- Describe the iterator (pull-based) execution model. How does it differ from vectorized execution, and what are the performance implications of each?
- Walk through the complete pipeline from SQL query text to physical execution plan. What transformations occur at each stage (parsing, logical optimization, physical planning)?
- How do indexes and buffer management influence query execution? Give an example of how an execution engine might leverage an index to reduce I/O.
- What is selectivity estimation, and why is it critical to query optimization? How do databases estimate selectivity when statistics are unavailable or stale?
- Implement a simple cost model for join operations: write code that estimates the cost of nested-loop vs. hash join given table sizes, memory constraints, and I/O costs.
- Parse a complex SQL query (e.g., multi-table join with WHERE clauses) by hand, building the parse tree and identifying logical operators; then sketch how a cost-based optimizer might transform it.
- Trace through a hash join algorithm step-by-step on a small dataset: build the hash table, probe it, and count I/O operations; compare to nested-loop cost on the same data.
- Analyze a real query execution plan (from PostgreSQL EXPLAIN, MySQL EXPLAIN, or SQLite QUERY PLAN) and explain why the optimizer chose that plan; identify the join order, join algorithms, and estimated vs. actual row counts.
- Implement cardinality estimation for a simple predicate (e.g., column > value) using histogram-based statistics; test accuracy against actual row counts.
- Design a vectorized execution operator (e.g., a filter or projection) that processes batches of rows; compare its performance to a row-at-a-time iterator implementation on a synthetic dataset.
Next up: This stage equips you with a deep understanding of how queries are transformed and executed, preparing you to explore transaction processing, concurrency control, and recovery mechanisms—the layers that ensure correctness and isolation while queries run concurrently.
Covers query compilation, operator execution, join strategies, and index usage at implementation depth, bridging the gap between storage internals and the full database engine stack.
The standard graduate-level reference for query optimization, cost estimation, and execution plans; read alongside or after Garcia-Molina to reinforce and extend the optimizer internals picture.
Concurrency, Transactions & Recovery
ExpertMaster the full theory and implementation of ACID transactions, isolation levels, MVCC, write-ahead logging, ARIES recovery, and lock-based and optimistic concurrency control.
▸ Study plan for this stage
Pace: 8–10 weeks, ~40–50 pages/day (Bernstein first 4–5 weeks, then Kleppmann 3–4 weeks, with 1–2 weeks for integration and projects)
- ACID properties (Atomicity, Consistency, Isolation, Durability) and their formal definitions and trade-offs
- Isolation levels (serializable, repeatable read, read committed, read uncommitted) and anomalies they prevent (dirty reads, non-repeatable reads, phantom reads, write skew)
- Lock-based concurrency control: two-phase locking (2PL), deadlock detection and prevention, lock granularity and escalation
- Optimistic concurrency control: timestamp ordering, MVCC (multi-version concurrency control), and snapshot isolation
- Write-ahead logging (WAL) principles: undo/redo logs, log records, and the WAL protocol
- ARIES recovery algorithm: analysis phase, redo phase, undo phase, and crash recovery correctness
- Transaction scheduling, serializability, conflict graphs, and precedence analysis
- Practical trade-offs: performance vs. correctness, consistency models in distributed systems, and real-world isolation level implementations
- Explain the ACID properties and why each is necessary. What are the practical trade-offs when relaxing each property?
- Compare lock-based (2PL) and optimistic concurrency control: when would you use each, and what are their performance characteristics under different contention scenarios?
- What is MVCC and how does it enable higher concurrency than traditional locking? How does snapshot isolation differ from serializability?
- Walk through the ARIES recovery algorithm: what happens in each phase (analysis, redo, undo) and why is the order critical?
- What is write-ahead logging and why is it essential for durability? Explain the difference between undo and redo logs.
- Define the four standard isolation levels (serializable, repeatable read, read committed, read uncommitted) and the anomalies each prevents. Which anomalies can occur at each level?
- How do real-world databases (PostgreSQL, MySQL, Oracle) implement isolation levels differently, and what are the performance implications?
- Implement a simple two-phase locking (2PL) scheduler in pseudocode or a language of your choice: track lock requests, detect deadlocks, and enforce the 2PL protocol for a sequence of transactions.
- Trace through a multi-transaction execution and identify all anomalies (dirty reads, non-repeatable reads, phantom reads, write skew) that would occur at each isolation level.
- Build a write-ahead log (WAL) simulator: write transactions to an undo/redo log, simulate a crash at different points, and verify that recovery produces the correct final state.
- Implement the ARIES recovery algorithm on a toy database: run the analysis, redo, and undo phases on a crash scenario and verify correctness.
- Analyze a real database's isolation level documentation (PostgreSQL, MySQL, or Oracle): map their implementation to the theory in Bernstein and Kleppmann, and identify which anomalies are prevented.
- Design a concurrency control strategy for a specific workload (e.g., high-contention OLTP vs. long-running analytical queries): justify your choice of locking vs. optimistic control and isolation level.
Next up: This stage equips you with the theoretical foundations and practical understanding of how databases maintain correctness under concurrency and failure, preparing you to tackle distributed transactions, consensus protocols, and consistency models in geographically distributed systems.
The definitive theoretical treatment of serializability, locking protocols, and recovery algorithms; establishes the formal foundations that underpin every modern RDBMS concurrency implementation.
Bridges theory and modern practice by examining how real systems (PostgreSQL, InnoDB, Kafka, Spanner) implement transactions, replication, and consistency — essential for connecting academic models to production code.
Distributed Databases & Research Frontiers
ExpertUnderstand consensus protocols, distributed transactions, replication, partitioning, and the design trade-offs of modern NewSQL and cloud-native database systems at research depth.
▸ Study plan for this stage
Pace: 8–10 weeks, ~40–50 pages/day (mix of dense technical content and research papers; allow 2–3 days per major topic for synthesis)
- Consensus protocols (Paxos, Raft, Byzantine Fault Tolerance) and their correctness guarantees under network partitions
- Distributed transaction models: 2-phase commit, 3-phase commit, and their limitations in asynchronous networks
- Replication strategies (primary-backup, multi-master, quorum-based) and consistency models (strong, eventual, causal, session)
- Data partitioning and sharding: range, hash, and directory-based schemes; handling skew and rebalancing
- CAP theorem and PACELC trade-offs: how modern systems navigate consistency, availability, and partition tolerance
- NewSQL and cloud-native design: how systems like Spanner, CockroachDB, and Aurora challenge traditional distributed database assumptions
- Failure detection, recovery, and durability in distributed settings (write-ahead logging, checkpointing, log-based recovery)
- Research frontiers: recent innovations in consensus, geo-replication, and adaptive consistency
- Explain the FLP impossibility result and why it matters for distributed consensus. What guarantees can Paxos and Raft actually provide?
- Compare 2-phase commit and Saga-based approaches for distributed transactions. Under what conditions does each fail, and why?
- What is the difference between strong consistency, eventual consistency, and causal consistency? Give a concrete example where each is appropriate.
- How do primary-backup replication and quorum-based replication differ in handling failures? What are the trade-offs in latency and availability?
- Describe how a distributed database system partitions data across nodes. How does it handle hot partitions and rebalancing?
- What does the CAP theorem actually say, and why is PACELC a more nuanced framework? How do Spanner and CockroachDB position themselves?
- Walk through the recovery process after a node failure in a distributed database. What role do write-ahead logs and checkpoints play?
- Implement a simplified Raft consensus protocol (leader election and log replication) in a language of your choice; test with network partitions and node failures.
- Build a toy distributed transaction coordinator that handles 2-phase commit; deliberately introduce failures (timeouts, crashes) and observe the outcome.
- Design a data partitioning scheme for a hypothetical e-commerce database (users, orders, inventory); identify hot partitions and propose rebalancing strategies.
- Analyze a research paper from 'Readings in database systems' (e.g., on Spanner or a recent consensus variant); write a 2–3 page summary explaining its key innovation and trade-offs.
- Set up and experiment with a real distributed database (CockroachDB, Cockroach Labs' free tier, or TiDB) across multiple nodes; observe consistency behavior under network delays and failures.
- Create a comparison matrix of 3–4 modern distributed databases (Spanner, CockroachDB, Aurora, Cassandra) on dimensions: consensus protocol, consistency model, partitioning strategy, and failure recovery.
- Trace through a concrete scenario (e.g., a multi-region transaction with a network partition) and determine which consistency guarantees hold and which are violated.
Next up: This stage establishes the theoretical foundations and practical patterns of distributed database design; the next stage will likely focus on specialized topics (e.g., time-series databases, graph databases, or stream processing systems) or on building production systems that apply these principles under real-world constraints.
The canonical graduate text on distributed query processing, distributed transactions, and replication — provides the rigorous distributed-systems foundation that cloud databases are built on.
Known as the 'Red Book,' this curated collection of landmark database research papers covers columnar storage, query optimization, stream processing, and NewSQL — the ideal capstone for understanding where the field has been and where it is going.
Discussion
Keep reading
Paths that share books, cover the same subject, or open a related topic.
