Toy database in C

The entire database is stored in a single file!

The front-end

A query goes through a chain of components in order to retrieve or modify data. The front-end consists of the:

1. tokenizer
2. parser
3. code generator

The input to the front-end is a SQL query. the output is sqlite virtual machine bytecod (essentially a compiled program that can operate on the database).

The back-end

4. virtual machine
5. B-tree
6. pager
7. os interface

The virtual machine takes bytecode generated by the front-end as instructions. It can then perform operations on one or more tables or indexes, each of which is stored in a data structure called a B-tree.

The VM is essentially a big switch statement on the type of bytecode instruction.

Each B-tree consists of many nodes. Each node is one page in length. The B-tree can retrieve a page from disk or save it back to disk by issuing commands to the pager.

The “front-end” of sqlite is a SQL compiler that parses a string and outputs an internal representation called bytecode.

Questions

• What format is data saved in? (in memory and on disk)
• When does it move from memory to disk?
• Why can there only be one primary key per table?
• How does rolling back a transaction work?
• How are indexes formatted?
• When and how does a full table scan happen?
• What format is a prepared statement saved in?