B-Tree Search

Top-Down Binary Search in Nodes

B-tree search starts at the root, binary-searches keys in the current node to pick a child pointer, and repeats until a leaf returns a value or reports missing. Height stays O(log n) because each node holds many keys.

Search Steps

For each node, find the first key greater than target; follow the left child of that key. On leaf, scan or binary search for exact match.

c
Loading…

Duplicate keys may live in linked leaf chains in some designs
Prefix compression shrinks internal nodes on disk
Cache pages in RAM so repeated searches avoid disk
Compare against binary search tree to see shallower trees

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 implement B-tree search from root to leaf and return the value or NOT_FOUND. This exercise asks you to trace one lookup path printing visited keys.

Write a C program that implements B-tree search.

Requirements:

Use the B-tree node structure from the previous task (MAX_KEYS=3)
Implement btree_search(node, key) that returns the value or -1 if not found
Use linear search within each node (simpler than binary search for small MAX_KEYS)
Build a B-tree manually with this structure: Root (internal): keys=[20, 50], children=[leafA, leafB, leafC] leafA: keys=[5, 10, 15], values=[50, 100, 150] leafB: keys=[25, 30, 40], values=[250, 300, 400] leafC: keys=[60, 70, 80], values=[600, 700, 800]
Search for these keys and print results: 5, 20, 30, 50, 100
For each search, print the path from root to leaf (which child was followed at each level)
Implement btree_search_range(node, min_key, max_key) that prints all key-value pairs in range
Test range search with min=15, max=60
Calculate and print the number of nodes visited for each search

Top-Down Binary Search in Nodes

Search Steps

For each node, find the first key greater than target; follow the left child of that key. On leaf, scan or binary search for exact match.

c
Loading…

Duplicate keys may live in linked leaf chains in some designs
Prefix compression shrinks internal nodes on disk
Cache pages in RAM so repeated searches avoid disk
Compare against binary search tree to see shallower trees

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 implement B-tree search from root to leaf and return the value or NOT_FOUND. This exercise asks you to trace one lookup path printing visited keys.

Write a C program that implements B-tree search.

Requirements:

Use the B-tree node structure from the previous task (MAX_KEYS=3)
Implement btree_search(node, key) that returns the value or -1 if not found
Use linear search within each node (simpler than binary search for small MAX_KEYS)
Build a B-tree manually with this structure: Root (internal): keys=[20, 50], children=[leafA, leafB, leafC] leafA: keys=[5, 10, 15], values=[50, 100, 150] leafB: keys=[25, 30, 40], values=[250, 300, 400] leafC: keys=[60, 70, 80], values=[600, 700, 800]
Search for these keys and print results: 5, 20, 30, 50, 100
For each search, print the path from root to leaf (which child was followed at each level)
Implement btree_search_range(node, min_key, max_key) that prints all key-value pairs in range
Test range search with min=15, max=60
Calculate and print the number of nodes visited for each search

Topic Overview

Top-Down Binary Search in Nodes

Search Steps

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source

B-Tree Search

Topic Overview

Top-Down Binary Search in Nodes

Search Steps

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source