From Bytes on Disk to Tables You Can Query
Every developer uses databases.
Whether you're building a small blog, a banking platform, an e-commerce store, or a distributed cloud service, sooner or later your application needs somewhere to store information.
We write SQL queries every day.
SELECT * FROM users;
INSERT INTO products (...);
UPDATE orders SET ...;
Most of the time, we stop there.
We trust PostgreSQL, MySQL, SQLite, or SQL Server to do the rest.
But have you ever wondered what actually happens after you press Enter?
How does a database know where your data lives?
How does it find rows without reading the entire file?
How does it survive power failures?
How does it store millions—even billions—of records efficiently?
When I first started backend development, I imagined databases as giant spreadsheets.
As I learned more, I realized they are closer to miniature operating systems.
They manage memory.
They schedule disk access.
They recover from crashes.
They optimize execution plans.
They maintain consistency while thousands of users access data simultaneously.
Building a database completely changed the way I think about software.
In this series, we'll build the foundations of our own SQL database in Rust.
Not because we're trying to replace PostgreSQL.
But because building one is one of the best ways to understand how modern software stores, retrieves, and protects information.
Let's begin with the most fundamental question.
Where does a database actually keep your data?
A Database Starts as a File
Many beginners imagine a database as something abstract living inside a server.
Reality is much simpler.
Every database ultimately stores information in files.
Application
│
▼
SQL Query
│
▼
Database Engine
│
▼
Database File
Whether you're using SQLite or PostgreSQL, the lowest layer eventually writes bytes to storage.
The database is simply responsible for organizing those bytes intelligently.
Thinking Beyond Tables
Applications show data as tables.
Users
+----+--------+
| ID | Name |
+----+--------+
| 1 | Derek |
| 2 | Alex |
+----+--------+
The disk never stores tables like this.
Instead, everything becomes binary.
01001001
00100111
11100001
...
Tables are abstractions.
The database translates between human-friendly structures and machine-friendly bytes.
Layers of a Database
A modern SQL database resembles a layered architecture.
SQL
│
▼
Query Engine
│
▼
Storage Engine
│
▼
File System
│
▼
SSD / HDD
Each layer has one responsibility.
That's good software engineering.
Designing Our Database
Our database will be called:
TinyDB
Project structure.
tinydb/
├── storage/
├── table/
├── page/
├── sql/
├── parser/
├── executor/
├── catalog/
├── buffer/
└── main.rs
Notice something interesting.
Large databases are simply well-organized software projects.
Representing a Row
Let's begin with one row.
Rust.
pub struct User {
pub id: u64,
pub name: String,
}
Simple.
Applications think in structures.
Storage engines think differently.
Serialization
Before writing data to disk, we must convert structures into bytes.
User
↓
Serialize
↓
Bytes
↓
Disk
The reverse process is called deserialization.
Example Serialization
Suppose we have:
User {
id: 1,
name: "Derek"
}
Serialized representation.
01 00 00 00
05
44 65 72 65 6B
The exact format is our choice.
That's one of the fascinating parts of building storage engines.
Storage Pages
Databases rarely read individual rows.
Instead they organize storage into pages.
Typically:
4096 Bytes
↓
One Page
Every read.
Every write.
Occurs page by page.
Why Pages?
Imagine a million users.
Reading one row at a time would be extremely inefficient.
Instead:
Disk
┌───────────┐
│ Page 1 │
├───────────┤
│ Page 2 │
├───────────┤
│ Page 3 │
└───────────┘
Pages minimize disk operations.
Designing a Page
Rust.
pub struct Page {
pub id: u32,
pub data: Vec<u8>,
}
Initially...
Just raw bytes.
Higher layers interpret them.
Table Storage
Suppose each page stores several rows.
Page
+-------------------------+
Row
Row
Row
Row
+-------------------------+
Eventually pages fill up.
The database allocates another.
Building the Storage Engine
Architecture.
Application
│
▼
Table
│
▼
Page Manager
│
▼
File Manager
│
▼
Disk
Each component solves one problem.
Writing Pages
Rust implementation.
use std::fs::File;
use std::io::Write;
fn write_page(
file: &mut File,
page: &Page,
) {
file.write_all(
&page.data
).unwrap();
}
Simple.
Yet this is the foundation of every database.
Reading Pages
Reading becomes equally straightforward.
use std::io::Read;
fn read_page(
file: &mut File,
page: &mut Page,
) {
file.read_exact(
&mut page.data
).unwrap();
}
Storage engines spend much of their lives performing operations like these.
Building a Table
Now we combine pages into tables.
Rust.
pub struct Table {
pub name: String,
pub pages:
Vec<Page>,
}
Eventually tables may contain thousands of pages.
Or millions.
Inserting Data
Suppose we execute:
INSERT INTO users
VALUES (1,'Derek');
Flow.
SQL
↓
Insert Command
↓
Serialize Row
↓
Find Free Page
↓
Write Bytes
↓
Commit
The SQL statement eventually becomes disk writes.
Reading Data
Now imagine:
SELECT *
FROM users;
Execution.
Read Page
↓
Deserialize Rows
↓
Return Results
Queries simply reverse the insertion process.
Catalog
How does the database know which tables exist?
Using a catalog.
Catalog
+-----------+
Users
Orders
Products
Invoices
+-----------+
Think of it as metadata describing the database itself.
Catalog Structure
Rust.
pub struct Catalog {
tables:
Vec<Table>,
}
Later this grows considerably.
Indexes.
Schemas.
Constraints.
Views.
Statistics.
Everything begins here.
Buffer Pool
Reading directly from disk every time would be painfully slow.
Instead databases cache pages.
Disk
↓
Buffer Pool
↓
Application
Recently used pages remain in memory.
Why Buffer Pools Matter
Suppose ten users request the same page.
Without caching.
Disk
↓
Disk
↓
Disk
↓
Disk
With caching.
Disk
↓
Memory
↓
Memory
↓
Memory
Much faster.
Simplified Buffer Manager
Rust.
use std::collections::HashMap;
pub struct BufferPool {
pages:
HashMap<u32, Page>,
}
Whenever possible:
Read from memory.
Otherwise:
Read from disk.
Database Flow
Putting everything together.
Application
↓
SQL
↓
Table Manager
↓
Buffer Pool
↓
Storage Engine
↓
Disk
Notice how SQL never interacts with files directly.
Every layer abstracts the one below it.
Complete Architecture
SQL Client
│
▼
Query Layer
│
▼
Table Manager
│
▼
Buffer Manager
│
┌────────────┼─────────────┐
▼ ▼ ▼
Page 1 Page 2 Page 3
│ │ │
└────────────┼─────────────┘
▼
Database File
│
▼
SSD / HDD
Even though our database is still small, the architecture already resembles production systems.
Implementation Summary
At this point, TinyDB supports the core storage concepts found in real databases:
- Rows represented as Rust structures.
- Serialization of rows into bytes.
- Fixed-size storage pages.
- Tables composed of multiple pages.
- A storage engine that reads and writes pages to disk.
- A simple catalog to track tables.
- A buffer pool that caches frequently accessed pages.
These pieces may appear simple, but they form the foundation of nearly every relational database.
Looking Ahead
So far, we've focused entirely on how data is stored.
But a database becomes truly useful when it understands SQL.
In Part 2, we'll build our own SQL engine from scratch.
We'll write a lexer to break SQL into tokens, build a parser that constructs an Abstract Syntax Tree (AST), implement a query planner, and create an execution engine capable of processing commands like:
CREATE TABLE users (...);
INSERT INTO users VALUES (...);
SELECT * FROM users WHERE id = 1;
We'll explore how databases transform human-readable SQL into executable operations, introduce table scans, filtering, and projections, and compare our design to the internal architecture of PostgreSQL and SQLite.
By the end of the next article, TinyDB won't just store data—it will understand and execute SQL.
Final Thoughts
One of the biggest surprises in building a database is realizing how much of it has nothing to do with SQL.
Before a parser, optimizer, or query planner can exist, the database must solve a far more fundamental problem: how to organize information on disk efficiently and reliably.
Everything starts with bytes.
Rows become serialized records.
Records are packed into pages.
Pages are written to files.
Files become tables.
Tables become databases.
Only then do higher-level abstractions like SQL begin to make sense.
That progression mirrors software engineering as a whole.
The most sophisticated systems are often built from remarkably simple layers, each solving one well-defined problem.
Understanding those layers gives you a deeper appreciation for every query you write.
The next time you execute SELECT * FROM users, you'll know that beneath those four words lies an intricate system of pages, buffers, storage engines, and carefully organized bytes working together to make data appear effortless.
And we're only just getting started.
Building Your Own SQL Database (Part 2)
Building a SQL Parser, Query Planner, and Execution Engine
In Part 1, we built the foundation of our database.
We learned that databases are not magical systems. At their core, they organize bytes on disk into pages, pages into tables, and tables into a storage engine capable of persisting information.
By the end of Part 1, our TinyDB architecture looked like this:
Application
│
▼
Table Manager
│
▼
Buffer Pool
│
▼
Storage Engine
│
▼
Database File
Our database could store information.
But there was one major problem.
Nobody wants to interact with raw pages or serialized bytes.
Developers speak SQL.
SELECT *
FROM users
WHERE id = 10;
The computer does not.
Computers understand instructions.
Somewhere between SQL and the storage engine, the database must translate human language into executable operations.
That's exactly what we're building today.
By the end of this article, TinyDB will understand SQL, build an Abstract Syntax Tree (AST), generate a query plan, and execute queries against our storage engine.
This is where our database begins to feel alive.
SQL Is Just Another Language
We often think of SQL as something special.
It isn't.
It's simply a programming language.
Like Rust.
Like Python.
Like JavaScript.
Every programming language follows the same pipeline.
Source Code
↓
Lexer
↓
Tokens
↓
Parser
↓
AST
↓
Execution
Databases follow exactly the same idea.
The Journey of a Query
Suppose the user writes:
SELECT name
FROM users
WHERE id = 5;
Internally our database performs:
SQL
↓
Lexer
↓
Tokens
↓
Parser
↓
AST
↓
Query Planner
↓
Execution Engine
↓
Storage Engine
↓
Results
Notice how SQL disappears very early.
Everything afterward operates on structured objects.
Step 1 — Lexical Analysis
The lexer breaks raw text into meaningful pieces.
Input:
SELECT name
FROM users;
Output:
SELECT
IDENTIFIER(name)
FROM
IDENTIFIER(users)
SEMICOLON
These pieces are called tokens.
Designing Tokens
Rust.
pub enum Token {
Select,
Insert,
Update,
Delete,
From,
Where,
Identifier(String),
Number(u64),
String(String),
Comma,
Semicolon,
}
Every SQL statement becomes a stream of these objects.
Example Lexer
Suppose our input is:
SELECT id FROM users;
The lexer produces:
+----------------+
SELECT
Identifier(id)
FROM
Identifier(users)
Semicolon
+----------------+
Simple.
Deterministic.
Fast.
Why Tokenization Matters
Imagine parsing SQL character by character.
S
E
L
E
C
T
Very difficult.
Instead we work with meaningful units.
SELECT
Much easier.
Parser
Now the parser transforms tokens into meaning.
Example.
SELECT
Identifier(name)
FROM
Identifier(users)
Becomes:
Select Query
├── Columns
│ name
└── Table
users
This structure is called an Abstract Syntax Tree.
Building the AST
Rust.
pub struct SelectStatement {
pub columns:
Vec<String>,
pub table: String,
}
Notice something important.
The SQL text disappears.
Only structure remains.
AST Visualization
SELECT
/ \
Columns Table
│ │
name users
This tree represents the query.
Every SQL database builds something similar.
Parsing SELECT
Pseudo-code.
parse_select()
↓
expect SELECT
↓
parse columns
↓
expect FROM
↓
parse table
↓
return AST
Every parser follows a predictable sequence.
Supporting WHERE
Now let's extend our AST.
SELECT *
FROM users
WHERE id = 7;
Rust.
pub struct Condition {
pub column: String,
pub value: Value,
}
Updated statement.
pub struct SelectStatement {
pub columns:
Vec<String>,
pub table: String,
pub condition:
Option<Condition>,
}
Our parser now understands filtering.
AST with WHERE
SELECT
├── Columns
│
├── Table
│
└── WHERE
│
id = 7
The AST captures meaning—not syntax.
Query Planning
Parsing tells us what the user wants.
Planning determines how to retrieve it.
Example.
SELECT *
FROM users;
Planner chooses:
Full Table Scan
Different query.
SELECT *
FROM users
WHERE id=5;
Planner may choose:
Index Scan
Different execution.
Same SQL language.
Query Plan
Our first planner is extremely simple.
SELECT
↓
Table Scan
↓
Filter
↓
Projection
↓
Results
Every database starts here.
Representing Plans
Rust.
pub enum Plan {
TableScan,
Filter,
Projection,
}
Later this grows into dozens of node types.
Table Scan
Suppose we have:
Users
1 Derek
2 Alex
3 Sarah
Table scan means:
Read Every Row
Simple.
Not always efficient.
Executing a Scan
Rust.
for row in table.rows() {
println!("{:?}", row);
}
That's literally a table scan.
Filtering Rows
Now suppose:
WHERE id = 2
Execution becomes:
Read Row
↓
Compare
↓
Keep?
↓
Yes
↓
Return
Rust.
if row.id == 2 {
result.push(row);
}
Projection
Users often request only specific columns.
SELECT name
Instead of:
ID
Name
Email
We return:
Name
Projection removes unnecessary data.
Execution Pipeline
Putting everything together.
Table
↓
Scan
↓
Filter
↓
Projection
↓
Results
Modern databases still follow this concept.
Example Execution
Suppose our table contains:
1 Derek
2 Alex
3 Sarah
Query.
SELECT name
FROM users
WHERE id = 2;
Execution.
Read Derek
↓
No
↓
Read Alex
↓
Yes
↓
Return Alex
↓
Read Sarah
↓
No
Supporting INSERT
INSERT follows another execution path.
INSERT INTO users
VALUES (4,'Mary');
Pipeline.
SQL
↓
Lexer
↓
Parser
↓
Insert AST
↓
Serialize Row
↓
Storage Engine
↓
Disk
Insert AST
Rust.
pub struct InsertStatement {
pub table: String,
pub values:
Vec<Value>,
}
Different SQL.
Different AST.
Same architecture.
Supporting CREATE TABLE
Example.
CREATE TABLE users (
id INT,
name TEXT
);
AST.
pub struct CreateTable {
pub name: String,
pub columns:
Vec<Column>,
}
The catalog eventually stores this information.
Complete SQL Pipeline
SQL
│
▼
Lexer
│
▼
Parser
│
▼
AST
│
▼
Query Planner
│
▼
Execution Engine
│
▼
Storage Engine
│
▼
Disk
Every layer has a single responsibility.
Why Query Planners Exist
Imagine two million users.
Query:
SELECT *
FROM users
WHERE id = 900;
Planner has choices.
Option 1
Table Scan
2 Million Rows
-----------------
Option 2
Index Lookup
1 Row
Same answer.
Massively different performance.
We'll build indexes in Part 3.
Current Architecture
SQL Client
│
▼
Lexer
│
▼
Parser
│
▼
AST
│
▼
Query Planner
│
▼
Execution Engine
│
┌───────────┼────────────┐
▼ ▼ ▼
Table Scan Filter Projection
│
▼
Storage Engine
│
▼
Database File
TinyDB is beginning to resemble a real relational database.
Comparing TinyDB to PostgreSQL
| Component | TinyDB | PostgreSQL |
|---|---|---|
| Lexer | ✅ | ✅ |
| Parser | ✅ | ✅ |
| AST | ✅ | ✅ |
| Query Planner | Basic | Cost-Based |
| Execution Engine | Basic | Volcano Executor |
| Storage Engine | Basic | Advanced |
| Optimizer | Planned | Sophisticated |
Although simplified, the architectural flow is remarkably similar.
What's Coming Next
TinyDB can now understand SQL and execute simple queries.
But performance is still terrible.
Every lookup scans the entire table.
If our database stores ten million users, finding one record means examining ten million rows.
Real databases don't work that way.
In Part 3, we'll solve this problem by building one of the most important data structures in computer science: the B-Tree.
We'll explore clustered and secondary indexes, implement efficient key lookups, introduce a buffer manager for intelligent caching, build a Write-Ahead Log (WAL) to survive crashes, and add transactions with Multi-Version Concurrency Control (MVCC).
By the end of the next article, TinyDB will begin behaving much more like PostgreSQL or MySQL, capable of handling fast queries while maintaining consistency and durability.
Final Thoughts
One of the biggest surprises in building a database is discovering that SQL is only a tiny part of the system.
The language itself is relatively simple.
The real engineering lies in everything that happens after the parser finishes its work.
A database reads text, transforms it into tokens, builds a structured representation, plans an efficient execution strategy, and finally coordinates with the storage engine to retrieve or modify data.
Those stages mirror the design of compilers, interpreters, and even operating systems.
Different domains.
The same architectural thinking.
Understanding this pipeline fundamentally changes how you write SQL.
A query stops being just a string.
It becomes a program that the database must parse, optimize, and execute.
And once you begin thinking that way, concepts like indexes, execution plans, and query optimization become far less mysterious.
Instead of seeing SQL as magic, you start seeing it for what it truly is: another elegant programming language executed by one of the most sophisticated pieces of software ever built.
Building Your Own SQL Database (Part 3)
Indexes, B-Trees, Transactions, and Making TinyDB Feel Like a Real Database
In Part 1, we built the foundation.
We learned that databases are ultimately machines that transform structured information into carefully organized bytes on disk.
We created:
- Pages
- Tables
- Serialization
- Storage engines
- Buffer pools
In Part 2, we gave our database a language.
TinyDB learned how to understand SQL.
We built:
- A lexer
- A parser
- An Abstract Syntax Tree
- A query planner
- An execution engine
Our architecture evolved into:
```text id="h5d7mq"
SQL
│
▼
Parser
│
▼
Query Planner
│
▼
Execution Engine
│
▼
Storage Engine
│
▼
Disk
But there is a major problem.
Our database is painfully slow.
Why?
Because we are searching like beginners.
---
# The Problem With Full Table Scans
Imagine we have one billion users.
Our table:
```text id="r2q5jz"
Users
1 Derek
2 Alex
3 Sarah
...
1000000000 John
Now execute:
SELECT *
FROM users
WHERE id = 999999999;
Our database currently does this:
```text id="f2m8qy"
Read Row 1
↓
Check
↓
Read Row 2
↓
Check
↓
Read Row 3
↓
Check
...
↓
Read Row 999999999
↓
Found
This is called a **full table scan**.
Complexity:
```plaintext
O(n)
The bigger the database becomes, the slower it gets.
Production databases cannot work this way.
They need indexes.
What Is an Index?
An index is a separate data structure designed to find information faster.
Think about a dictionary.
Without alphabetical ordering:
```text id="7m4z1p"
apple
zebra
computer
banana
network
Finding "computer" requires checking every word.
With an index:
```text id="n8s7vz"
A
B
C → computer
D
E
The search becomes much faster.
Databases use the same idea.
Database Index Architecture
Without an index:
```text id="f0kqxa"
Query
↓
Table
↓
Scan Every Row
↓
Result
With an index:
```text id="zq2m3h"
Query
↓
Index
↓
Find Location
↓
Read Row
↓
Result
The index acts like a roadmap.
Choosing the Right Data Structure
Many structures can create indexes:
- Hash tables
- Binary trees
- Skip lists
- B-Trees
- B+ Trees
Most relational databases rely heavily on B-Trees.
Why?
Because databases are not only searching memory.
They are searching disks.
Understanding B-Trees
A normal binary tree looks like:
```text id="7xq4kl"
50
/ \
25 75
/ \ / \
10 30 60 90
Each node has two children.
A B-Tree expands this idea.
Instead of two children:
A node can have hundreds.
```text id="m2e8k4"
[50|100|150]
/ | \
/ | \
many keys many keys many keys
This reduces the height of the tree.
Why B-Trees Are Perfect for Databases
Disk access is expensive.
Imagine:
```text id="u8b3s1"
Memory
↓
Fast
Disk
↓
Slow
A binary tree with one billion records might require many disk reads.
A B-Tree keeps the height small.
Example:
```plaintext
B-Tree height: 3
One lookup:
Root
↓
Child
↓
Leaf
Only a few disk operations.
Building Our B-Tree
Let's create a simplified version.
```rust id="w8j3fr"
pub struct BTreeNode {
pub keys: Vec<u64>,
pub children:
Vec<u64>,
pub leaf: bool,
}
Each node stores:
* Keys
* Child pointers
* Whether it is a leaf
---
# Example Index
Suppose we insert:
```plaintext
10
20
30
40
50
Our tree:
```text id="g2a9pm"
[30]
/ \
[10|20] [40|50]
Searching:
```plaintext
Find 40
↓
Compare with 30
↓
Go right
↓
Find 40
Much faster.
Index Lookup Flow
```text id="j5w0pk"
SELECT *
WHERE id = 50;
SQL
│
▼
Planner
│
▼
Index
│
▼
B-Tree Search
│
▼
Row Location
│
▼
Table
---
# Adding Indexes to TinyDB
Our table now becomes:
```text id="4q1q5n"
Table
┌──────────────┐
│ Rows │
└──────────────┘
Index
┌──────────────┐
│ B-Tree │
└──────────────┘
The index does not replace data.
It points to data.
Storing Row Locations
Instead of storing complete rows:
```text id="j8g6mb"
50 → Derek
We store:
```text id="c7v1zq"
50 → Page 15 Offset 200
Then:
Find location
↓
Read page
↓
Return row
Implementing Index Entries
Rust:
```rust id="w4d0kr"
pub struct IndexEntry {
pub key: u64,
pub page_id: u32,
pub offset: usize,
}
The index becomes a navigation system.
---
# The Need for Transactions
Indexes solve searching.
But databases have another massive problem:
Multiple users changing data at the same time.
Imagine:
User A:
```sql
UPDATE accounts
SET balance=500;
User B:
UPDATE accounts
SET balance=700;
Who wins?
The Lost Update Problem
Timeline:
```text id="z7j1qm"
User A
Reads balance = 100
User B
Reads balance = 100
User A
Writes 500
User B
Writes 700
Final result:
```plaintext
700
User A's update disappeared.
This is a concurrency problem.
Introducing Transactions
A transaction groups operations into one logical unit.
Example:
BEGIN;
UPDATE accounts
SET balance = balance - 100;
COMMIT;
A transaction provides:
- Atomicity
- Consistency
- Isolation
- Durability
The famous ACID properties.
Transaction Lifecycle
```text id="k2x8pq"
BEGIN
|
|
Perform Operations
|
|
COMMIT
Or:
```text id="m4v2zd"
BEGIN
|
|
Error
|
|
ROLLBACK
Transaction Manager
We add:
```rust id="p1q6lm"
pub struct Transaction {
pub id: u64,
pub state: State,
}
The database tracks active operations.
---
# Write-Ahead Logging (WAL)
What happens if the computer crashes?
Imagine:
```plaintext
Update balance
↓
Write to memory
↓
Power failure
The change disappears.
Databases solve this using WAL.
The WAL Principle
Before changing the database:
Write the intention to a log.
```text id="y9p4nv"
Transaction:
Change user 5 balance
Before:
1000
After:
900
Then:
```plaintext
Write log
↓
Modify database
WAL Architecture
```text id="a7x2qm"
Application
|
▼
Transaction
|
▼
Write Ahead Log
|
▼
Database Pages
The log is the source of truth during recovery.
---
# WAL Implementation
A simple log entry:
```rust id="s8x9jk"
pub struct LogEntry {
pub transaction_id: u64,
pub page_id: u32,
pub before:
Vec<u8>,
pub after:
Vec<u8>,
}
Crash Recovery
Imagine:
```text id="c4q9hz"
Transaction starts
↓
Write WAL
↓
Update page
↓
Crash
On restart:
Database reads WAL:
```text id="f9v6kx"
Find unfinished transaction
↓
Redo changes
or
Undo changes
The database repairs itself.
Buffer Management Becomes More Important
Now we have:
- Tables
- Pages
- Indexes
- Transactions
Memory becomes critical.
Our buffer pool now manages:
```text id="r7n2wm"
Buffer Pool
+--------------------------+
| Page 1 |
| Page 2 |
| Page 3 |
| Page 4 |
+--------------------------+
When memory is full:
Which page leaves?
---
# LRU Cache
Most databases use variations of:
Least Recently Used.
Idea:
Remove pages nobody is using.
Example:
```text id="v5b8df"
Recently Used
↓
Page A
Page B
Page C
↓
Old
Page D
Page D gets removed.
Updated TinyDB Architecture
Our database has grown.
```text id="r8x2kp"
SQL
|
▼
Query Engine
|
▼
Query Planner
|
┌───────────┴───────────┐
▼ ▼
Table Scan Index Scan
| |
└───────────┬───────────┘
▼
Transaction Layer
|
▼
Buffer Pool
|
┌───────────┴───────────┐
▼ ▼
WAL Storage Engine
|
▼
Disk
This is now starting to resemble a real database.
---
# What We Have Built
TinyDB now supports:
✅ Persistent storage
✅ Pages
✅ Tables
✅ SQL parsing
✅ Query execution
✅ B-Tree indexes
✅ Faster lookups
✅ Transactions
✅ WAL logging
✅ Crash recovery foundation
The system has evolved from a file writer into a real database engine.
---
# What Comes Next
There is still one major challenge.
Concurrency.
Right now, transactions exist, but they are still limited.
What happens when:
* Thousands of users read simultaneously?
* Multiple transactions update the same rows?
* Long-running queries overlap?
* Data changes while another transaction is reading?
Real databases solve this with **MVCC — Multi-Version Concurrency Control**.
In Part 4, we will build:
* Row versions
* Snapshots
* Isolation levels
* Garbage collection
* Concurrent reads and writes
* A PostgreSQL-style MVCC system
This is where TinyDB becomes truly powerful.
---
# Final Thoughts
Building indexes and transactions changed the way I think about databases.
A database is not simply a place where data lives.
It is an intelligent system constantly balancing competing goals:
* Speed
* Safety
* Consistency
* Reliability
* Scalability
An index sacrifices storage space to gain speed.
A transaction sacrifices simplicity to gain correctness.
A WAL sacrifices extra writes to gain durability.
Every database feature is a carefully engineered trade-off.
The beauty of database engineering is that there is rarely a perfect solution.
There are only intelligent compromises.
And understanding those compromises is what separates someone who uses databases from someone who can design them.
# Building Your Own SQL Database (Part 4)
## MVCC, Isolation, and Making TinyDB a Truly Concurrent Database
In the previous parts, we transformed TinyDB from a simple file storage system into a small relational database engine.
We started with bytes.
Then we built:
* Storage pages
* Tables
* Serialization
* Buffer pools
* SQL parsing
* Query execution
* Query planning
* B-Tree indexes
* Transactions
* Write-Ahead Logging
Our architecture now looks like this:
```text
SQL
│
▼
Query Engine
│
▼
Query Planner
│
┌───────────────┴────────────────┐
▼ ▼
Index Scan Table Scan
│ │
└───────────────┬────────────────┘
▼
Transaction Manager
│
▼
Buffer Pool
│
┌───────────┴───────────┐
▼ ▼
WAL Storage Engine
│
▼
Disk
But there is still a fundamental problem.
Our database works.
It stores data.
It executes queries.
It survives crashes.
But it struggles with something every modern database must handle:
Thousands of users doing things at the same time.
Imagine an online banking system.
One user checks their balance.
Another user transfers money.
A third user receives a payment.
All at the same time.
How does the database make sure everyone sees correct information?
This is where one of the most beautiful ideas in database engineering appears.
Multi-Version Concurrency Control.
MVCC.
The Concurrency Problem
Let's imagine a simple table.
Accounts
+----+---------+
| ID | Balance |
+----+---------+
| 1 | 1000 |
+----+---------+
Two transactions start.
Transaction A:
UPDATE accounts
SET balance = 900
WHERE id = 1;
Transaction B:
SELECT balance
FROM accounts
WHERE id = 1;
What should B see?
1000?
900?
Something else?
The database needs rules.
The Old Solution: Locks
The traditional approach is locking.
Transaction A locks the row.
Transaction A
│
▼
Lock Row
│
▼
Update Data
│
▼
Unlock
Transaction B waits.
Transaction B
│
▼
Waiting...
│
▼
Read Data
This works.
But it creates problems.
Why Locks Become Difficult
Imagine thousands of users.
User 1 ─┐
User 2 ─┤
User 3 ─┤── Waiting
User 4 ─┤
User 5 ─┘
The database becomes a traffic jam.
Readers block readers.
Readers block writers.
Writers block readers.
The system spends more time coordinating than working.
The MVCC Idea
MVCC takes a completely different approach.
Instead of changing data:
Create a new version.
Old data stays.
New data appears.
Example:
Before:
Account
Balance = 1000
After update:
Version 1
Balance = 1000
Version 2
Balance = 900
Both versions exist.
The database decides which one each transaction can see.
Data Becomes a Timeline
Traditional thinking:
Row = Current Value
MVCC thinking:
Row = History of Values
Example:
Time
────────────────────────────►
Version 1
Balance = 1000
Update
Version 2
Balance = 900
The database becomes aware of time.
Adding Versions to Rows
Previously our row looked like:
pub struct Row {
pub id: u64,
pub data: Vec<u8>,
}
Now:
pub struct VersionedRow {
pub id: u64,
pub data: Vec<u8>,
pub created_tx: u64,
pub deleted_tx: Option<u64>,
}
Every row knows:
- When it appeared
- When it disappeared
Transaction IDs
Every transaction receives an identifier.
Example:
Transaction 1
Transaction 2
Transaction 3
Transaction 4
Rust:
pub struct Transaction {
pub id: u64,
}
These IDs allow the database to understand history.
Creating a Snapshot
When a transaction begins:
BEGIN TRANSACTION
│
▼
Create Snapshot
│
▼
Execute Queries
The snapshot defines what data is visible.
Example Snapshot
Database:
Version 1
Name = Derek
Created = 1
Version 2
Name = Alex
Created = 5
Transaction 3 starts.
It sees:
Derek
Transaction 6 starts.
It sees:
Alex
Same database.
Different realities.
Visibility Rules
A version is visible if:
created_tx <= transaction_id
and:
deleted_tx > transaction_id
or:
deleted_tx does not exist
In simple terms:
"The row existed during this transaction."
Implementing Visibility
Rust:
impl VersionedRow {
pub fn visible(
&self,
tx_id: u64
) -> bool {
if self.created_tx > tx_id {
return false;
}
match self.deleted_tx {
Some(delete_id) => {
tx_id < delete_id
}
None => true,
}
}
}
This tiny function is the heart of MVCC.
Updating Data in MVCC
Traditional database:
Modify existing row
MVCC:
Create new version
Example:
Before:
ID
1
Name
Derek
Update:
UPDATE users
SET name='Alex';
After:
Version 1
Derek
Created: 1
Deleted: 8
Version 2
Alex
Created: 8
Deleted: NULL
Nothing was overwritten.
Delete Operations
Deletion works the same way.
Traditional:
Remove row
MVCC:
Mark version invisible
Example:
Before:
User
Derek
After:
User
Derek
Deleted Transaction = 10
Old transactions can still see Derek.
New transactions cannot.
Reading With MVCC
A query:
SELECT *
FROM users;
becomes:
Read all versions
│
▼
Check visibility
│
▼
Return visible versions
Implementation:
rows
.iter()
.filter(
|row|
row.visible(transaction.id)
)
Handling Multiple Writers
Now imagine:
Transaction A:
Creates Version 5
Transaction B:
Creates Version 6
Both changes exist.
The database later decides whether conflicts exist.
Isolation Levels
Databases offer different levels of isolation.
The most common:
Read Uncommitted
You can see changes before they are committed.
Fast.
Dangerous.
Read Committed
Only committed data is visible.
Most common default.
Repeatable Read
A transaction sees the same data throughout its lifetime.
Serializable
Transactions behave as if executed one by one.
Safest.
Slowest.
Adding Isolation to TinyDB
Transaction state:
pub enum IsolationLevel {
ReadCommitted,
RepeatableRead,
Serializable,
}
The visibility engine changes behavior depending on this choice.
MVCC Storage Layout
Our storage engine changes.
Before:
Page
├── Row
├── Row
└── Row
After:
Page
├── Row Version
│ └── Previous Version
├── Row Version
│ └── Previous Version
History becomes part of storage.
Version Chains
Many databases organize versions as chains.
Example:
Newest
│
▼
Version 3
│
▼
Version 2
│
▼
Version 1
The database walks backward until it finds a visible version.
Garbage Collection
A problem appears.
If every update creates a new version forever:
Derek
↓
Alex
↓
John
↓
Mary
↓
...
Storage grows endlessly.
We need cleanup.
Vacuuming
Databases periodically remove old versions.
Example:
Version 1
No transaction needs it
│
▼
Delete
PostgreSQL calls this:
VACUUM
Implementing Simple Cleanup
We track active transactions.
pub struct TransactionManager {
active:
Vec<u64>,
}
Find the oldest active transaction:
Oldest Active = 50
Any version deleted before 50 can disappear.
The Complete Database Architecture
TinyDB is now a real database engine.
SQL
│
▼
SQL Parser
│
▼
Query Optimizer
│
▼
Execution Engine
│
▼
Transaction Manager
│
┌───────────┴───────────┐
▼ ▼
MVCC WAL
│ │
└───────────┬───────────┘
▼
Buffer Pool
│
▼
Storage Engine
│
▼
Disk
What We Have Built
After four parts, TinyDB contains the fundamental ideas behind modern relational databases:
Storage
✓ Pages
✓ Serialization
✓ Tables
✓ Disk persistence
Query Processing
✓ SQL lexer
✓ Parser
✓ AST
✓ Query planner
✓ Execution engine
Performance
✓ Buffer pool
✓ B-Tree indexes
✓ Efficient lookups
Reliability
✓ Transactions
✓ WAL logging
✓ Crash recovery
Concurrency
✓ MVCC
✓ Snapshots
✓ Isolation levels
✓ Version cleanup
Comparing TinyDB With Real Databases
| Feature | TinyDB | PostgreSQL |
|---|---|---|
| SQL Parser | Basic | Advanced |
| Storage Engine | Simple | Highly optimized |
| Indexes | B-Tree | Multiple types |
| Transactions | Yes | Yes |
| WAL | Basic | Advanced |
| MVCC | Basic | Advanced |
| Query Optimizer | Simple | Cost-based |
| Replication | No | Yes |
The difference is not the fundamental ideas.
The difference is years of optimization.
Lessons From Building a Database
Building TinyDB taught me something important.
The hardest part of software engineering is rarely writing code.
The hardest part is managing complexity.
A database solves hundreds of difficult problems:
- How do we store information?
- How do we find it quickly?
- How do we survive failures?
- How do we support thousands of users?
- How do we prevent corruption?
The answer is not one giant algorithm.
It is thousands of small engineering decisions working together.
Final Thoughts
A database is not just a storage system.
It is a carefully designed machine for managing reality.
It remembers the past through MVCC.
It protects the future through transactions.
It accelerates the present through indexes and caching.
Every SQL query is the result of decades of engineering research hidden behind a few simple words.
When you write:
SELECT * FROM users;
you are not just reading data.
You are interacting with:
- A parser
- A planner
- An optimizer
- A transaction system
- A concurrency engine
- A storage engine
Building your own database reveals the hidden world underneath everyday software.
And perhaps the biggest lesson is this:
Great systems are not built by making things complicated.
They are built by taking complicated problems and organizing them into simple, understandable layers.
Top comments (0)