Loading page…
Master the fundamental concepts of b-trees through this focused micro-challenge.
You have read the whole brief, and the concepts above stay free on every task. Writing and running the code needs a plan.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksOn-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.
Header, key count, key array, child page ids, free space pointer for inserts.
cLoading…
PAGE_SIZE minus headerKeep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.
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.
Databases store B-tree nodes in fixed-size pages. Serialize this node into a 64-byte page by copying the struct { int page_id, is_leaf, num_keys; int keys[3], values[3], children[4]; } (4-byte little-endian ints, zero padding after it), then read it back:
Print the view selected on stdin.
One word: hex, deser, children or all. Anything else behaves like all.
Print exactly these lines for each mode:
hex: the first 16 bytes of the page as lowercase hex
cLoading…
deser: copy the page back into a struct and print some fields
cLoading…
children: the child page ids (-1 = none)
cLoading…
all: the first 8 bytes, the header fields, and the key utilization num_keys / MAX_KEYS as a percentage with 1 decimal
cLoading…
Input:
cLoading…
Output:
cLoading…
Hidden tests cover deserialization, the child ids and the summary.