2nd Edition. — Leanpub, 2024. — 103 p. — (From B+Tree To SQL).
Learn databases from the bottom up by coding your own, in small steps, and with simple Go code (language agnostic).
Database literature is full of confusing, overloaded jargon with no consistent meaning. It’s easy to get lost when reading about it. On the other hand, Feymann once said, “what I can’t build, I don’t understand”. Can you build a database by reading about databases? Test your understanding! While there is a lot to learn, not all knowledge is equally important, it takes only a few principles to build a DB, so anyone can try.
SQL is almost a synonym for database. But SQL is just a user interface, it’s not fundamental to a DB. What’s important is the functionalities underneath. Another much simpler interface is key-value (KV). You can get, set, and delete a single key, and most importantly, list a range of keys in sorted order. KV is simpler than SQL because it’s one layer lower. Relational DBs are built on top of KV-like interfaces called storage engines. Query languages: parsers and interpreters: The last step is easy, despite the larger LoC. Both the parser and the interpreter are coded with nothing but recursion! The lesson can be applied to almost any computer language, or creating your own programming language or DSL.
Atomicity & durability. A DB is more than files!
Persist data with fsync.
Crash recovery.
KV store based on B-tree.
Disk-based data structures.
Space management with a free list.
Relational DB on top of KV.
Learn how tables and indexes are related to B-trees.
SQL-like query language; parser & interpreter.
Concurrent transactions with copy-on-write data structures.
IntroductionFrom Files To Databases
Indexing Data Structures
B-Tree & Crash Recovery
B+Tree Node and Insertion
B+Tree Deletion and Testing
Append-Only KV Store
Free List: Recyle & Reuse
Tables on KV
Range Queries
Secondary Indexes
Atomic Transactions
Concurrency Control
SQL Parser
Query Language