Table B-Trees, Index B-Trees, Interior/Leaf Pages, and Cells

Learning outcomes

Chapter 10 used the word B-tree as a query-planning structure. Now we make that structure spatial. A B-tree is not one giant sorted array. It is a hierarchy of database pages. SQLite starts from a root page, uses separator keys in interior pages to choose a child, and eventually reaches leaf pages that hold table or index cells.

Root, interior, leaf: navigation rather than a flat scan

                         root page
                    [separator keys]
                    /      |       \
                   /       |        \
          interior page  interior page  ...
             /   \           /   \
            /     \         /     \
        leaf     leaf      leaf     leaf
       [cells]   [cells]   [cells]  [cells]

An interior page mainly helps choose a child page. A leaf page contains the terminal B-tree cells for that branch. Small tables and indexes may need only a single leaf root page; as content grows, SQLite splits pages and adds interior levels.

The exact balance, split choices, and cell packing are SQLite implementation work. Developers should reason from the documented format and observed page statistics, not attempt to predict every page number.

Ordinary rowid tables: rowid is the table B-tree key

For a normal rowid table, SQLite stores table rows in a table B-tree whose integer key is the rowid. If a column is declared exactly INTEGER PRIMARY KEY, Chapter 3 showed that the column aliases this rowid. The table payload contains the row’s non-rowid column values in SQLite’s record format.

DROP TABLE IF EXISTS btree_note;CREATE TABLE btree_note(  note_id INTEGER PRIMARY KEY,  device_code TEXT NOT NULL,  occurred_at TEXT NOT NULL,  status TEXT NOT NULL,  summary TEXT NOT NULL);SELECT name, type, rootpage, sqlFROM sqlite_schemaWHERE name='btree_note';

The rootpage column identifies the root B-tree page for ordinary table/index schema objects. It is useful for observation but should not be embedded as an application identifier: rebuilding or changing the file can move structures to different pages.

Index B-trees: ordered search keys plus row identity

A secondary index has its own B-tree. For a rowid table, the index record contains the indexed column values and normally the rowid as the final field needed to identify the underlying table row. That is why a non-covering secondary-index plan can be thought of as two navigations: find matching index entries, then use rowids to fetch table rows.

CREATE INDEX idx_btree_note_device_timeON btree_note(device_code, occurred_at DESC);SELECT name, type, rootpageFROM sqlite_schemaWHERE name IN ('btree_note','idx_btree_note_device_time')ORDER BY type DESC, name;PRAGMA index_xinfo('idx_btree_note_device_time');

PRAGMA index_xinfo exposes key columns plus auxiliary fields. In a rowid-table index, an auxiliary rowid entry often appears with a column rank of -1.

Composite and covering indexes become concrete

A composite index on (device_code, occurred_at) stores entries ordered first by device code and then by time within each device. A covering index simply stores enough values in that same index record to answer a particular query without returning to the table B-tree.

DROP INDEX IF EXISTS idx_btree_note_device_time;CREATE INDEX idx_btree_note_device_timeON btree_note(device_code, occurred_at DESC, status, summary);EXPLAIN QUERY PLANSELECT occurred_at, status, summaryFROM btree_noteWHERE device_code='PUMP-007'ORDER BY occurred_at DESC;

The word COVERING in EQP is a planner observation. On disk, there is no separate “covering-index” species—the ordinary index entry simply contains all the values this query needs.

Cells: small record containers inside B-tree pages

A cell is a variable-size unit stored on a B-tree page. Its exact fields depend on whether the page is a table/index and interior/leaf page. At this course level, use this mental model:

Lesson 3 will explain how payload that cannot fit locally spills onto overflow pages.

WITHOUT ROWID changes the table’s organizing key

A WITHOUT ROWID table does not have the hidden integer rowid B-tree. Instead, its table storage uses an index-style B-tree organized by the declared PRIMARY KEY. This can avoid duplicating a natural/composite primary key in both a rowid table and a separate uniqueness index, but it changes APIs and storage behavior as Chapter 3 discussed.

DROP TABLE IF EXISTS rowid_assignment;DROP TABLE IF EXISTS wr_assignment;CREATE TABLE rowid_assignment(  device_code TEXT NOT NULL,  tag TEXT NOT NULL,  value TEXT,  PRIMARY KEY(device_code,tag));CREATE TABLE wr_assignment(  device_code TEXT NOT NULL,  tag TEXT NOT NULL,  value TEXT,  PRIMARY KEY(device_code,tag)) WITHOUT ROWID;PRAGMA table_list('rowid_assignment');PRAGMA table_list('wr_assignment');PRAGMA index_list('rowid_assignment');PRAGMA index_list('wr_assignment');

The ordinary rowid version needs its rowid table plus a primary-key uniqueness structure. The WITHOUT ROWID version uses the primary key as the table’s B-tree key. Do not infer that one form is universally smaller or faster; measure your keys, rows, and workload.

Optional deep inspection: dbstat

The official dbstat virtual table is read-only and reports B-tree page usage: object name, page number, page type, cell count, payload bytes, unused bytes, largest payload, and page size. However, it is only available when SQLite was built with SQLITE_ENABLE_DBSTAT_VTAB.

SELECT sqlite_compileoption_used('ENABLE_DBSTAT_VTAB') AS has_dbstat;-- Run these only when has_dbstat = 1:SELECT name, path, pageno, pagetype, ncell, payload, unused, mx_payload, pgsizeFROM dbstatWHERE name IN ('btree_note','idx_btree_note_device_time')ORDER BY name, pathLIMIT 30;-- Aggregated view: one row per B-tree.SELECT name, pageno AS pages, payload, unused, mx_payload, pgsizeFROM dbstatWHERE aggregate=TRUE  AND name IN ('btree_note','idx_btree_note_device_time');

If dbstat is unavailable, the mandatory learning objectives still work: use sqlite_schema.rootpage, PRAGMA index_xinfo, PRAGMA page_count, and the conceptual diagrams. Never install or enable an extension just to satisfy this lesson.

Hands-on B-tree lab

Insert enough rows to give SQLite a reason to use multiple pages, then inspect the table and index. Your exact page numbers and tree depth are local observations.

WITH RECURSIVE seq(x) AS (  VALUES(1)  UNION ALL  SELECT x+1 FROM seq WHERE x<10000)INSERT INTO btree_note(device_code,occurred_at,status,summary)SELECT printf('DEV-%04d', (x%300)+1),       printf('2026-08-%02dT%02d:%02d:00Z',(x%28)+1,x%24,x%60),       CASE WHEN x%9=0 THEN 'open' ELSE 'closed' END,       printf('Storage observation %d',x)FROM seq;SELECT COUNT(*) FROM btree_note;SELECT name, rootpage FROM sqlite_schemaWHERE name IN ('btree_note','idx_btree_note_device_time');PRAGMA page_count;

Common misconceptions

Knowledge check and bridge

Production judgment and next step

You now know where a row or index entry lives conceptually, but not every record fits entirely on its leaf page. Lesson 3 follows large TEXT/BLOB payloads into overflow chains and turns “wide rows cost more” into a measured storage experiment.

Authoritative references

• SQLite — Database File Format: B-tree pages and cells.
• SQLite — DBSTAT Virtual Table.
• SQLite — WITHOUT ROWID.
• SQLite — PRAGMA index_xinfo.