7.3B-tree and B+ tree: order, height, node counts
The idea
A B+ tree is a balanced search tree for disks. Order p means an internal node has up to p child pointers and p − 1 keys. All record pointers sit in the leaves.
Think of it like this: A phone book with thick tabs: few steps (high fan-out) get you to the right page.
Why it exists
You compute the order from the block size and the tree height from the record count.
How it works
- Internal node: p·P + (p − 1)·K ≤ B, largest p that fits.
- Leaf: holds (key, record pointer) pairs plus one next-leaf pointer: leaf·(K + D) + P ≤ B.
- Half full is the minimum: ⌈p/2⌉ children, ⌈leaf/2⌉ keys.
- Smallest height: all nodes full. Largest height: all nodes half full.
Worked example: B = 512, K = 8, P = 6.
p·6 + (p − 1)·8 ≤ 512 → 14p ≤ 520 → p = 37.
Now play with it
- →Change the block size in the calculator and watch p and the height change.
- →See how many levels a million keys need.
Internal node: p·P + (p − 1)·K ≤ B. Leaf node: leaf·(K + D) + P ≤ B (one pointer to the next leaf). Height range: all nodes full gives the minimum, all nodes half full gives the maximum.
Check yourself
Block = 1024 B, key = 10 B, block pointer = 8 B. The order of an internal node of a B+ tree is
Exam notes (the dense version)
In a B+ tree of order p an internal node has up to p pointers and p − 1 keys; leaves hold p − 1 (key, record pointer) pairs and a next-leaf pointer. Find the largest p with p · P + (p − 1) · K ≤ B (pointer size P, key size K). Minimum fill: internal nodes ⌈p/2⌉ children, leaves ⌈(p − 1)/2⌉ keys. Height h supports up to p^h leaf-level pointers (about (p − 1) · p^(h−1) keys). B+ trees store data pointers only in leaves, so internal nodes have a bigger fan-out than in a B-tree.
Previous year questions: File Organisation & Indexing (9)
PYQs are grouped by topic, so this is the full set for File Organisation & Indexing; try the ones that match this subtopic. Open all 9 on the topic page.