Storage Engines & DatabasesB-TreesHard

Persist B-Trees to Disk with Fixed-Size Pages

Master the fundamental concepts of b-trees through this focused micro-challenge.

~90 minutes B-Trees Ready to learn

Topic Overview

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.

Implementation Task

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

Progressive Hints

Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.

Resources

B-Tree On-Disk Layout

Learn by building

Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.

How it works

Storage Engines & DatabasesB-TreesHard

Persist B-Trees to Disk with Fixed-Size Pages

Master the fundamental concepts of b-trees through this focused micro-challenge.

Open Editor

~90 minutes B-Trees Ready to learn

Topic Overview

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.

Implementation Task

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

Progressive Hints

Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.

Resources

B-Tree On-Disk Layout

Learn by building

Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.

How it works