Build Your Own Database From Scratch in Go: From B+Tree To SQL in 3000 Lines (Build Your Own X From Scratch)

Cover
Contents
00. Introduction
	Master fundamentals by building your own DB
		What to learn?
		Code a database in 3000 LoC, incrementally
		Learn by doing: principles instead of jargon
	Topic 1: durability and atomicity
		More than a data format
		Durability and atomicity with `fsync`
	Topic 2: indexing data structures
		Control latency and cost with indexes
		In-memory data structures vs. on-disk data structures
	Topic 3: Relational DB on KV
		Two layers of DB interfaces
		Query languages: parsers and interpreters
	Build Your Own X book series
01. From Files To Databases
	1.1 Updating files in-place
	1.2 Atomic renaming
		Replacing data atomically by renaming files
		Why does renaming work?
	1.3 Append-only logs
		Safe incremental updates with logs
		Atomic log updates with checksums
	1.4 `fsync` gotchas
	1.5 Summary of database challenges
02. Indexing Data Structures
	2.1 Types of queries
	2.2 Hashtables
	2.3 Sorted arrays
	2.4 B-tree
		Reducing random access with shorter trees
		IO in the unit of pages
		The B+tree variant
		Data structure space overhead
	2.5 Log-structured storage
		Update by merge: amortize cost
		Reduce write amplification with multiple levels
		LSM-tree indexes
		LSM-tree queries
		Real-world LSM-tree: SSTable, MemTable and log
	2.6 Summary of indexing data structures
03. B-Tree & Crash Recovery
	3.1 B-tree as a balanced n-ary tree
		Height-balanced tree
		Generalizing binary trees
	3.2 B-tree as nest arrays
		Two-level nested arrays
		Multiple levels of nested arrays
	3.3 Maintaining a B+tree
		Growing a B-tree by splitting nodes
		Shrinking a B-tree by merging nodes
	3.4 B-Tree on disk
		Block-based allocation
		Copy-on-write B-tree for safe updates
		Copy-on-write B-tree advantages
		Alternative: In-place update with double-write
		The crash recovery principle
	3.5 What we learned
04. B+Tree Node and Insertion
	4.1 Design B+tree nodes
		What we will do
		The node format
		Simplifications and limits
		In-memory data types
		Decouple data structure from IO
	4.2 Decode the node format
		Header
		Child pointers
		KV offsets and pairs
		KV lookups within a node
	4.2 Update B+tree nodes
		Insert into leaf nodes
		Node copying functions
		Update internal nodes
	4.3 Split B+tree nodes
	4.4 B+tree insertion
	4.5 What’s next?
05. B+Tree Deletion and Testing
	5.1 High-level interfaces
		Keep the root node
		Sentinel value
	5.2 Merge nodes
		Node update functions
		Merge conditions
	5.3 B+tree deletion
	5.4 Test the B+tree
06. Append-Only KV Store
	6.1 What we will do
	6.2 Two-phase update
		Atomicity + durability
		Alternative: durability with a log
		Concurrency of in-memory data
	6.3 Database on a file
		The file layout
		`fsync` on directory
		`mmap`, page cache and IO
	6.4 Manage disk pages
		Invoke `mmap`
		`mmap` a growing file
		Capture page updates
	6.5 The meta page
		Read the meta page
		Update the meta page
	6.6 Error handling
		Scenarios after IO errors
		Revert to the previous version
		Recover from temporary write errors
	6.7 Summary of the append-only KV store
07. Free List: Recyle & Reuse
	7.1 Memory management techniques
		What we will do
		List of unused objects
		Embedded linked list
		External list
	7.2 Linked list on disk
		Free list requirements
		Free list disk layout
		Update free list nodes
	7.3 Free list implementation
		Free list interface
		Free list data structure
		Consuming from the free list
		Pushing into the free list
	7.4 KV with a free list
		Page management
		Update the meta page
	7.5 Conclusion of the KV store
08. Tables on KV
	8.1 Encode rows as KVs
		Indexed queries: point and range
		The primary key as the “key”
		The secondary indexes as separate tables
		Alternative: auto-generated row ID
	8.2 Databases schemas
		The table prefix
		Data types
		Records
		Schemas
		Internal tables
	8.3 Get, update, insert, delete, create
		Point query and update interfaces
		Query by primary key
		Read the schema
		Insert or update a row
		Create a table
	8.4 Conclusion of tables on KV
09. Range Queries
	9.1 B+tree iterator
		The iterator interface
		Navigate a tree
		Seek to a key
	9.2 Order-preserving encoding
		Sort arbitrary data as byte strings
		Numbers
		Strings
		Tuples
	9.3 Range query
	9.4 What we learned
10. Secondary Indexes
	10.1 Secondary indexes as extra keys
		Table schema
		KV structures
	10.2 Using secondary indexes
		Select an index by matching columns
		Encode missing columns as infinity
	10.3 Maintaining secondary indexes
		Sync with the primary data
		Atomicity of multi-key updates
	10.4 Summary of tables and indexes on KV
11. Atomic Transactions
	11.1 The all-or-nothing effect
		Commit and rollback
		Atomicity via copy-on-write
		Alternative: atomicity via logging
	11.2 Transactional interfaces
		Move tree operations to transactions
		Transactional table operations
	11.3 Optional optimizations
		Reduce copying on multi-key updates
		Range delete
		Compress common prefixes
12. Concurrency Control
	12.1 Levels of concurrency
		The problem: interleaved readers and writers
		Readers-writer lock (RWLock)
		Read-copy-update (RCU)
		Optimistic concurrency control
		Alternative: pessimistic concurrency control
		Comparison of concurrency controls
	12.2 Snapshot isolation for readers
		Capture local updates
		Read back your own write
		Version numbers in the free list
	12.3 Handle conflicts for writers
		Detect conflicts with history
		Serialize internal data structures
13. SQL Parser
	13.1 Syntax, parser, and interpreter
		Tree representation of computer languages
		Evaluate by visiting tree nodes
	13.2 Query language specification
		Statements
		Conditions
		Expressions
	13.3 Recursive descent
		Tree node structures
		Split the input into smaller parts
		Convert infix operators into a binary tree
		Operator precedence with recursion
14. Query Language
	14.1 Expression evaluation
	14.2 Range queries
		Set up a range query
		Revisit the infinity encoding
	14.3 Results iterator
		Iterators all the way down
		Transform data with iterators
	14.4 Conclusions and next steps