Python DB Storage Engine

A from-scratch implementation of core database storage engine internals in pure Python (no external dependencies) — built to understand, hands-on, how a database keeps data on disk, indexes it efficiently, and survives a crash.

Why this project

Most engineers use databases as a black box. This project peels back that abstraction by implementing the pieces that make a storage engine durable and queryable:

• B-Tree index — how data is organized on disk for O(log n) search, insert, update, and delete, including node splitting and merging.
• Write-Ahead Log (WAL) — how writes are made durable before they're applied, and how a crashed database recovers without losing committed data.
• Checkpointing & recovery — how a database avoids replaying its entire history on every restart.

Deliberately out of scope: replication/failover, transactions & concurrency control (isolation levels), and query parsing/optimization — the focus is the storage layer itself, with everything else simplified away.

Architecture

┌─────────────────────────────────────────────────────────────┐
│                          Database                             │
│                                                                 │
│   insert(k, v) / update(k, v) / delete(k)                      │
│        │                                                        │
│        ├──1. append_log──▶  WAL (wal_<table>.txt)             │
│        │                     append-only, flushed to disk       │
│        │                     before the operation is applied    │
│        │                                                         │
│        └──2. apply────────▶  B-Tree (in-memory index)          │
│                                                                  │
│   every N operations ──▶ checkpoint:                            │
│        - serialize B-Tree ──▶ checkpoint_<table>.txt           │
│        - truncate WAL                                          │
│                                                                  │
│   on startup ──▶ recover:                                       │
│        - load checkpoint (if any)                               │
│        - replay remaining WAL entries on top                    │
└─────────────────────────────────────────────────────────────┘

Write path (durability)

Every mutation follows the classic log-before-apply pattern:

1. The operation is wrapped in an LSN (Log Sequence Number) record — {operation_type, data, timestamp}.
2. The LSN is serialized and fsync'd to the WAL file first. If the process crashes here, the operation can still be replayed on restart.
3. Only then is the operation applied to the in-memory B-Tree.

Recovery path

On startup, Database._recover():

1. Loads the last checkpoint (a full serialized snapshot of the B-Tree), if one exists.
2. Replays every WAL entry written after that checkpoint, reconstructing any state lost between the last checkpoint and the crash.

Checkpointing

Replaying an ever-growing WAL on every restart doesn't scale. Every checkpoint_trigger_operation_count operations, the engine:

1. Serializes the entire B-Tree to checkpoint_<table>.txt (JSON).
2. Truncates the WAL, since its entries are now captured in the checkpoint.

B-Tree index

storage_engines/btree.py implements a textbook B-Tree of configurable minimum degree m:

• Search — recursive descent, O(log n).
• Insert — inserts into the correct leaf, splitting nodes (and propagating the split upward, including creating a new root) on overflow.
• Delete — handles all three classic cases: deletion from a leaf, deletion of an internal key (replaced by its in-order predecessor/successor), and underflow resolution via borrowing from a sibling or merging siblings.
• Serialize / deserialize — JSON round-trip of the whole tree, used for WAL replay and checkpointing.

Project layout

database/
  database.py      # Database: ties B-Tree + WAL + checkpoint/recovery together
storage_engines/
  btree.py          # BTree / BTreeNode: insert, search, update, delete, (de)serialize
wal/
  wal.py            # WAL: append-only log file, read, truncate
shared/
  lsn.py            # LSN: the log record format written to the WAL

Usage

from database.database import Database

db = Database("users")

db.insert(1, "alice")
db.insert(2, "bob")
db.update(1, "alice-updated")

print(db.btree.search(1))   # -> "alice-updated"

db.delete(2)
print(db)                    # pretty-prints the B-Tree level by level

Every call above is first written to wal_users.txt, then applied to the B-Tree. Kill the process mid-way and re-run — Database.__init__ will replay the WAL and restore exactly the state before the crash. Every 2 operations (checkpoint_trigger_operation_count), the tree is snapshotted to checkpoint_users.txt and the WAL is cleared.

Try a crash & recovery demo

python3 -c "
from database.database import Database
db = Database('demo')
for i in range(5):
    db.insert(i, f'value-{i}')
print(db)
"

# Re-run — recovers from checkpoint + WAL, picks up where it left off
python3 -c "
from database.database import Database
db = Database('demo')
print(db)
"

Roadmap

This project follows the original learning spec — the B-Tree + WAL path above is implemented; the rest is planned next:

• Hash table storage engine (linear probing / chaining) implementing the same insert/search/delete interface, for a direct architectural comparison with the B-Tree.
• Benchmark suite comparing B-Tree vs. hash table on response time and memory/disk usage across workloads.
• CLI entry point for interactive use.

Tech stack

• Python 3.14, standard library only (no runtime dependencies).
• ruff for linting/formatting, enforced via pre-commit hooks.