SQLite B-Tree

Table Btree: Rowid-Keyed

The default storage for tables with INTEGER PRIMARY KEY (or no explicit PK).

Every "ordinary" SQLite table is a b-tree where:

key   = 64-bit signed integer rowid (auto-assigned or your INTEGER PRIMARY KEY)
value = the row's column values, serialized via the SQLite "record format"

cell layout in a leaf:
  varint payload-length
  varint rowid
  payload bytes:
    varint header-length
    varint type-code per column (NULL, int, real, text, blob, …)
    raw column values

The varints (variable-length integers) make small numbers cheap: a column type code for NULL is one byte; an INT row payload header is ~5 bytes total. The record format also encodes column types alongside data, letting SQLite be schemaless internally — type affinity is enforced at insert time but storage is type-aware.

Rowid lookup: descend the b-tree from root to leaf. Interior cells contain (rowid, child_page); leaf cells contain (rowid, payload). Standard b-tree algorithm. For a 1M-row table at 4 KB pages, the tree is ~3 levels deep: root, interior, leaf. Three reads to find any row.

Index Btree: Composite-Keyed

Secondary indexes and WITHOUT ROWID tables.

Index btrees use a different cell format:

key   = the indexed column(s) value, then the rowid
        (concatenation makes keys unique even for non-unique indexes)
value = empty (the rowid is part of the key, suffices to find the row)

CREATE INDEX idx_name ON users(name);
→ index btree keyed on (name, rowid)
→ leaf cell payload is empty
→ to read the user's other columns, follow the rowid into the table btree

The (column, rowid) composite key serves two purposes: (1) it makes index entries unique even when many rows share the same column value, (2) it provides a stable secondary order so that a SELECT WHERE name='alice' ORDER BY id returns rows in rowid order without a sort.

A query that uses an index to find rows pays for the extra hop: index btree descent (to find the rowid), then table btree descent (to read the row). Two trees touched, ~6 reads for a 1M-row table. Covered indexes (where every column the query needs is in the index key) avoid the second descent.

WITHOUT ROWID Tables

A table whose primary key is also its index — no separate rowid.

The default table format wastes space when the user has a natural primary key (a UUID, a string), because the table btree's rowid is auto-assigned and you typically also need an index on the natural key — paying for two btrees. WITHOUT ROWID collapses these: the natural primary key becomes the table btree's key, and the row data is the cell payload.

CREATE TABLE users (
  email TEXT PRIMARY KEY,
  name TEXT,
  created_at INTEGER
) WITHOUT ROWID;

→ table is a b-tree keyed on email (string compare)
→ cell payload is (name, created_at)
→ no separate index on email needed (the table IS the index)

Tradeoffs: lookups by primary key are faster (one btree instead of two). Lookups by other columns still need separate secondary indexes that point to the primary key (no rowid to use as the lightweight pointer). And the primary key gets repeated in every secondary index. For tables with many secondary indexes and a non-trivial primary key, WITHOUT ROWID can be a loss; for primary-key-dominated lookup workloads, it's a clear win.

Overflow Pages

Storing payloads larger than a page.

A 4 KB page leaves room for cells whose payload is up to ~1023 bytes locally (after the header, cell pointer array, and other cell overhead). For larger payloads (a 10 KB BLOB, a long TEXT), SQLite splits:

cell on btree leaf:
  varint payload-length
  varint rowid
  first 1023 bytes of payload locally
  4-byte: page number of first overflow page

overflow page 1:
  4-byte: page number of next overflow page (or 0 if last)
  next chunk of payload (4092 bytes)

overflow page 2: ...
...

Reading a row with overflow: read the leaf cell, follow the chain of overflow pages until you've read the full payload. For a 10 KB BLOB on 4 KB pages, that's 1 leaf read + 3 overflow reads = 4 page reads. If the workload often reads big BLOBs, raising PRAGMA page_size to 16K or 32K (before any tables are created) reduces overflow chain depth.

Page Splits

When inserts exceed page capacity.

Insert into a full page → split:

1. allocate a new page (from freelist or by growing the file)
2. distribute cells between the two pages, ~50/50 by size
3. insert a divider cell into the parent page, pointing to the new page
4. if parent is also full, recursively split

cost: typically 1 new page write + 1 modified parent page
worst case: split cascades to root, root splits, tree grows by 1 level

Splits are uncommon in steady state — most pages have free space left over from earlier operations, and inserts fit. But during bulk inserts in random order, splits are frequent and concentrate writes. Bulk-insert workloads benefit hugely from sorted insertion (rowid order, or insert into a BEGIN; INSERT; COMMIT batch) so each new page fills up in one stretch instead of getting split repeatedly.

The Freelist

Recycling pages from deletions.

Deletes free pages — sometimes empty leaves, sometimes whole subtrees. SQLite doesn't truncate the file on every delete (too expensive). Instead, freed pages are linked into a freelist whose head is stored in the database header (offset 32, 4 bytes). The next allocation pops from this list before extending the file.

Without auto-vacuum, a database file never shrinks — only grows or stays the same size. Freelist pages are reused for new writes but if you've deleted 90% of your data, the file is still its peak size. VACUUM rewrites the entire database into a new file with no freelist, then renames atomically. PRAGMA auto_vacuum=FULL truncates after every commit at the cost of more I/O; INCREMENTAL shrinks lazily on PRAGMA incremental_vacuum(N).

FAQ