The Architecture Of A Modern SQLite: Pager, B‑Tree, And Virtual Machine Internals

Introduction

The year is 2024. Your smartphone has just processed a thousand contact lookups, your browser has cached the last dozen visited pages, and your smart thermostat has logged temperature readings every minute for the past month. Every one of those operations, from the trivial to the critical, likely relied on the same piece of software: SQLite. It is, by almost any measure, the most widely deployed database engine in existence. It lives inside every Android and iOS device, every major web browser (Chrome, Firefox, Safari), countless embedded systems, and even runs on the International Space Station. Yet for all its ubiquity, SQLite remains an enigma to most developers. We interact with it through a simple SQL interface, treat it as a “drop‑in” file‑based database, and move on. But beneath that innocent facade lies one of the most elegant and carefully engineered pieces of system software ever written.

SQLite was created by D. Richard Hipp in 2000, initially as a side project while working for a major defense contractor. The original motivation was simple: provide an SQL interface over a local file store that required no configuration, no server process, and no administration. Twenty‑four years later, the core architectural decisions—a compact virtual machine, a copy‑on‑write B‑tree, and a meticulously designed pager layer—remain largely unchanged. The version numbering alone (3.46.x as of mid‑2024) testifies to the stability of the design.

This blog post is the first in a series that will pull back the curtain on SQLite’s internals. We’ll explore not just how SQLite works, but why it works the way it does—why its architecture has remained remarkably stable for over two decades, and how a handful of design decisions enable it to outperform more heavyweight databases in environments where memory is measured in kilobytes and reliability is paramount.

Why SQLite’s Architecture Matters

You might ask: why should a modern developer care about the internals of a small, embedded database? The answer is threefold.

First, because performance predictability is critical. When you write INSERT INTO logs VALUES (...) in a mobile app, you expect that call to complete in a few milliseconds—not a few seconds. But that seemingly simple statement triggers a cascade of interconnected subsystems: parsing, binding, planning, paging, caching, journaling, and finally, the actual write to disk. Understanding how these layers interact helps you diagnose latency spikes, choose the right transaction mode, and avoid common pitfalls like unnecessary large transactions or improper use of PRAGMA.

Second, reliability is non‑negotiable. SQLite is used in safety‑critical systems (avionics, automotive, medical devices) where a database corruption could be disastrous. Its design emphasizes crash safety through techniques like atomic commits via a rollback journal (or Write‑Ahead Log), meticulous handling of disk page writes, and a defensive coding style that assumes the worst from the underlying filesystem. Knowing the internals gives you confidence that the library lives up to its famous tagline: “SQLite will never give you corrupt data.”

Third, portability and resource efficiency are increasingly important in the era of edge computing and serverless architectures. SQLite’s codebase is around 150,000 lines of C, compiles to a single library of ~700 KB, and runs on everything from 8‑bit microcontrollers to 64‑bit supercomputers. Its architecture has been refined to minimize heap allocations, avoid dynamic dispatch, and fit comfortably within a few hundred kilobytes of RAM. Understanding how it achieves this leanness can inspire better design in your own systems, whether you’re building a caching layer, a configuration store, or a full‑blown distributed database.

A Quick Historical Perspective

To appreciate the architecture, it helps to know the constraints that shaped it. SQLite was born in an era when desktop computers had 64 MB of RAM and spinning hard disks with 10 ms seek times. The initial design goals were:

• Zero‑configuration: No server, no configuration files, no tuning knobs.
• Small footprint: Library size under 250 KB (achieved and later exceeded with features).
• Full ACID transactions: Even on systems that crash midway through a write.
• Public domain (later changed to a permissive open‑source license).

These constraints led to a layered architecture where each layer solves a specific problem:

1. Tokenizer / Parser: Converts SQL text into an internal parse tree.
2. Code Generator: Translates the parse tree into bytecode for an internal virtual machine.
3. Virtual Machine (VDBE): Executes bytecode, operating on database records and controlling flow.
4. B‑Tree: Manages the on‑disk structure of rows and indexes, providing ordered storage and efficient lookups.
5. Pager: Handles the nuts‑and‑bolts of reading/writing pages to disk, transaction management, and crash recovery.
6. OS Interface: Abstracts filesystem operations (locking, flushing, read/write) for portability.

The rest of this post dives deep into three of the most fascinating subsystems: the Pager, the B‑Tree, and the Virtual Machine. By the end, you’ll be able to trace the journey of a simple SQL statement from text to disk and back again.

1. The Pager: The Gatekeeper of Disk I/O

The pager is the lowest layer of SQLite’s storage engine, sitting directly above the OS interface. Its job is both simple and terrifyingly complex: manage a cache of fixed‑size pages, ensure atomic writes to the database file, and provide consistent data even after power loss or system crash.

1.1 Page Anatomy

SQLite divides the database file into pages, which are fixed‑size blocks. The default page size is 4096 bytes (4 KB), but it can be set from 512 bytes up to 65536 bytes when the database is created. Every page belongs to one of a few categories:

• Lock‑byte page: A reserved page used for file‑locking protocols (on some platforms).
• Freelist pages: Pages that have been freed and are available for reuse.
• Pointer‑map pages: Used in incremental vacuum to track relocation of pages.
• B‑Tree pages: The most common type, storing actual table or index data.
• Overflow pages: Used for large B‑Tree cells that don’t fit in a single page.

The pager doesn’t care about the content of a page—it treats pages as opaque blocks of memory. It provides a simple interface:

// Read page number Pgno into memory, return pointer.
void *sqlite3PagerGet(Pager *pPager, Pgno pgno);

// Write the contents of a page back to disk (if dirty).
int sqlite3PagerWrite(DbPage *pPage);

// Commit all pending changes.
int sqlite3PagerCommitPhaseOne(Pager*, int final);
int sqlite3PagerCommitPhaseTwo(Pager*);

// Rollback to previous state.
int sqlite3PagerRollback(Pager*);

1.2 The Page Cache

Every database connection maintains an in‑memory cache of recently accessed pages, known as the page cache (or sometimes the “pcache” module). The cache size is configurable via PRAGMA cache_size; the default is 2 MB for a 4 KB page size (i.e., 500 pages). The pager uses a sophisticated algorithm that blends least‑recently‑used (LRU) eviction with explicit knowledge of B‑Tree access patterns.

But cache management is only half the story. The pager also implements journaling to guarantee atomic transactions.

1.3 Journaling Modes: Rollback vs. Write‑Ahead Log

SQLite offers two fundamentally different approaches to ensuring that a transaction is either fully applied or fully rolled back: the traditional rollback journal and the newer write‑ahead log (WAL).

Rollback Journal (Original)

The rollback journal mode works as follows:

1. Before modifying any page, the original content is written to a separate file called the journal (e.g., database.sqlite-journal).
2. The modified pages are written to the main database file only after the journal is fully flushed to disk (the “commit”).
3. If a crash occurs before the commit is finalized, the journal is used to restore the original content.

This is a classic “undo” log. The critical step is ordering: the original pages must be on disk in the journal before the main database is overwritten. SQLite guarantees this using fsync() (or its platform equivalent) at key points. The trade‑off is that every write transaction involves writing the data twice (journal + database), which can be I/O‑intensive.

Write‑Ahead Log (WAL)

Introduced in SQLite 3.7.0 (2010), WAL mode dramatically improves concurrency and write performance. Instead of writing changes directly to the main database file, all modifications are appended to a separate WAL file (-wal). Readers continue to read from the main database file, which remains immutable while a writer is active. A checkpoint operation later merges the WAL changes back into the main database.

Key advantages of WAL:

• Concurrent reads and writes: A writer does not block readers; readers only wait if they need to read a page that is currently being written to the WAL.
• Better write throughput: Writes become sequential appends to the WAL, which is much faster than random page updates in the main file.
• Improved crash recovery: The WAL is always consistent; recovery simply replays or truncates the WAL.

The trade‑off is slightly more complexity (the WAL must be checkpointed periodically) and slightly higher disk usage during large transactions.

1.4 The Art of the Atomic Commit

SQLite’s most celebrated internal achievement is its atomic commit protocol—the mechanism that ensures a transaction is either completely visible or completely invisible after a crash. The protocol is documented in exquisite detail in the SQLite source code (see atomic_commit.md), but the essence is:

• Phase 1 (write): All modified pages are written to the appropriate journal (rollback or WAL) and flushed to disk.
• Phase 2 (commit): A single sector‑aligned write (the “commit record”) is performed to the database file (rollback) or WAL header (WAL). If the process crashes before this write, the journal is used to roll back. If it crashes after, the journal is ignored (for rollback) or replayed (for WAL).

The cleverness lies in making that final write atomic at the disk sector level. Most hard drives guarantee that a 512‑byte sector write is atomic (it either happens completely or not at all). SQLite exploits this by ensuring its commit record fits within a single sector, and that the sector is written using the most reliable method available (direct I/O or O_SYNC).

1.5 Locking and Concurrency

Even though SQLite is an embedded library (not a server), it still must handle multiple processes accessing the same database file simultaneously. The pager uses a file‑locking protocol based on the OS’s advisory file locks. On Unix, this means flock() or fcntl(). On Windows, it uses LockFileEx().

The locking states (simplified) are:

• UNLOCKED: No locks held.
• SHARED: Can read from the database but cannot write. Multiple shared locks can coexist.
• RESERVED: A writer intends to modify the database but hasn’t started yet. Other processes can still hold shared locks.
• PENDING: The writer is waiting for existing shared locks to release; new shared locks are denied.
• EXCLUSIVE: The writer has exclusive access and can modify pages.

The transition from SHARED to RESERVED is non‑blocking: a writer can plan the changes (read pages, compute new B‑tree cells) while readers still hold shared locks. Only when the writer actually needs to commit does it escalate to EXCLUSIVE, which may block.

Note: WAL mode changes the locking drastically—readers never block writers and vice versa, except for checkpointing operations.

1.6 Performance‑Sensitive Details

The pager is heavily optimized for typical workloads:

• Sector‑size alignment: Pages are written at offsets that are multiples of the disk sector size to avoid read‑modify‑write cycles.
• Bulk write optimizations: During commit, dirty pages are sorted by page number and written in sequential order to minimize disk seeks.
• Memory‑mapped I/O (mmap): On modern 64‑bit systems, SQLite can use mmap() to map the database file directly into the process’s address space, eliminating the need for explicit read/write calls and page cache copies. This can double performance for read‑heavy workloads.
• Double‑write buffering: When using the rollback journal, the pager maintains a copy of the page image in memory to avoid re‑reading from the journal during rollback.

1.7 Code Example: Peeking Inside the Pager

Let’s look at a simplified representation of a pager‑page structure (from sqlite3.c):

struct DbPage {
  Pgno pgno;                /* Page number for this page */
  DbPage *pNextFree, *pPrevFree; /* Free list links */
  Pager *pPager;            /* The pager that owns this page */
  u8 *pData;                /* Page content (size pPager->pageSize) */
  u8 flags;                 /* Page flags: PGHDR_DIRTY, etc. */
  // ... many more fields
};

The pager maintains a hash table (by page number) for fast lookup, plus a LRU free list for eviction. Every call to sqlite3PagerGet() either finds the page in the cache or issues a disk read, potentially evicting the least‑recently‑used page from the free list if the cache is full.

2. The B‑Tree: Ordered, Scalable, Resilient

Above the pager sits the B‑Tree module. SQLite uses a variant of the classic B‑Tree known as a B+‑Tree, where all actual data resides in the leaf nodes and internal nodes contain only keys and pointers. This is the same structure underlying most relational databases (e.g., InnoDB), but tuned for the embedded environment.

2.1 B‑Tree Page Layout

Every B‑Tree page follows a fixed header:

After the header comes the cell pointer array: an array of 2‑byte offsets (little‑endian), each pointing to the start of a cell in the cell content area. The cells themselves are packed from the bottom of the page upward, and the free space grows from the top downward. This design allows efficient insertion: you move the cell pointers, then append the new cell at the top of the content area.

2.2 Cell Structure

A cell is the atomic unit of the B‑Tree. For a table leaf page, a cell contains:

• A payload (the actual row data, potentially split across overflow pages).
• The row ID (a 64‑bit integer, usually the rowid if no explicit primary key is declared).
• Payload length fields (varint‑encoded).

For an interior table page, a cell contains a child page number and a row ID (the minimum key in the subtree).

For index pages, cells store the index key values and a reference to the original row (either a rowid or the full row content if WITHOUT ROWID).

2.3 Overflow Pages

SQLite has a clever way of handling large rows. Each page has a usable size (typically 4 KB minus a overhead for the page header and reserved bytes for extensions). If a row’s payload exceeds roughly one quarter of the usable space (the “overflow threshold”), part of the payload is stored in a chain of overflow pages. The cell then contains only the local payload (the first few bytes) plus a pointer to the first overflow page.

The overflow pages themselves are simple: they store a pointer to the next overflow page (if any) and the rest of the payload data. This avoids the complexity of splitting large rows across B‑Tree pages while still keeping small rows efficient.

2.4 Searching and Traversal

When a query uses a primary key or a unique index, the B‑Tree performs a binary search on the cell pointers within a page. Because the cell pointers are sorted by key (row ID or index key), the search is O(log n) per page, and the tree depth is logarithmic in the number of pages. In practice, SQLite B‑trees rarely exceed 4 levels (even for databases with billions of rows), so a typical lookup involves 3–4 page reads.

For range queries, the B‑Tree supports forward/backward iteration by following the cell pointers and the “right‑most child” pointer on interior pages. The leaves are linked via a next‑page pointer (the last cell pointer of a leaf page includes the sibling page number, though this is not explicitly stored—the pager’s B‑Tree layer maintains a separate linked list over the pages). Actually, in SQLite, leaf pages of the same depth are not explicitly linked; instead, the code does a cursor‑based traversal that walks down the tree and follows right‑child pointers. This is a deviation from a classic B+‑tree where leaves form a linked list. SQLite’s approach saves one pointer per leaf but complicates full‑table scans (they must always go through the root). There is a SQLITE_ENABLE_SORTED_TABLES compile‑time option that adds leaf‑level links, but it’s not default.

2.5 Insertions, Splits, and Balance

When a new row is inserted into a B‑Tree leaf that is full, the page must split. SQLite allocates a new page from the freelist (or from the end of the file), moves roughly half the cells to the new page, inserts the new cell in the appropriate leaf, and then promotes the smallest key from the new page up to the parent. This process can cascade up the tree, potentially splitting the root and increasing the tree height.

Splits are expensive, so SQLite tries to reduce them by leaving about 10% free space in each page after a split (the fill factor). The default fill factor is 100% (i.e., pages are packed full), but the B‑Tree still reserves some slack for future insertions by not splitting at exactly half—the exact algorithm is described in the source as “balanced splitting” to keep the tree roughly balanced.

2.6 Integration with the Pager

The B‑Tree module never talks directly to the disk. All page access goes through the pager:

1. sqlite3BtreeGetPage() calls sqlite3PagerGet() to load the page.
2. Before writing to a page, the B‑Tree calls sqlite3PagerWrite() which first copies the original page to the journal (if in rollback mode) or notifies the WAL.

This separation means the B‑Tree can focus on data structures while the pager handles concurrency and crash recovery. The B‑Tree also uses cursors (BtreeCursor objects) to track position in the tree, which hold a reference to a page (through the pager) and an index into the cell pointer array.

2.7 Example: Creating a Table and Inserting

When you execute:

CREATE TABLE users (id INTEGER PRIMARY KEY, name TEXT);
INSERT INTO users VALUES (1, 'Alice');

SQLite creates a B‑Tree to store table users. The tree initially has a single root page (type leaf table). The CREATE TABLE statement writes a record to the sqlite_schema table (also a B‑Tree). Then the INSERT creates a cell for rowid=1 with the column data (the constant 1, and the text 'Alice'). If the page is full, it splits.

2.8 Without Rowid Tables

Modern SQLite allows CREATE TABLE ... WITHOUT ROWID. In this case, the table is stored as an index B‑Tree where the primary key columns become the key of the tree, and the remaining columns are stored in the payload. This eliminates the artificial rowid and can be more efficient for tables with compound primary keys.

3. The Virtual Machine (VDBE): Where SQL Comes to Life

The VDBE (Virtual DataBase Engine) is the runtime that executes compiled SQL bytecode. It is a register‑based virtual machine, somewhat similar in spirit to the Java Virtual Machine (JVM) or the Lua VM, but designed specifically for relational operations. Every SQL statement is compiled into a sequence of VDBE opcodes, which are then executed by a simple loop.

3.1 Opcode Overview

There are about 200 opcodes, but a typical query uses only a dozen. Opcodes are defined in sqlite3.c (or the symbolic vdbe.h). Examples:

• OP_OpenRead / OP_OpenWrite – Open a cursor on a B‑Tree.
• OP_SeekRowid – Position a cursor to a specific rowid.
• OP_Next – Advance to next entry in a B‑Tree.
• OP_Column – Extract a column from the current row.
• OP_ResultRow – Output a row to the user.
• OP_Transaction – Begin a transaction.

Each opcode has up to 5 operands (P1, P2, P3, P4, P5) and a comment field (P5 is a flag byte, P4 can be a string or a pointer).

3.2 Register‑Based Versus Stack‑Based

Unlike the stack‑based JVM, the VDBE uses a register model. There is a fixed array of registers (default 1000 or so) in the VDBE’s virtual machine state. Operations read values from one or more registers, compute, and write the result back to a register. For example, OP_Add takes two arguments (P1 is the result register, P2 and P3 are source registers). This reduces instruction count compared to a stack machine because there’s no need for push/pop overhead.

3.3 Cursors

Cursors are the VM’s way of navigating B‑Tree tables and indexes. They are identified by small integer indices (P1 of cursor‑related opcodes). A cursor holds:

• A pointer to the B‑Tree structure.
• Current page number and cell index.
• A flag indicating whether it is at a valid position.
• A mask of columns to be fetched (for partial decoding).

The VM supports up to SQLITE_MAX_VDBE_CURSORS (default 64) concurrently.

3.4 Compilation to Bytecode: An Example

Consider:

SELECT name FROM users WHERE id = 1;

The code generator produces something like this (simplified):

01: OP_Transaction     0                    # Begin read transaction
02: OP_OpenRead        0   2   "users"      # Open cursor 0 on table with root page 2
03: OP_SeekRowid       0   1                # Seek cursor 0 to rowid=1
04: OP_Column          0   0                # Retrieve column 0 (name) into register 1
05: OP_ResultRow       1   1                # Output register 1 as a single‑column row
06: OP_Close           0                    # Close cursor
07: OP_Halt            0                    # End execution

If the row does not exist, OP_SeekRowid sets a flag that causes a branch (not shown) to skip OP_Column and OP_ResultRow.

3.5 The Execution Loop

The execution engine is a single switch statement inside a while loop (sqlite3VdbeExec()). It fetches the next opcode, decodes operands, and performs the action. The loop is tight and fast, with minimal overhead. For read‑only queries, the VM runs entirely within user‑space (no context switches) and can process millions of simple lookups per second.

3.6 Subqueries, Aggregates, and Sorting

Complex queries are broken into multiple VDBE programs. For example, a subquery becomes a separate VM that is invoked via OP_SubProgram. Aggregates (e.g., GROUP BY) use a separate aggregate context and opcodes like OP_AggStep and OP_AggFinal. Sorting uses an external sort structure (a priority queue or merge sort, also built on top of B‑Tree temporary tables).

3.7 Debugging and Profiling

You can inspect the bytecode generated by any SQL statement using the .explain command in the sqlite3 shell:

sqlite> EXPLAIN SELECT name FROM users WHERE id = 1;
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     8     0                    00  Start at 8
1     OpenRead       0     2     0     2              00  root=2
2     SeekRowid      0     1     6                     00  intkey=1
3     Column         0     0     1                     00  users.name
4     ResultRow      1     1                          00
5     Halt           0
6     Close          0                                 00
7     Halt           0
8     Transaction    0     0                          01  useCache
9     Goto           0     1                          00

The Init opcode at address 0 does housekeeping, then jumps to the main program starting at address 1 (via Goto). This layout allows SQLite to handle error handling and cleanup gracefully.

3.8 Performance Tricks in the VM

• Constant folding: Operations on constants are computed at compile time.
• In‑place updates: When possible, the VM modifies a B‑Tree cell directly without a full delete/insert.
• Short‑circuit evaluation: WHERE clauses that are always false or true are optimized away.
• Affinity handling: The VM automatically converts values between storage classes (integer, real, text, blob) based on column affinity, but does so efficiently using type encoding in the register values.

3.9 The VM as a Portability Layer

One of the most brilliant aspects of SQLite is that the VDBE bytecode is not just an implementation detail—it’s the core of the SQL engine. Because the VM is platform‑independent, SQLite can be ported to new operating systems by simply recompiling the C source; the VM never changes. Moreover, the VM makes it possible to implement custom SQL functions, virtual tables, and even entirely new query plans without altering the pager or B‑Tree.

4. Putting It All Together: The Life of a Query

Let’s trace a complete INSERT with a rollback journal to see how the layers interact.

1. SQL Parsing: The tokenizer breaks the input into tokens, the parser builds a parse tree.
2. Code Generation: The code generator emits VDBE bytecode: OP_Transaction (with a flag indicating a write transaction), OP_OpenWrite for the table, OP_NewRowid (or use passed rowid), OP_MakeRecord to pack columns, OP_Insert to insert into B‑Tree, and OP_Commit eventually.
3. VM Execution: The VDBE runs the bytecode. The OP_Transaction calls into the pager to begin a write transaction. The pager may escalate from SHARED to PENDING to EXCLUSIVE lock.
4. B‑Tree Insert: OP_Insert calls sqlite3BtreeInsert(). This function calls sqlite3PagerWrite() on the leaf page that will receive the new cell. The pager, seeing the page is dirty for the first time, writes the original page image to the rollback journal and flushes it. Then the B‑Tree inserts the cell (which may trigger a split).
5. Commit: After the last OP_Insert, the OP_Commit opcode calls sqlite3PagerCommitPhaseOne(), which flushes all modified pages to the database file (not just the journal). After flushing, it writes the commit record. Then PhaseTwo clears the journal and releases the lock.

If a crash occurs after the journal flush but before the commit record write, the journal remains and the recovery process replays it, undoing the changes. If the crash occurs after the commit record write, the journal is ignored (or deleted).

5. Failure Modes and Edge Cases

5.1 Journal File Recovery

If an application opens a database that has a stale journal file, the pager’s recovery routine runs. For rollback mode, this involves reading the journal, overwriting the corresponding pages in the database file, and then deleting the journal. In WAL mode, recovery replays the WAL (applying any committed changes) and truncates it.

5.2 Database Corruption

Despite its reliability, SQLite can encounter corruption due to hardware faults, filesystem bugs, or manual editing of the database file. The pager includes integrity checks (like checksum in the page header) that can detect corruption. When detected, the library returns SQLITE_CORRUPT and prevents further damage.

5.3 Handling of Shared Cache Mode

SQLite also supports a shared cache mode where multiple database connections within the same process can share the same pager cache and B‑Tree objects. This mode (enabled by PRAGMA shared_cache) can improve performance in multi‑threaded applications but introduces subtle locking rules. It’s not widely recommended and is disabled by default in newer versions.

6. Modern Developments and the Future

SQLite is actively maintained, with a steady stream of improvements:

• WAL2 mode (experimental): An improvement over WAL that reduces checkpoint overhead.
• Content‑free schema: Plans to allow schema changes without rewriting the entire database (see the sqlite3recover work).
• Better use of large page sizes: Optimizations for NVMe SSDs and high‑bandwidth storage.
• Compiled SQL and VDBE caching: In SQLite 3.31.0, prepared statements can be cached more aggressively.

The architecture, however, remains fundamentally unchanged—a testament to the soundness of the original design.

Conclusion

SQLite is often underestimated because it’s small and free. But its internals reveal a masterwork of software engineering: a tightly integrated stack of pager, B‑Tree, and virtual machine that delivers ACID transactions, incredible portability, and robust performance across billions of devices. Understanding these layers not only helps you use SQLite more effectively (choosing WAL vs. rollback, tuning the cache, interpreting the output of .explain), but also provides inspiration for building your own resilient, embedded systems.

The next time you issue a SELECT from your smartphone’s address book, take a moment to appreciate the journey: from a text string, through a parser, into bytecode, across a register‑based VM, down through a B‑tree, via the pager’s page cache, through an OS‑level read() syscall, all the way to the NAND flash chip. It’s a remarkable feat for a library that fits in 700 KB.

Now go forth and PRAGMA journal_mode=WAL; with confidence.

This article was the first in a series on SQLite internals. Future posts will dive deeper into the query optimizer, the WAL checkpoint mechanism, and the virtual table interface. Subscribe to stay updated.