Every table and every index in an SQLite 2 file is a b-tree, and each node of it is one page. A b-tree page has an 8-byte header, then cells and free blocks anywhere in the rest of the page. The cells are not kept in an array: each one points to the cell with the next key, so the page is read by following the chain from the header.
Page header
The first 8 bytes of the page, the struct PageHdr in the 2.8.17
source. Numbers are in the file’s byte order.
| Offset | Size | Type | Name | Description |
|---|---|---|---|---|
| 0 | 4 | u32 | Right child | The child page with the keys after the last cell; 0 on a leaf page. |
| 4 | 2 | u16 | First cell | The offset, from the start of the page, of the cell with the smallest key; 0 when the page has no cells. |
| 6 | 2 | u16 | First free block | The offset of the first free block; 0 when there is none. |
Cells and free space
Bytes 8 to 1,023 hold cells and free
blocks, in any order by offset. Every structure starts at a 4-byte boundary and
takes a multiple of 4 bytes. A page holds at most 63 cells
(MX_CELL).
The cells form a list in key order: the header’s first cell, then each cell’s “next cell” field, until a 0 ends it. To read the cells of a page:
- Take the first cell offset from the page header. If it is 0, the page is empty.
- Read the cell there, and its next cell offset.
- Repeat with that offset until it is 0.
When SQLite reads a page it checks that each cell offset is from 8 to 1,008 and a multiple of 4, that each cell ends inside the page, that the free blocks come in increasing order of offset, and that their sizes add up to the space the cells do not use. Bytes that no cell or free block covers break that last rule; the explorer shows them as unaccounted.
Leaf and interior pages
On a leaf page every cell’s left child is 0, and so is the right child. An interior page holds entries too, not just pointers: a page with N cells has N + 1 children, in the order Ptr(0) Key(0) Ptr(1) Key(1) … Key(N − 1) Ptr(N). Ptr(k) is the left child of cell k, and Ptr(N) is the right child in the page header.
So to visit every entry of a b-tree in key order, for each cell in chain order visit its left child’s entries, then the cell itself; after the last cell, visit the right child’s entries.
SQLite 3 differs here: its b-tree pages carry a type byte and an array of cell pointers, and table interior pages hold no rows (see SQLite 3’s b-tree pages).
Free blocks
Unused space on the page is a chain of free blocks, the struct FreeBlk,
in increasing order of offset from the header’s first free block. Note the order:
the size comes first.
| Offset | Size | Type | Name | Description |
|---|---|---|---|---|
| 0 | 2 | u16 | Size | The size of the free block in bytes, these 4 included. |
| 2 | 2 | u16 | Next free block | The offset of the next free block, or 0 for the last. |
An empty page, as SQLite makes it, has first cell 0 and one free block from offset 8 to the end: 1,016 bytes.
Example
The start of a little-endian leaf page holding one row: rowid 1 of a table with the
values 'hi', NULL and '42'. The example is built from the
2.8.17 layout.
00000000 00 00 00 00 08 00 24 00 00 00 00 00 04 00 00 00
00000010 00 00 0A 00 80 00 00 01 04 07 07 0A 68 69 00 34
00000020 32 00 00 00 DC 03 00 00- 0 to 7, the page header: right child 0 (a leaf), first cell at offset 8, first
free block at offset 36 (
24 00). - 8 to 35, the cell: 12 bytes of cell header, 14 bytes of key and data and 2 bytes of padding. It is taken apart on the cells page.
- 36, the free block: size 988 (
DC 03), next 0. 8 + 28 + 988 = 1,024, so the page is fully accounted for.