Disk Serialization — Read & Write Pages

So far our data lives in memory. Now we serialize pages to a binary format and read them back — the bridge between RAM and persistent storage.

The Database File Layout

A database file is a sequence of fixed-size pages:

+--------+--------+--------+--------+-----+
| Page 0 | Page 1 | Page 2 | Page 3 | ... |
+--------+--------+--------+--------+-----+
  4096B    4096B    4096B    4096B

To read page N: seek to offset N * page_size and read page_size bytes.

Binary Encoding

Each field is encoded at a fixed byte offset using a specific integer size:

Byte 0:      Page type (1 byte: 0x0D=leaf, 0x05=internal)
Bytes 1-2:   Cell count (2 bytes, big-endian)
Bytes 3-4:   Free space offset (2 bytes)
Bytes 5-6:   First cell offset (2 bytes)
Byte 7:      Reserved
Bytes 8+:    Cell pointer array (2 bytes each)

Big-endian encoding means the most significant byte comes first. SQLite uses big-endian for all multi-byte integers in the file format (even though most CPUs are little-endian).

Encoding Integers

Variable-Length Integers (Varints)

SQLite uses varints for payload sizes — a variable-length encoding where small values use fewer bytes:

Value      Encoding     Bytes Used
0-240      [value]      1 byte
241-2287   [241+hi,lo]  2 bytes

This saves space: most rowids and payload sizes fit in 1-2 bytes.

Cell Serialization

Each cell in the page is serialized as:

[payload_size: varint] [rowid: varint] [column data...]

Column data is encoded using SQLite's serial types:

• Type 0: NULL (0 bytes)
• Type 1: 8-bit integer (1 byte)
• Type 2: 16-bit integer (2 bytes)
• Type 4: 32-bit integer (4 bytes)
• Type N (N>=12, even): blob of (N-12)/2 bytes
• Type N (N>=13, odd): text of (N-13)/2 bytes

The Database File Header

Page 0 (the first page) contains a special 100-byte header:

Bytes 0-15:   Magic string "SQLite format 3\000"
Bytes 16-17:  Page size (e.g., 4096)
Bytes 28-31:  File change counter
Bytes 44-47:  Schema cookie

Verifying Round-Trip

The test for serialization: write pages to a hex format, read them back, and verify all data is intact. This proves your encoding/decoding is correct.

Your Task

Implement DB SAVE (serialize all pages to hex) and DB LOAD (deserialize), verifying that data survives the round-trip.