RustSQLite

How it works

1. 01

   Parse the SQL by hand

   A tokenizer and a recursive-descent parser turn SQL into a statement, one function per grammar rule. WHERE clauses go through parse_or_expr, then parse_and_expr, then parse_comparison, so AND binds tighter than OR without a precedence table.

2. 02

   Encode each row as a SQLite record

   A row becomes a record: a header with one serial type per column, then the values. Integers take the smallest width that fits, and 0 and 1 store no bytes at all. Types and lengths are varints, SQLite's 1-to-9-byte integer encoding. Each record becomes a cell keyed by rowid, placed by walking the table B-tree from the root to the right leaf.
3. 03

   Split a page when it fills

   Pages are 4 KB. Cells pack in from the end of the page while a sorted array of 2-byte cell pointers grows from the header. When a new cell no longer fits, the leaf splits: the lower half stays, the upper half moves to a new page, and a copy of the left half's largest key goes up to the parent as the separator. That is SQLite's own convention, so sqlite3's integrity check passes however many pages a table spans. If the root splits, the new root's page number is written back to sqlite_schema. Deletes run the other way: a page that falls below a third full is merged into a sibling, or shares rows with it, so no empty page is left behind, and freed pages go on SQLite's freelist to be reused.
4. 04

   Keep SQLite's automatic indexes

   For every UNIQUE column, and every primary key that isn't an INTEGER PRIMARY KEY, SQLite keeps a hidden index named sqlite_autoindex_<table>_<n>. The engine writes the same one: a second B-tree in SQLite's index-page format, holding (value, rowid) records sorted the way SQLite compares them. Every insert, update and delete keeps it in step, and a duplicate is rejected by looking it up there. sqlite3 uses it for lookups, and its query plan says so.

5. 05

   Commit through a write-ahead log

   Statements don't write to the database file. Changed pages collect in a dirty list, and reads check that list, then the log, then the file. On commit, each dirty page is appended to the write-ahead log as a frame, and the last frame carries a commit flag. Either the whole batch counts or none of it does. ROLLBACK just drops the list.
6. 06

   Recover, then checkpoint

   On open, any frames after the last commit flag are discarded, so a transaction cut off mid-write disappears. A checkpoint copies the newest version of each page into the database file, updates the 100-byte header and empties the log. It runs once the log passes 1,000 committed frames, on .checkpoint, and when the database closes.