SQLite File Layout: Pages, B-Trees, and the Freelist

An application database on a phone is one file in an app container, and that file is a paged store with a b-tree on top. There is no separate index file, no directory of tables, and no fixed record length. A row lives wherever the tree put it, a large row is split across pages joined by pointers, and a deleted row leaves a hole that the allocator will hand out again. Nearly every behaviour that surprises people follows from this layout: the file that does not shrink after a bulk delete, the write that is slower than the row size suggests, the corruption after a power loss.

Pages are the unit of everything

A database file is an array of equally sized pages, numbered from one. Page one is special because it begins with a 100-byte header; every other page is pure payload. The page size is a power of two between 512 and 65536 bytes, stored as a two-byte big-endian value at offset 16 of the header, with the value 1 standing in for 65536 since that number does not fit in sixteen bits. The conventional choice is 4096 bytes, matching the usual memory page and the usual erase granularity reported by flash translation layers.

Every read and every write happens at page granularity. The pager holds a cache of pages, and a transaction that modifies one row dirties exactly one page unless the row spills. That is the central design constraint: the storage engine never asks the filesystem for a byte range, so the cost of an update is one page rewrite regardless of whether one field changed or forty. On flash this matters more than on a spinning disk, because rewriting a 4 KiB page inside a 512 KiB erase block forces the controller to copy the other live pages out first.

Not all of a page is usable. Offset 20 of the header gives the number of reserved bytes at the end of each page, normally zero but set to 32 or more by some builds for checksums or for page-level encryption. The usable size is the page size minus that reservation, and every capacity limit below is expressed in terms of the usable size, not the nominal page size.

What the header pins down

The header is not a free-form metadata area; almost every field answers a question the reader must settle before it can trust a single byte.

The first sixteen bytes hold the magic string SQLite format 3 followed by a NUL. Offsets 18 and 19 record the file format write and read versions: 1 means the legacy rollback journal, 2 means write-ahead logging. These two bytes are how a database remembers that it is in WAL mode across connections: the setting is in the file, not in the process. Offsets 21 through 23 encode the payload fractions (64, 32, 32) that the overflow arithmetic depends on.

Offset 24 is the file change counter, incremented on every transaction that modifies the file, and offset 92 records which value of that counter the in-header page count at offset 28 was valid for. A reader that finds these two disagreeing knows the page count is stale and must re-derive it from the file size. Offset 32 points at the first trunk page of the freelist and offset 36 counts the free pages, which is the pair of numbers that explains why a file fails to shrink.

Offset 40 is the schema cookie, bumped whenever the schema changes, which is how a prepared statement knows its cached plan is obsolete. Offset 44 holds the schema format number, 1 through 4; format 4, in use since SQLite 3.3.0, is the version that permits descending indexes. Offset 56 declares the text encoding, where 1 is UTF-8, 2 is UTF-16 little-endian, and 3 is UTF-16 big-endian. Offset 60 is the four-byte application-defined user_version, and offset 68 the application_id, both of which exist purely so an application can identify its own file and its own schema generation.

Page one is also the root of the sqlite_schema table, so its b-tree header starts at byte 100 and it has 100 fewer bytes of cell space than any other page. A schema with many tables and indexes can therefore overflow page one, at which point the schema table grows a level like any other b-tree.

Cells, freeblocks, and the overflow threshold

A b-tree page begins with an eight-byte header: a type byte, a two-byte offset to the first freeblock, a two-byte cell count, a two-byte offset to the start of cell content, and one byte counting fragmented free bytes. Interior pages add a four-byte right-most child pointer and use a twelve-byte header. The type byte distinguishes a table interior page (5), table leaf (13), index interior (2), and index leaf (10). The four combinations exist because table pages key on a rowid and index pages key on an arbitrary record.

After the header comes the cell pointer array: two-byte offsets, sorted by key, pointing into the cell content area which grows downward from the end of the page. Cells are not stored in key order; the pointer array is. An insertion appends a cell wherever free space allows and inserts a pointer in the right slot, which is why a page can accumulate fragmentation when cells of varying size are deleted and reinserted.

A table leaf cell is a varint payload length, a varint rowid, the payload, and, if the payload did not fit, a four-byte pointer to an overflow page. The threshold is the interesting part. With U the usable size, a table leaf stores up to U-35 bytes locally. Above that, the engine computes M = ((U-12)*32/255)-23 and K = M + ((P-M) % (U-4)) for a payload of P bytes; it stores K bytes locally when K <= U-35 and M bytes otherwise, pushing the remainder into a chain of overflow pages. Each overflow page spends four bytes on the next pointer, so a chain of n pages holds n*(U-4) bytes. The consequence is that a 1 MiB blob occupies roughly 256 overflow pages at 4096-byte pages, and reading it requires 256 dependent page fetches rather than one sequential read.

Freeblocks inside a page are a linked list threaded through the cell content area, each with a two-byte next offset and a two-byte size, minimum four bytes. Space that cannot form a four-byte freeblock counts as fragmented and is reclaimed only when the page is rebuilt, which happens on vacuum or on a b-tree balance.

The freelist and why the file does not shrink

Dropping a table or deleting rows frees pages, but the pages are not returned to the filesystem. They go on a freelist, a singly linked chain of trunk pages. A trunk page stores a four-byte pointer to the next trunk, a four-byte count of leaf entries, and then that many four-byte page numbers, so a single trunk can reference at most (U/4)-2 free pages: 1022 entries at 4096 bytes. When the database needs a page, it takes one from the freelist before extending the file.

This is why a table that grows to 200 MB and then loses 190 MB of rows still occupies 200 MB. The header’s free-page count tells the truth; the file size does not. Two mechanisms reclaim the space. A full VACUUM rebuilds the entire database into a new file and swaps it in, which requires free space equal to the database size and rewrites every page. Incremental vacuum, enabled by PRAGMA auto_vacuum=INCREMENTAL before any table exists, moves pages off the end of the file one step at a time and truncates the tail, at the cost of a pointer-map page per page group and slightly more work on every page move.

-- Sizes and slack in an open database
PRAGMA page_size;        -- bytes per page, e.g. 4096
PRAGMA page_count;       -- pages currently in the file
PRAGMA freelist_count;   -- pages allocated but unused
PRAGMA auto_vacuum;      -- 0 none, 1 full, 2 incremental
SELECT (SELECT * FROM pragma_page_count) * (SELECT * FROM pragma_page_size)
       - (SELECT * FROM pragma_freelist_count) * (SELECT * FROM pragma_page_size)
       AS live_bytes;

The difference between page_count and freelist_count is the amount actually in use. On a device with a fixed storage budget, that difference is the number worth budgeting against, and the free pages are a reserve that a later insert can consume without touching the filesystem.

Where the format constrains the application

Three consequences follow from the layout rather than from any policy.

Row size is not free. A row whose payload exceeds the local threshold costs an overflow chain, and the chain is traversed page by page, so a schema that stores images or long text in ordinary columns turns a single-row read into hundreds of page fetches. Storing large objects in separate files, with the database holding a path and a length, keeps the b-tree pages dense and the reads sequential.

Page size is fixed at creation. PRAGMA page_size has no effect once a table exists; changing it requires a VACUUM into a new file, and on a phone that means temporarily needing twice the space. A 4096-byte page is the safe default; larger pages reduce depth for large rows but waste space on small ones and increase the write amplification of a single-row update.

Deletion is cheap, reclamation is not. The freelist makes deletes fast and keeps the file size stable, and the same mechanism makes the file a poor indicator of how much data it holds. The write-ahead log adds a second layer to this picture: WAL frames and checkpointing determine how much of the file is being rewritten per transaction, and journal modes and fsync cost determine whether those page writes survive a power cut. Both build directly on the page numbering described here.

The format also explains a class of corruption that has nothing to do with the b-tree logic. Because a page is written as a unit, a crash during a page write can leave a page half old and half new. Every durability mechanism in SQLite exists to ensure that such a page is either never visible or can be reconstructed, and any application that stores its database on a filesystem that does not honour flush requests (a removable volume, a network mount, a directory synced by an external tool) has removed that guarantee without being told.