Have you ever wondered what actually happens when you run a SQL query like:
SELECT name FROM users WHERE id = 10;
Where is the data stored?
How does the database find the correct row?
How are tables represented on disk?
How does the database survive after the program exits?
And how does a database engine turn SQL into operations on bytes, pages, indexes, and files?
Instead of only using a database, let's build a small SQLite-like database engine from scratch in C.
We won't try to recreate all of SQLite. That would be an enormous project. Instead, we'll build a small educational database engine that teaches the fundamental architecture behind relational databases.
By the end, we'll understand how the pieces fit together:
SQL Query
│
▼
┌─────────────┐
│ SQL Parser │
└──────┬──────┘
│
▼
┌─────────────┐
│ Query Plan │
└──────┬──────┘
│
▼
┌─────────────┐
│ Executor │
└──────┬──────┘
│
▼
┌─────────────┐
│ B-Tree │
└──────┬──────┘
│
▼
┌─────────────┐
│ Buffer Pool │
└──────┬──────┘
│
▼
┌─────────────┐
│ Disk / File │
└─────────────┘
Let's build it step by step.
1. What Are We Actually Building?
Our goal is a small database executable:
$ ./mydb database.db
Then we can interact with it:
db > CREATE TABLE users;
db > INSERT INTO users VALUES (1, "Farhad");
db > INSERT INTO users VALUES (2, "Ali");
db > SELECT * FROM users;
And eventually:
1 | Farhad
2 | Ali
The important part is that the data should remain after the program exits.
If we run:
$ ./mydb database.db
again, the database should still contain:
1 | Farhad
2 | Ali
That means we need persistent storage.
2. Why C?
C is an excellent language for learning how databases work internally because it gives us direct control over:
- memory
- pointers
- structs
- files
- byte arrays
- serialization
- memory allocation
- system calls
- data structures
A database engine ultimately deals with a lot of low-level concepts.
For example, a database page might simply be:
unsigned char page[4096];
Those 4096 bytes could contain:
+----------------------------------+
| Page Header |
+----------------------------------+
| Slot Array |
+----------------------------------+
| |
| Records |
| |
+----------------------------------+
| Free Space |
+----------------------------------+
At this level, there is no magic.
It's bytes.
Our job is to give those bytes meaning.
3. The Architecture
Before writing code, we need an architecture.
A simplified database can be divided into several layers:
┌───────────────────────────────┐
│ SQL Layer │
│ Lexer / Parser / Statements │
├───────────────────────────────┤
│ Query Executor │
├───────────────────────────────┤
│ Access Methods │
│ Table / B-Tree │
├───────────────────────────────┤
│ Buffer Pool │
├───────────────────────────────┤
│ Page Cache │
├───────────────────────────────┤
│ Storage Manager │
├───────────────────────────────┤
│ Database File │
└───────────────────────────────┘
We'll implement these components incrementally.
4. Step 1 — The Database File
The simplest database can start as a normal file.
For example:
database.db
We can open it with:
FILE *file = fopen("database.db", "r+b");
Or create it if it doesn't exist:
FILE *file = fopen("database.db", "w+b");
But simply writing random structures into a file isn't enough.
We need a storage format.
5. Step 2 — Pages
Databases generally don't treat the disk as one giant byte array.
Instead, we divide the database file into fixed-size pages.
For our educational database:
#define PAGE_SIZE 4096
A database file might look like:
database.db
┌──────────────┐
│ Page 0 │
│ 4096 bytes │
├──────────────┤
│ Page 1 │
│ 4096 bytes │
├──────────────┤
│ Page 2 │
│ 4096 bytes │
├──────────────┤
│ Page 3 │
│ 4096 bytes │
├──────────────┤
│ ... │
└──────────────┘
If the database has 100 pages:
100 × 4096 = 409,600 bytes
A page gives us a fixed unit for storage and caching.
6. Why Pages?
Suppose we need record number 500.
We don't want to read the entire database file.
Instead, we determine which page contains the record:
record
│
▼
page number
│
▼
database file offset
The offset is:
offset = page_number * PAGE_SIZE;
For example:
page = 10
offset = 10 × 4096
= 40960
So page 10 begins at byte 40960.
7. Step 3 — The Pager
Now we create one of the most important components:
the pager.
The pager is responsible for moving pages between the database file and memory.
Conceptually:
RAM
┌──────────────┐
│ Page 0 │
│ Page 4 │
│ Page 7 │
└───────┬──────┘
│
│
┌────▼────┐
│ Pager │
└────┬────┘
│
▼
┌──────────────┐
│ database.db │
└──────────────┘
A basic pager structure might look like:
#define TABLE_MAX_PAGES 100
typedef struct {
int file_descriptor;
uint32_t file_length;
void *pages[TABLE_MAX_PAGES];
} Pager;
The pages array stores pointers to pages currently loaded in memory.
8. Loading a Page
Suppose we request page 5.
The pager checks:
if (pager->pages[5] == NULL)
If it isn't loaded, allocate memory:
pager->pages[5] = malloc(PAGE_SIZE);
Then read the page from disk.
Conceptually:
database.db
│
│ read page 5
▼
┌─────────────┐
│ Page 5 │
└─────────────┘
│
▼
RAM
This is the beginning of a buffer pool/cache.
9. Step 4 — Rows
Now we need to decide how a table row is represented.
For a simple database, let's define:
typedef struct {
uint32_t id;
char username[32];
char email[64];
} Row;
A row might contain:
id = 1
username = "Farhad"
email = "farhad@example.com"
But we cannot simply assume that a C struct's memory layout is our database format.
We should explicitly serialize the row.
10. Serialization
Serialization means converting a C structure into bytes.
For example:
C structure
Row
┌───────────────┐
│ id │
├───────────────┤
│ username │
├───────────────┤
│ email │
└───────────────┘
│
▼
serialize
│
▼
Bytes on disk
We can write:
void serialize_row(Row *source, void *destination)
{
memcpy(destination, &source->id, sizeof(source->id));
memcpy(destination + 4,
source->username,
sizeof(source->username));
memcpy(destination + 36,
source->email,
sizeof(source->email));
}
And later deserialize it.
This is important because the database file needs a well-defined format.
11. Step 5 — The Table
Now we can store rows inside pages.
Initially, we could use a very simple layout:
Page
┌──────────────────────────────┐
│ Row 0 │
├──────────────────────────────┤
│ Row 1 │
├──────────────────────────────┤
│ Row 2 │
├──────────────────────────────┤
│ Row 3 │
├──────────────────────────────┤
│ ... │
└──────────────────────────────┘
For example:
#define ROW_SIZE 100
#define ROWS_PER_PAGE \
(PAGE_SIZE / ROW_SIZE)
Then:
page_number = row_number / ROWS_PER_PAGE;
row_offset = row_number % ROWS_PER_PAGE;
This gives us a simple way to locate rows.
12. Step 6 — The REPL
Now let's create an interface.
A REPL means:
Read → Evaluate → Print → Loop
Our program could display:
db >
The user enters:
db > insert 1 Farhad
Our program reads the input:
char input[1024];
while (1) {
printf("db > ");
if (!fgets(input, sizeof(input), stdin))
break;
// process input
}
At first, don't implement SQL.
Start with commands like:
insert
select
.exit
This makes development much easier.
13. Step 7 — INSERT
Suppose the user enters:
insert 1 Farhad
The database needs to:
Input
│
▼
Parse command
│
▼
Create Row
│
▼
Serialize Row
│
▼
Find page
│
▼
Write Row
│
▼
Mark page dirty
Conceptually:
Row row;
row.id = 1;
strcpy(row.username, "Farhad");
execute_insert(&row);
14. Step 8 — SELECT
Now:
select
should read all rows.
The executor might:
for each page
load page
for each row
deserialize row
print row
Conceptually:
database
│
▼
Page 0
│
├── Row 0
├── Row 1
└── Row 2
Page 1
│
├── Row 3
├── Row 4
└── Row 5
This is essentially a table scan.
15. Step 9 — From Commands to SQL
Once the storage engine works, we can start implementing SQL.
Instead of:
insert 1 Farhad
we want:
INSERT INTO users VALUES (1, 'Farhad');
And:
SELECT * FROM users;
Now we need a lexer and parser.
16. The SQL Lexer
The lexer converts characters into tokens.
For:
SELECT * FROM users;
we might produce:
SELECT
ASTERISK
FROM
IDENTIFIER(users)
SEMICOLON
The input:
SELECT * FROM users;
becomes:
┌────────┐
│ SELECT │
├────────┤
│ * │
├────────┤
│ FROM │
├────────┤
│ users │
├────────┤
│ ; │
└────────┘
17. The Parser
The parser takes those tokens and builds a representation of the query.
For example:
SELECT * FROM users;
could become:
SelectStatement
├── columns: *
└── table: users
For:
INSERT INTO users VALUES (1, 'Farhad');
we could create:
InsertStatement
├── table: users
└── values
├── 1
└── Farhad
18. Step 10 — The Query Executor
The parser tells us what the user wants.
The executor determines how to perform it.
For example:
SELECT * FROM users;
might become:
Parser
│
▼
SELECT statement
│
▼
Executor
│
▼
Table scan
│
▼
Read pages
│
▼
Read rows
│
▼
Return results
This separation is extremely important.
19. Step 11 — Slotted Pages
Our first page layout was very simple.
A real database needs a more flexible structure.
This is where slotted pages become useful.
A page might look like:
┌─────────────────────────────┐
│ Page Header │
├─────────────────────────────┤
│ Slot 0 │
├─────────────────────────────┤
│ Slot 1 │
├─────────────────────────────┤
│ Slot 2 │
├─────────────────────────────┤
│ │
│ Free Space │
│ │
├─────────────────────────────┤
│ Record 2 │
├─────────────────────────────┤
│ Record 1 │
├─────────────────────────────┤
│ Record 0 │
└─────────────────────────────┘
The slot array tells us where records are located.
This allows records to have variable sizes and move around within a page without changing their logical identifiers.
20. Step 12 — Record IDs
Instead of identifying a record simply by its memory address, we can use a logical identifier.
For example:
RID
├── page_id
└── slot_id
So:
RID = (12, 4)
means:
Page 12
Slot 4
This gives us a stable way to refer to records.
21. Step 13 — Free Space Management
Eventually pages become full.
We need to know:
Which pages have free space?
A simple free-space map could track this:
Page 0 → full
Page 1 → 1200 bytes free
Page 2 → full
Page 3 → 3000 bytes free
When inserting a record, the storage manager searches for a page with enough free space.
This is one of the fundamental responsibilities of a storage engine.
22. Step 14 — B-Tree Indexes
A table scan works:
SELECT * FROM users WHERE id = 1000000;
But it can be very slow.
If there are one million rows, scanning every row is expensive.
We need an index.
A common database index structure is a B-tree or B+ tree.
Conceptually:
[50]
/ \
/ \
[10,20,30] [60,70,80]
The index lets us navigate toward the desired key instead of scanning every row.
For:
WHERE id = 70
we navigate:
[50]
\
▼
[60,70,80]
│
▼
row 70
23. Why B-Trees?
B-trees are particularly useful for storage systems because they reduce the number of disk/page accesses required to locate records.
Instead of:
Page 0
Page 1
Page 2
Page 3
...
Page 1,000,000
we can navigate through a tree:
Root
│
┌──────┴──────┐
▼ ▼
Internal Internal
│ │
▼ ▼
Leaves Leaves
│
▼
Record
The database doesn't have to inspect every row.
24. Step 15 — Buffer Pool
Disk is much slower than RAM.
Therefore, databases keep frequently used pages in memory.
A buffer pool might look like:
RAM
┌───────────────┐
│ Frame 0 │ → Page 17
├───────────────┤
│ Frame 1 │ → Page 4
├───────────────┤
│ Frame 2 │ → Page 31
├───────────────┤
│ Frame 3 │ → Page 9
└───────────────┘
When the database requests page 17:
Request Page 17
│
▼
Is it in buffer?
│
┌──┴──┐
yes no
│ │
▼ ▼
return read disk
│
▼
buffer
This dramatically reduces disk I/O.
25. Dirty Pages
Suppose we load a page:
Disk → RAM
Then modify it:
RAM
Page 5
│
└── modified
The page is now dirty.
Eventually we need:
RAM → Disk
So a buffer frame might have:
typedef struct {
void *data;
uint32_t page_id;
int dirty;
} Frame;
If:
frame->dirty = 1;
we know the page must eventually be written back.
26. Step 16 — Transactions
Now we reach a much more serious database feature.
What happens if the program crashes halfway through a write?
For example:
Transaction:
1. Update row A
2. Update row B
3. Program crashes
We don't want the database to end up in an inconsistent state.
Transactions provide atomicity.
Conceptually:
BEGIN
│
├── operation 1
├── operation 2
├── operation 3
│
COMMIT
Or:
BEGIN
│
├── operation 1
├── operation 2
│
ROLLBACK
27. Step 17 — Write-Ahead Logging
A common technique is Write-Ahead Logging (WAL).
Before modifying the actual database page, record the change in a log.
Transaction
│
▼
Write Log
│
▼
Modify Page
│
▼
Commit
If the database crashes, the log can be used during recovery.
This is one of the major steps from a toy database toward a real database engine.
28. Step 18 — Database Catalog
Once we support multiple tables, the database needs metadata.
For example:
CREATE TABLE users (...);
CREATE TABLE products (...);
The database needs to know:
users
├── columns
├── types
└── root page
products
├── columns
├── types
└── root page
This metadata is often called the system catalog.
Our catalog could contain information such as:
Table name
Column name
Column type
Column position
Index information
Root page
29. Step 19 — Data Types
Eventually our SQL engine should understand:
INTEGER
TEXT
REAL
BOOLEAN
For example:
CREATE TABLE users (
id INTEGER,
name TEXT,
age INTEGER
);
Internally, a row might be serialized as:
┌──────────┬────────────┬──────────┐
│ id │ name │ age │
│ INTEGER │ TEXT │ INTEGER │
└──────────┴────────────┴──────────┘
The serialization layer needs to understand each type.
30. Step 20 — Query Execution
Eventually we want queries such as:
SELECT name
FROM users
WHERE age > 18;
The execution pipeline becomes:
SQL
│
▼
Lexer
│
▼
Parser
│
▼
AST
│
▼
Query Planner
│
▼
Execution Plan
│
▼
Executor
│
▼
Index / Table Scan
│
▼
Pages
│
▼
Rows
│
▼
Result
This is where our database starts becoming a real database engine rather than a file-based storage program.
31. A Practical Development Roadmap
Don't try to build everything at once.
Build the database in stages.
Stage 1 — File Storage
Implement:
database file
page size
read page
write page
Stage 2 — Pager
Implement:
Pager
page cache
page loading
page flushing
Stage 3 — Rows
Implement:
Row
serialize
deserialize
Stage 4 — Table
Implement:
insert
select
table scan
Stage 5 — REPL
Implement:
db >
with commands such as:
.insert
.select
.exit
Stage 6 — SQL Lexer
Implement tokens:
SELECT
INSERT
CREATE
FROM
WHERE
INTEGER
TEXT
IDENTIFIER
NUMBER
STRING
Stage 7 — SQL Parser
Build an AST for SQL statements.
Stage 8 — Slotted Pages
Implement:
page header
slot directory
records
free space
Stage 9 — B-Tree
Implement:
leaf nodes
internal nodes
search
insert
split
Stage 10 — Catalog
Implement:
tables
columns
types
indexes
Stage 11 — Query Execution
Implement:
table scan
index scan
filter
projection
Stage 12 — Transactions
Implement:
BEGIN
COMMIT
ROLLBACK
Stage 13 — WAL and Recovery
Implement:
log
checkpoint
recovery
Stage 14 — Concurrency
Eventually:
locks
latches
transactions
isolation
32. Suggested Project Structure
A clean project might eventually look like:
mydb/
│
├── src/
│ ├── main.c
│ ├── repl.c
│ ├── lexer.c
│ ├── parser.c
│ ├── executor.c
│ ├── catalog.c
│ ├── table.c
│ ├── row.c
│ ├── page.c
│ ├── pager.c
│ ├── buffer_pool.c
│ ├── btree.c
│ ├── transaction.c
│ ├── wal.c
│ └── recovery.c
│
├── include/
│ ├── repl.h
│ ├── lexer.h
│ ├── parser.h
│ ├── executor.h
│ ├── catalog.h
│ ├── table.h
│ ├── row.h
│ ├── page.h
│ ├── pager.h
│ ├── buffer_pool.h
│ ├── btree.h
│ ├── transaction.h
│ ├── wal.h
│ └── recovery.h
│
├── tests/
│ ├── test_pager.c
│ ├── test_page.c
│ ├── test_btree.c
│ └── test_sql.c
│
├── Makefile
└── database.db
You don't need all of these files on day one.
Start small and grow the architecture as the database becomes more capable.
33. The Most Important Concept
The biggest lesson from building a database from scratch is this:
A database is not just SQL.
SQL is only the interface.
Underneath SQL are many layers:
SQL
↓
Parser
↓
Query Planner
↓
Executor
↓
Indexes
↓
Tables
↓
Records
↓
Pages
↓
Buffer Pool
↓
Storage Manager
↓
Operating System
↓
Disk
And underneath all of that:
bytes
Understanding those layers gives you a completely different perspective on databases.
34. What We Should Not Build Initially
A common mistake is trying to implement everything immediately.
Don't start with:
SQL
Transactions
WAL
Concurrency
B-Trees
Joins
Indexes
Networking
Replication
all at once.
Instead:
file
↓
pages
↓
pager
↓
rows
↓
table
↓
insert/select
↓
B-tree
↓
SQL
↓
transactions
↓
WAL
Each stage should work before moving to the next.
35. Final Architecture
Our final educational database could look like this:
USER
│
▼
┌─────────────┐
│ SQL │
└──────┬──────┘
▼
┌─────────────┐
│ Lexer │
└──────┬──────┘
▼
┌─────────────┐
│ Parser │
└──────┬──────┘
▼
┌─────────────┐
│Query Planner│
└──────┬──────┘
▼
┌─────────────┐
│ Executor │
└──────┬──────┘
▼
┌─────────┴─────────┐
│ │
▼ ▼
Table Scan B-Tree
│ │
└─────────┬─────────┘
▼
┌─────────────┐
│ Buffer Pool │
└──────┬──────┘
▼
┌─────────────┐
│ Pager │
└──────┬──────┘
▼
┌─────────────┐
│ Database DB │
│ File │
└─────────────┘
Conclusion
Building a SQLite-like database from scratch is one of the best projects for learning systems programming.
You will learn far more than SQL.
You'll learn:
- C programming
- memory management
- binary data
- file I/O
- serialization
- page layouts
- storage engines
- buffer pools
- indexing
- B-trees
- parsing
- query execution
- transactions
- logging
- crash recovery
- operating-system I/O
The important thing is to build it incrementally.
Don't begin by asking:
"How do I build SQLite?"
Start by asking:
"How do I store one page?"
Then:
"How do I store one row?"
Then:
"How do I find that row?"
Then:
"How do I find millions of rows efficiently?"
Then:
"How do I make the operation safe if the program crashes?"
That's how a database engine grows—from a few thousand bytes of C code into a complete storage system.
And the best part is that every layer you implement gives you a deeper understanding of what databases are actually doing underneath the SQL interface.
