The Tree Interface: Where Pages Become Structure in SQLite

#webdev #programming #database #architecture

Hello, I'm Maneshwar. I'm working on FreeDevTools online currently building "one place for all dev tools, cheat codes, and TLDRs" — a free, open-source hub where developers can quickly find and use tools without any hassle of searching all over the internet.

Up to this point, most of our attention has been on the pager. That was deliberate. The pager owns durability, atomicity, and recovery. It decides when bytes move, when locks escalate, and when a transaction truly commits.

The tree module sits one level above that machinery.

Its job is not to worry about journals, locks, or crashes.

Its job is to expose a logical, ordered view of the database, tables and indexes implemented using B-trees and B+-trees and to give the VM a safe way to navigate and modify that structure.

The interface functions we look at today are the bridge between the VM and the pager-backed storage world.

Opening and Closing the Database

Everything begins with sqlite3BtreeOpen.

Despite the name, this function does not open a single tree. It opens a connection to the database file itself. Internally, it delegates that responsibility straight to the pager by calling sqlite3PagerOpen.

What it returns is a Btree object — a handle that represents the database connection at the tree layer. From this point on, the VM talks to the database exclusively through this handle.

Closing follows the same layered discipline.

When sqlite3BtreeClose is called, SQLite does not immediately tear things down.

First, it rolls back any active transaction, invalidates and closes all open cursors, and frees all tree-level resources.

Only then does it call sqlite3PagerClose to release the underlying pager and file handles.

This ordering matters. It ensures that no higher-level object ever outlives the pager state it depends on.

Cursors: How the VM Walks Trees

The most important abstraction the tree module exposes is the cursor.

A cursor represents an active position inside a single B-tree. It is created by calling sqlite3BtreeCursor, which opens a specific tree identified by its root page.

A cursor can be either a read cursor, or a write cursor but never both.

SQLite enforces a strict rule here: read and write cursors may not coexist on the same tree. This means a transaction cannot read and write the same tree concurrently through different cursors.

The restriction simplifies correctness and avoids subtle structural hazards.

Multiple cursors can exist on the same tree, as long as they all agree on access mode.

When the very first cursor is created on a connection, the tree module obtains a shared lock on the database file through the pager.

The tree layer doesn’t decide lock strength it simply signals intent. The pager does the actual locking.

Cursor Lifetime and Lock Release

Closing a cursor is explicit.

sqlite3BtreeCloseCursor releases the cursor’s internal resources. When the last cursor on a connection is closed regardless of which tree it was on the shared lock on the database file is released.

sqlite3BtreeClearCursor goes one step further. It invalidates the cursor without freeing it. Any future attempt to use that cursor results in an error. This is commonly used during rollback paths, where cursors must be rendered unusable immediately.

Navigating the Tree

Once a cursor exists, the tree module provides movement primitives that feel natural to the VM.

sqlite3BtreeFirst moves the cursor to the first entry in the tree, which means descending to the left-most leaf.

sqlite3BtreeLast does the symmetric operation and moves to the right-most leaf.

From there, iteration is explicit and ordered.

sqlite3BtreeNext advances the cursor forward, while sqlite3BtreePrevious moves it backward. These functions encapsulate all the complexity of moving across leaf pages, handling page boundaries, and maintaining cursor invariants.

The VM doesn’t need to know where pages split or how siblings are linked. It simply asks for “next” or “previous”.

Transactions at the Tree Layer

Starting a transaction from the VM’s perspective happens through sqlite3BtreeBeginTrans.

This function requests either a read transaction, or a write transaction

and may optionally request an exclusive transaction, which prevents all other connections from accessing the database.

The tree module itself does not manage locks or journals.

It forwards the request to the pager, which decides whether the request can be satisfied and what lock transitions are required.

Commit and Rollback, Tree-Style

Committing at the tree layer mirrors what we saw earlier at the pager layer.

sqlite3BtreeCommitPhaseOne performs the heavy lifting: flushing journals and database files.
sqlite3BtreeCommitPhaseTwo finalizes the journal, downgrades locks, and releases them if no cursors remain.