storage-format

Source excerpt starting at line 1.

1---2name: storage-format3description: SQLite file format, B-trees, pages, cells, overflow, freelist that is used in tursodb4---5# Storage Format Guide6 7## Database File Structure8 9```10┌─────────────────────────────┐11│ Page 1: Header + Schema     │  ← First 100 bytes = DB header12├─────────────────────────────┤13│ Page 2..N: B-tree pages     │  ← Tables and indexes14│            Overflow pages   │15│            Freelist pages   │16└─────────────────────────────┘17```18 19Page size: power of 2, 512-65536 bytes. Default 4096.20 21## Database Header (First 100 Bytes)22 23| Offset | Size | Field |24|--------|------|-------|25| 0 | 16 | Magic: `"SQLite format 3\0"` |26| 16 | 2 | Page size (big-endian) |27| 18 | 1 | Write format version (1=rollback, 2=WAL) |28| 19 | 1 | Read format version |29| 24 | 4 | Change counter |30| 28 | 4 | Database size in pages |31| 32 | 4 | First freelist trunk page |32| 36 | 4 | Total freelist pages |33| 40 | 4 | Schema cookie |34| 56 | 4 | Text encoding (1=UTF8, 2=UTF16LE, 3=UTF16BE) |35 36All multi-byte integers: **big-endian**.37 38## Page Types39 40| Flag | Type | Purpose |41|------|------|---------|42| 0x02 | Interior index | Index B-tree internal node |43| 0x05 | Interior table | Table B-tree internal node |44| 0x0a | Leaf index | Index B-tree leaf |45| 0x0d | Leaf table | Table B-tree leaf |46| - | Overflow | Payload exceeding cell capacity |47| - | Freelist | Unused pages (trunk or leaf) |48 49## B-tree Structure50 51Two B-tree types:52- **Table B-tree**: 64-bit rowid keys, stores row data53- **Index B-tree**: Arbitrary keys (index columns + rowid)54 55```56Interior page:  [ptr0] key1 [ptr1] key2 [ptr2] ...57                   │         │         │58                   ▼         ▼         ▼59               child     child     child60               pages     pages     pages61 62Leaf page:     key1:data  key2:data  key3:data ...63```64 65Page 1 always root of `sqlite_schema` table.66 67## Cell Format68 69### Table Leaf Cell70```71[payload_size: varint] [rowid: varint] [payload] [overflow_ptr: u32?]72```73 74### Table Interior Cell75```76[left_child_page: u32] [rowid: varint]77```78 79### Index Cells80Similar but key is arbitrary (columns + rowid), not just rowid.81 82## Record Format (Payload)83 84```85[header_size: varint] [type1: varint] [type2: varint] ... [data1] [data2] ...86```87 88Serial types:89| Type | Meaning |90|------|---------|91| 0 | NULL |92| 1-4 | 1/2/3/4 byte signed int |93| 5 | 6 byte signed int |94| 6 | 8 byte signed int |95| 7 | IEEE 754 float |96| 8 | Integer 0 |97| 9 | Integer 1 |98| ≥12 even | BLOB, length=(N-12)/2 |99| ≥13 odd | Text, length=(N-13)/2 |100 101## Overflow Pages102 103When payload exceeds threshold, excess stored in overflow chain:104```105[next_page: u32] [data...]106```107Last page has next_page=0.108 109## Freelist110 111Linked list of trunk pages, each containing leaf page numbers:112```113Trunk: [next_trunk: u32] [leaf_count: u32] [leaf_pages: u32...]114```115 116## Turso Implementation117 118Key files:119- `core/storage/sqlite3_ondisk.rs` - On-disk format, `PageType` enum120- `core/storage/btree.rs` - B-tree operations (large file)121- `core/storage/pager.rs` - Page management122- `core/storage/buffer_pool.rs` - Page caching123 124## Debugging Storage125 126```bash127# Integrity check128cargo run --bin tursodb test.db "PRAGMA integrity_check;"129 130# Page count131cargo run --bin tursodb test.db "PRAGMA page_count;"132 133# Freelist info134cargo run --bin tursodb test.db "PRAGMA freelist_count;"135```136 137## References138 139- [SQLite File Format](https://sqlite.org/fileformat.html)140- [SQLite B-Tree Module](https://sqlite.org/btreemodule.html)141- [SQLite Internals: Pages & B-trees](https://fly.io/blog/sqlite-internals-btree/)142