B-Tree Node Structure

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.

Write a C program that defines and prints a B-tree node structure.

Requirements:

Define MAX_KEYS as 3 (for demonstration; real databases use much larger)
Define a BTreeNode struct with:
- int keys[MAX_KEYS]
- int values[MAX_KEYS]
- struct BTreeNode* children[MAX_KEYS + 1]
- int num_keys
- int is_leaf
Implement create_node() that allocates and initializes a node
Implement print_node() that shows:
- Whether the node is a leaf or internal
- All keys and values
- Number of children (if internal)
Create and print three example nodes:
- Root (internal): keys=[10, 20], values=[100, 200], children=[leaf1, leaf2, leaf3]
- Leaf1: keys=[1, 5, 8], values=[10, 50, 80], is_leaf=1
- Leaf2: keys=[12, 15, 18], values=[120, 150, 180], is_leaf=1
- Leaf3: keys=[25, 30], values=[250, 300], is_leaf=1
Print the tree structure showing parent-child relationships
Calculate and print the maximum number of keys a tree of height 2 can hold with MAX_KEYS=3
Include a note about why real databases use larger MAX_KEYS

Nodes Sized for Disk Pages

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.

Write a C program that defines and prints a B-tree node structure.

Requirements:

Define MAX_KEYS as 3 (for demonstration; real databases use much larger)
Define a BTreeNode struct with:
- int keys[MAX_KEYS]
- int values[MAX_KEYS]
- struct BTreeNode* children[MAX_KEYS + 1]
- int num_keys
- int is_leaf
Implement create_node() that allocates and initializes a node
Implement print_node() that shows:
- Whether the node is a leaf or internal
- All keys and values
- Number of children (if internal)
Create and print three example nodes:
- Root (internal): keys=[10, 20], values=[100, 200], children=[leaf1, leaf2, leaf3]
- Leaf1: keys=[1, 5, 8], values=[10, 50, 80], is_leaf=1
- Leaf2: keys=[12, 15, 18], values=[120, 150, 180], is_leaf=1
- Leaf3: keys=[25, 30], values=[250, 300], is_leaf=1
Print the tree structure showing parent-child relationships
Calculate and print the maximum number of keys a tree of height 2 can hold with MAX_KEYS=3
Include a note about why real databases use larger MAX_KEYS

Topic Overview

Nodes Sized for Disk Pages

Typical In-Memory Layout

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source

B-Tree Node Structure

Topic Overview

Nodes Sized for Disk Pages

Typical In-Memory Layout

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source