A · Compressed recap
B+ tree: internal nodes hold ≤ p child pointers and ≤ p − 1 separator keys, no record pointers; leaves hold ≤ p_leaf ⟨key, Pr⟩ entries + a next-leaf pointer; all keys are in leaves; every search ends at a leaf; ranges walk the leaf chain. Orders: p·P + (p − 1)K ≤ B and p_leaf(K + Pr) + P ≤ B. Capacity with h levels: max p^(h−1)·p_leaf; min 2⌈p/2⌉^(h−2)⌈p_leaf/2⌉.
Insert: leaf overflow splits and copies the right leaf's first key up; internal overflow moves its middle key up; root split grows height. Delete: borrow (update separator) or merge (drop separator). B+ trees beat B-trees on fan-out and ranges.
B · Merged rule card
5.6.1 B+ tree: internal vs leaf nodes, leaf chaining, range queries
- Internal: ≤ p children, ≤ p − 1 keys, no record pointers; non-root ≥ ⌈p/2⌉ children.
- Leaves: ≤ p_leaf ⟨key, Pr⟩ entries + next pointer; non-root ≥ ⌈p_leaf/2⌉ entries; all keys here, sorted.
- Search always reaches a leaf (cost = height).
- Range: descend to the low key, then follow leaf links.
- Leaf level = dense index; internal levels = sparse multilevel index.
5.6.2 B+ tree order from block size, key size and pointer size
- Internal: p·P + (p − 1)K ≤ B. Leaf: p_leaf(K + Pr) + P ≤ B.
- Max records with h levels: p^(h−1)·p_leaf. Min: 2⌈p/2⌉^(h−2)⌈p_leaf/2⌉.
- B+ internal order > B-tree order for the same sizes.
- Check the question's definition of "order".
5.6.3 B+ tree insertion and deletion traces; height and capacity; B vs B+
- Insert into leaf; leaf overflow → split (left keeps ⌈(p_leaf+1)/2⌉), copy right's first key up; internal overflow → split, move middle key up; root split → height + 1.
- Delete from leaf; underflow → borrow (update separator) or merge (remove separator); separators may be stale.
- B vs B+: record pointers everywhere vs leaves only; lower vs higher fan-out; awkward vs easy ranges; median up vs copy up.
C · Interleaved GATE-style questions
Q1 · NAT · 2 mark(s) — Internal order
B = 2048, K = 12, P = 4. B+ internal order p?
Numerical answer: ________
Q2 · NAT · 2 mark(s) — Leaf order
B = 2048, K = 12, Pr = 8, P = 4. B+ leaf order p_leaf?
Numerical answer: ________
Q3 · NAT · 2 mark(s) — Capacity
p = 128, p_leaf = 102, h = 2 levels. Maximum records?
Numerical answer: ________
Q4 · MCQ · 1 mark(s) — Search
A B+ tree has height 3. A search for a key that is a separator in the root reads:
- (A) 2 nodes
- (B) 3 nodes
- (C) it depends on the key
- (D) 1 node
Q5 · NAT · 2 mark(s) — Splits
B+ tree with at most 2 keys per node. Insert 10, 20, 30, 40, 50, 60, 70. Total splits?
Numerical answer: ________
Q6 · MCQ · 2 mark(s) — Copy vs move
After inserting 10 … 70 (at most 2 keys per node), how many times does 50 appear in the tree?
- (A) once
- (B) twice (root and a leaf)
- (C) three times
- (D) not at all
Q7 · MCQ · 1 mark(s) — Leaves
The leaf level of a B+ tree is equivalent to:
- (A) a sparse index
- (B) the data file itself, always
- (C) a hash table
- (D) a dense index on the search key
Q8 · MSQ · 2 mark(s) — Facts
Which are true?
- (A) Non-root leaves are at least half full.
- (B) All leaves are on the same level.
- (C) Leaves are chained.
- (D) B+ internal nodes contain record pointers.
D · Answer Vault
Reveal answers when you’re ready
Q1 Answer: 128 · 2 mark(s)
4p + 12(p − 1) ≤ 2048 → 16p ≤ 2060 → 128.
Re-read: Lesson 5.6.2 — B+ tree order from block size, key size and pointer size
Q2 Answer: 102 · 2 mark(s)
20 p_leaf ≤ 2044 → 102.
Re-read: Lesson 5.6.2 — B+ tree order from block size, key size and pointer size
Q3 Answer: 13056 · 2 mark(s)
128 × 102.
Re-read: Lesson 5.6.2 — B+ tree order from block size, key size and pointer size
Q4 Answer: (B) · 1 mark(s)
Every search ends at a leaf.
- (A) is wrong: No.
- (C) is wrong: Always the height.
- (D) is wrong: The root has no record pointer.
Re-read: Lesson 5.6.1 — B+ tree: internal vs leaf nodes, leaf chaining, range queries
Q5 Answer: 4 · 2 mark(s)
Traced in Lesson 5.6.3.
Re-read: Lesson 5.6.3 — B+ tree insertion and deletion traces; height and capacity; B vs B+
Q6 Answer: (B) · 2 mark(s)
Copied up from the leaf split, then moved from the old root to the new root.
- (A) is wrong: It is also in a leaf.
- (C) is wrong: The internal copy moved, not duplicated.
- (D) is wrong: It is present.
Re-read: Lesson 5.6.3 — B+ tree insertion and deletion traces; height and capacity; B vs B+
Q7 Answer: (D) · 1 mark(s)
One entry per key.
- (A) is wrong: Upper levels are sparse.
- (B) is wrong: Usually entries point to records.
- (C) is wrong: No.
Re-read: Lesson 5.6.1 — B+ tree: internal vs leaf nodes, leaf chaining, range queries
Q8 Answer: (A) (B) (C) · 2 mark(s)
Internal nodes hold no record pointers.
- (D) is wrong: False.
Re-read: Lesson 5.6.1 — B+ tree: internal vs leaf nodes, leaf chaining, range queries