Persistence, Indexing, Concurrency
James Smith
overblik
Databases are not black boxes. Understand them by coding your own from scratch!
A walkthrough of a minimal persistent database implementation. We start with a B-Tree, then add a new concept with each chapter, and eventually go from a simple KV to a mini relational DB.
Covers three important topics:
1. Persistence. How not to lose or corrupt your data. Recovering from a crash.
2. Indexing. Efficiently querying and manipulating your data. (B-tree).
3. Concurrency. How to handle multiple (large number of) clients. And transactions.
contents
Part I: Simple KV Store
(Self-contained, free-to-read web version.)
Introduction
Files vs Databases
Indexing
B-Tree: The Ideas
B-Tree: The Practice (Part I)
B-Tree: The Practice (Part II)
Persist to Disk
Free List: Reusing Pages
Part II: Mini Relational DB
(Included in the ebook and paperback editions.)
Rows and Columns
Range Query
Secondary Index
Atomic Transactions
Concurrent Readers and Writers
Query Language: Parser
Query Language: Execution