Persist B-Trees to Disk with Fixed-Size Pages

Serialize Nodes to Fixed Pages

On-disk B-trees map each node to a page with a header (page id, type, checksum) followed by serialized keys and offsets. SQLite and PostgreSQL read exactly one page per tree level during a cache miss.

Page Layout Sketch

Header, key count, key array, child page ids, free space pointer for inserts.

c
Loading…

Little-endian wire format is common for portability
Slot directory at page end supports variable-length values
Deserialize validates checksum before trusting content
Keep node size <= PAGE_SIZE minus header

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

Trace first: walk one failing input step by step
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will serialize and deserialize a B-tree node into a byte buffer of fixed page size. This exercise requires round-tripping keys without loss and reporting bytes used.

Write a C program that serializes and deserializes B-tree nodes to fixed-size pages.

Requirements:

Define PAGE_SIZE as 128 bytes (small for demonstration)
Define a page header struct: page_id (int), is_leaf (int), num_keys (int), reserved (padding to 16 bytes)
Implement serialize_node(node, page_id, char* buffer) that writes:
- Header at offset 0
- Keys at offset 16 (4 bytes each)
- Values at offset 16 + MAX_KEYS*4 (4 bytes each)
- Child page IDs at offset 16 + MAX_KEYS*8 (4 bytes each, internal nodes only)
Implement deserialize_node(char* buffer) that reconstructs a node
Create a node: page_id=1, is_leaf=0, keys=[10, 20], values=[100, 200], children=[2, 3, 4]
Serialize it to a byte buffer and print the buffer as hex dump (16 bytes per line)
Deserialize the buffer back into a node
Print the deserialized node and verify it matches the original
Calculate and print the space utilization: bytes used / PAGE_SIZE
Include a note about why real databases use 4KB-16KB pages

Serialize Nodes to Fixed Pages

Page Layout Sketch

Header, key count, key array, child page ids, free space pointer for inserts.

c
Loading…

Little-endian wire format is common for portability
Slot directory at page end supports variable-length values
Deserialize validates checksum before trusting content
Keep node size <= PAGE_SIZE minus header

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

Trace first: walk one failing input step by step
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will serialize and deserialize a B-tree node into a byte buffer of fixed page size. This exercise requires round-tripping keys without loss and reporting bytes used.

Write a C program that serializes and deserializes B-tree nodes to fixed-size pages.

Requirements:

Define PAGE_SIZE as 128 bytes (small for demonstration)
Define a page header struct: page_id (int), is_leaf (int), num_keys (int), reserved (padding to 16 bytes)
Implement serialize_node(node, page_id, char* buffer) that writes:
- Header at offset 0
- Keys at offset 16 (4 bytes each)
- Values at offset 16 + MAX_KEYS*4 (4 bytes each)
- Child page IDs at offset 16 + MAX_KEYS*8 (4 bytes each, internal nodes only)
Implement deserialize_node(char* buffer) that reconstructs a node
Create a node: page_id=1, is_leaf=0, keys=[10, 20], values=[100, 200], children=[2, 3, 4]
Serialize it to a byte buffer and print the buffer as hex dump (16 bytes per line)
Deserialize the buffer back into a node
Print the deserialized node and verify it matches the original
Calculate and print the space utilization: bytes used / PAGE_SIZE
Include a note about why real databases use 4KB-16KB pages

Topic Overview

Serialize Nodes to Fixed Pages

Page Layout Sketch

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source

Persist B-Trees to Disk with Fixed-Size Pages

Topic Overview

Serialize Nodes to Fixed Pages

Page Layout Sketch

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source