Build Your Own Database in Go From Scratch - From B+tree to SQL in 3000 lines, 2nd Edition (James Smith)（Z-Library）

# Build Your Own Database in Go From Scratch - From B+tree to SQL in 3000 lines, 2nd Edition ## 【One-Line Pitch】 A hands-on, incremental guide to building a complete database from scratch—from durable file storage and B+tree indexing to SQL parsing and concurrent transactions—in about 3000 lines of Go code. Perfect for developers who want to truly understand how databases work by building one themselves. ## 【Book Arc】 - **Opening (~0%–10%)**: Introduces the core challenges of database design—atomicity, durability, crash recovery, and why disks behave differently from RAM. Establishes the roadmap: files → indexing → B-tree → KV store → relational layer → SQL → concurrency. - **Early (~10%–23%)**: Explains indexing data structures, contrasting in-memory vs. on-disk approaches. Covers why B-trees beat binary trees for disk I/O (shorter trees, page-sized nodes) and introduces the B+tree as nested sorted arrays with copy-on-write semantics. - **Middle (~23%–42%)**: Implements the B+tree data structure in Go—node format design, insertion with node splitting, deletion with merging, and testing strategies. Introduces the three core invariants (balanced height, bounded node size, non-empty nodes) and the sentinel key trick. - **Late (~42%–60%)**: Builds the durable KV store layer: append-only file writing, fsync discipline, crash recovery via copy-on-write, and the free list for space reuse. Shows how to persist the B+tree to disk with proper ordering guarantees. - **Ending (~60%–100%)**: Layers the relational database on top of the KV store—mapping tables and indexes to B-trees, implementing range queries and secondary indexes, then adding atomic transactions, concurrency control, and finally a recursive-descent SQL parser and interpreter. ## 【Key Takeaways】 - **Disks are not just slow RAM** (Early): In-place updates risk corruption after crashes; the OS page cache and sector-based I/O force databases to think in pages and use fsync carefully. This motivates append-only and copy-on-write designs. - **B-trees beat binary trees for disk** (Early): N-ary trees reduce disk reads per lookup (logₙN vs log₂N), and nodes should align with page sizes (typically 4KB) to avoid wasted I/O. Larger nodes mean fewer reads but slower updates—a fundamental trade-off. - **Copy-on-write is the crash-safety foundation** (Middle): Instead of updating nodes in place, write new versions and atomically swap the root pointer. This reduces crash recovery to a single pointer update, though it requires a free list to reclaim old node versions. - **Three invariants maintain B+tree correctness** (Middle): Same height for all leaves, bounded node size, and non-empty nodes. Insertion splits oversized nodes (propagating upward), deletion merges underfull ones—both preserving these invariants. - **fsync ordering is the durability contract** (Late): Write new pages → fsync → update root pointer → fsync again. The directory fsync after file creation/renaming is a common gotcha. A log-based alternative can reduce fsyncs by batching updates. - **The free list solves space reuse** (Late): Append-only files grow unboundedly without recycling; a free list tracks deallocated pages for reuse. This completes the practical KV store beyond the naive append-only version. - **SQL is just a user interface** (Ending): The real database is the storage engine underneath—tables and indexes are mapped to B-trees over KV pairs. The SQL parser and interpreter are surprisingly simple, built entirely with recursion. - **Concurrency needs copy-on-write** (Ending): The immutable, append-only nature of copy-on-write structures enables concurrent transactions without locks on reads, with careful handling of write conflicts. ## 【Reading Tips】 - **Skim the first two chapters** (~0–10%) if you're already familiar with file I/O and basic durability concepts; they set up terminology but the real meat starts with B-tree design. - **Deep-read chapters 3–5** (~10–42%): The B+tree implementation is the heart of the book. Work through the node format, insertion, and deletion code carefully—these are the most conceptually dense sections. - **Pay special attention to the node format design** (Chapter 4): The binary layout (header, pointers, offsets, KV pairs) determines everything downstream, including page size decisions and split/merge logic. - **The SQL parser chapter is easier than it looks** (~88%+): The author notes it's "nothing but recursion"—skim the grammar details and focus on how the interpreter maps SQL operations back to KV/B-tree operations. - **Don't skip the testing sections**: The fake node callbacks and in-memory testing strategy are valuable patterns for validating data structures before adding disk I/O complexity. ## 【Coverage Limits】 This guide covers the book's progression from file fundamentals through B+tree implementation, durable KV storage, and the relational/SQL layer. The excerpts do not cover the detailed SQL parser implementation, specific concurrency control algorithms, or the final transaction isolation levels in depth. ##