Storage Engines & DatabasesB-TreesMedium

B-Tree Node Structure

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

~45 minutes B-Trees Ready to learn

Topic Overview

Nodes Sized for Disk Pages

B-tree nodes pack sorted keys and child pointers in a fixed fanout so each node fits one disk page (commonly 4KB/8KB). PostgreSQL B-Tree pages, SQLite table b-trees, and InnoDB indexes share this on-disk shape even when in-memory prototypes use smaller degrees for teaching.

Typical In-Memory Layout

Leaf flag, key count, parallel arrays of keys and values or child pointers, plus parent link if mutable.

c
Loading…

Minimum degree t means keys per node between t-1 and 2t-1 (except root)
Keep keys sorted for binary search within the node
Disk pages add header checksums and sibling pointers in real engines
Fanout drives tree height: higher fanout, fewer I/Os per lookup

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 define a B-tree node struct and print its layout fields. This exercise requires showing how many keys fit given MAX_KEYS and page size constants.

Implementation Task

Your Task

Define a B-tree node with room for MAX_KEYS = 3 key/value pairs and MAX_KEYS + 1 child pointers, plus num_keys and is_leaf. Build this two-level tree:

root (internal): key 20 → value 200, children left and right;
left (leaf): 10 → 100, 15 → 150;
right (leaf): 25 → 250, 30 → 300.

Print the node or nodes selected on stdin. A node prints as LABEL: leaf|internal keys=N [k:v k:v] capacity=3.

Input

One word: leaf, keys, root or demo. Anything else behaves like demo.

Output

Print exactly these lines for each mode:

leaf: the left leaf, labelled Node

c
Loading…

keys: the left leaf, then its first key

c
Loading…

root: the root, labelled Root

c
Loading…

demo: the root, the left leaf, the right leaf, then the capacity

c
Loading…

Example

Input:

c
Loading…

Output:

c
Loading…

Requirements

Store keys in sorted order inside each node. print_node walks keys[0..num_keys).
Allocate nodes with calloc and free them all before exiting.

Hidden tests cover the first key, the root node and the whole tree.