Build your own database from scratch

Description

Cover Contents 00. Introduction 0.1 What is This Book About? 0.2 How to Use This Book? 0.3 Topic One: Persistence 0.4 Topic Two: Indexing 0.5 Topic Three: Concurrency 01. Files vs Databases 1.1 Persisting Data to Files 1.2 Atomic Renaming 1.3 fsync 1.4 Append-Only Logs 02. Indexing 2.1 Key-Value Store and Relational DB 2.2 Hashtables 2.3 B-Trees 2.4 LSM-Trees 03. B-Tree: The Ideas 3.1 The Intuitions of the B-Tree and BST 3.2 B-tree and Nested Arrays 3.3 B-Tree Operations 3.4 Immutable Data Structures 04. B-Tree: The Practice (Part I) 4.1 The Node Format 4.2 Data Types 4.3 Decoding the B-tree Node 4.4 The B-Tree Insertion Step 1: Look Up the Key Step 2: Update Leaf Nodes Step 3: Recursive Insertion Step 4: Handle Internal Nodes Step 5: Split Big Nodes Step 6: Update Internal Nodes 05. B-Tree: The Practice (Part II) 5.1 The B-Tree Deletion Step 1: Delete From Leaf Nodes Step 2: Recursive Deletion Step 3: Handle Internal Nodes Step 4: The Conditions for Merging 5.2 The Root Node 5.3 Testing the B-Tree 5.4 Closing Remarks 06. Persist to Disk 6.1 The Method for Persisting Data 6.2 mmap-Based IO 6.3 The Master Page 6.4 Allocating Disk Pages 6.5 Initializing the Database 6.6 Update Operations 07. Free List: Reusing Pages 7.1 Design the Free List 7.2 The Free List Datatype 7.3 The Free List Implementation 7.4 Manage Disk Pages Step 1: Modify the Data Structure Step 2: Page Management for B-Tree Step 3: Page Management for the Free List Step 4: Update the Free List Step 5: Done 08. Rows and Columns 8.1 Introduction 8.2 Data Structures 8.3 Point Query 8.4 Updates 8.5 Create New Tables 09. Range Query 9.1 B-Tree Iterator 9.2 Data Serialization 9.3 Range Query 10. Secondary Index 10.1 Index Definitions 10.2 Maintaining Indexes 10.3 Using Secondary Indexes Step 1: Select an Index Step 2: Encode Index Prefix Step 3: Fetch Rows via Indexes Step 4: Put All Pieces Together Step 5: Congratulations 11. Atomic Transactions 11.1 KV Transaction Interfaces 11.2 DB Transaction Interfaces 11.3 Implementing the KV Transaction 12. Concurrent Readers and Writers 12.1 The Readers-Writer Problem 12.2 Analysing the Implementation 12.3 Concurrent Transactions Part 1: Modify the KV type Part 2: Add the Read-Only Transaction Type Part 3: Add the Read-Write Transaction Type 12.4 The Free List 12.5 Closing Remarks 13. Query Language: Parser 13.1 The Grammar 13.1.1 Statements 13.1.2 Conditions 13.1.3 Expressions 13.2 Operator Precedence and Recursion 13.3 Parsing Expressions 13.3.1 Parsing Keywords 13.3.2 Generalization 13.3.3 Parsing Names 13.4 Parsing Statements 14. Query Language: Execution 14.1 Introduction 14.2 Expression Evaluation 14.3 Fetching Rows 14.3.1 Initializing the Iterator 14.3.2 Iterating Rows 14.4 Executing Statements 14.5 Further Steps