Building a Database Engine

The author shares his experience from 13 years of application development and concludes: databases survive any technology stack, and most developers know very little about them. This book aims to change that by offering a step-by-step guide to building your own database engine.

What you’ll learn

Data storage: from a naive CSV approach to an efficient TLV binary format.
Pre-write log (WAL): implementing fault tolerance.
Data pages: using 4KB pages with an LRU-based buffer to improve efficiency.
Indexes: building B-trees and hash indexes for fast searching.
Buffer pools: caching data pages using an LRU cache supported by a linked list and hash table.
Why Read

Overcome your fear of systems programming.
Understand fundamental database principles.
Develop skills that will set you apart from other developers.
Prepare for higher-level technical interviews.

Part I
Building a database engine is a 2-part e-book. Part I is 133 pages and contains these chapters:

01
Storage layer
From a naive CSV-based approach, through a fixed-size format, to a variable-length TLV-based storage system.

02
TLV implementation
An efficient storage format is the foundation of the entire database engine. In this chapter, we implement reusable TLV encoders and decoders with generics.

03
Column definitions
Before writing data to tables the engine needs to handle columns and column options such as `nullable`

04
Project structure
The project will follow package-oriented design. In this chapter, we establish the main packages.

05
Databases and tables
It’s time to create and store databases and tables on the disk. We’ll follow Postgres’ format. Each database is a folder, each table is a file.

06
Insert
Implementing insert which needs to encode a hash map to a TLV encoded record and store it in the table file.

07
Select
Implementing select. At this stage, it’s a full table scan. Meaning it reads and decodes the entire table file sequentially.

08
Delete
Implementing delete which works the same as MySQL‘s delete. Meaning it doesn’t actually delete the bytes. It only marks them as “deleted.” It’s more efficient.

09
Update
Implementing update which is a combination of delete and insert.

Part II
Building a database engine is a 2-part e-book. Part II is 163 pages and contains the following chapters. This is where the fun begins.

01
WAL
Adding Write-Ahead Log which will guarantee a certain degree of fault tolerance. Even if the engine fails while inserting, the data won’t be lost.

02
Data pages
Organizing each table into 4KB data pages. This is a crucial step to support B-Tree indexes. On top of that, it’s more efficient in lots of situations.

03
B-Tree indexes
In this chapter, we’re going to implement a B-Tree based primary index for tables. It will result in blazing fast lookups.

04
Buffer pool
Adding an LRU-based page-level cache backed by a linked list and a hash map. This will also increase the performance of SELECT queries.

05
Hash-based full-text indexes
Finally, another type of index. It is backed by a hash map instead of a B-Tree. We’ll use this to support some basic full-text search functionality.

Appendix
There’s a 98-page appendix that teaches you MySQL-related concepts

01
Database indexing
This massive 60-page chapter teaches everything about database indexing. Theory and practice are both included.

02
MySQL can do more than you think
This chapter includes the most interesting MySQL features that lots of developers don’t know about. Things like CTEs, windows functions, partitioning.

03
Query optimization 101
Discover the fastest and easiest tricks and tips you can apply to optimize your queries.

04
Understanding ACID
One of the most important properties of a relational database is ACID. Atomicity, consistency, isolation, durability.

Amazon Page

下载地址