5.6.2 · B+ tree order from block size, key size and pointer size

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

What do B+ internal nodes not store, compared with B-tree nodes? from Lesson 5.6.1
Give the B-tree node-size inequality. from Lesson 5.5.1
What is the multilevel search cost with t levels? from Lesson 5.3.3

1 · The Hook

"Block size 512 bytes, search key 9 bytes, block pointer 6 bytes, record pointer 7 bytes. What is the order of the B+ tree's internal nodes? Of its leaves?" GATE has asked this kind of question in many forms. Two inequalities answer all of them.

2 · Predict First

Block 512 bytes, key 9, block pointer 6. An internal node has p pointers and p − 1 keys. What is the largest p?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

6p + 9(p − 1) ≤ 512 → 15p ≤ 521 → p ≤ 34.7 → p = 34.

Internal node order p

p block pointers + (p − 1) keys:

p·P + (p − 1)·K ≤ B

Leaf order p_leaf

p_leaf ⟨key, record pointer⟩ entries + one next-leaf block pointer:

p_leaf·(K + Pr) + P ≤ B

(If the question says leaves hold data-block pointers instead, use P in place of Pr. If it says no sibling pointer, drop the + P.)

Running numbers

B	K	P	Pr	internal p	leaf p_leaf
512	9	6	7	⌊521/15⌋ = 34	⌊506/16⌋ = 31
1024	9	6	7	⌊1033/15⌋ = 68	⌊1018/16⌋ = 63
1024	9	6	7	B-tree: ⌊1040/22⌋ = 47

The B+ internal order (68) is much larger than the B-tree order (47): no record pointers.

Capacity of a B+ tree with h levels

Maximum records indexed: p^(h−1) × p_leaf (h − 1 internal levels of fan-out p, then full leaves).
Example (p = 68, p_leaf = 63): h = 3 → 68² × 63 = 291,312; h = 4 → 68³ × 63 = 19,809,216.
Minimum (half-full rules): root 2 children, internal ⌈p/2⌉ children, leaves ⌈p_leaf/2⌉ entries: 2 × ⌈p/2⌉^(h−2) × ⌈p_leaf/2⌉ for h ≥ 2. Example h = 3: 2 × 34 × 32 = 2,176.

"Order" in B+ tree questions

Most GATE B+ questions use order = max pointers (children) for internal nodes, and either give p_leaf separately or ask for it. If a question defines order as the maximum number of keys in a node, then max children = order + 1. Read the definition.

4 · Visual

Internal node (B = 512):  P K P K P ... K P        p pointers, p-1 keys
                          6p + 9(p-1) <= 512  ->  p = 34

Leaf node:                K Pr K Pr ... K Pr | P   p_leaf entries + next pointer
                          16 p_leaf + 6 <= 512 ->  p_leaf = 31

5 · Worked Examples

Example 1 Easy

B = 1024, K = 12, P = 8. Internal order p?

Solution

8p + 12(p − 1) ≤ 1024 → 20p ≤ 1036 → p = 51.

Example 2 Medium

B = 1024, K = 12, Pr = 10, P = 8. Leaf order p_leaf?

Solution

22 p_leaf + 8 ≤ 1024 → 22 p_leaf ≤ 1016 → p_leaf = 46.

Example 3 GATE

With p = 51 and p_leaf = 46, what is the maximum number of records a 3-level B+ tree can index? And the minimum number of block accesses to fetch one record through it (data block separate)?

Solution

51² × 46 = 2601 × 46 = 119,646 records. Access: 3 tree levels + 1 data block = 4.

6 · GATE Traps

Internal: p pointers and p − 1 keys. Leaf: p_leaf keys, p_leaf record pointers and one block pointer.
Use floor for the order.
Do not include record pointers in B+ internal nodes.
Max records = p^(h−1) × p_leaf, not p^h.
Check whether "order" counts keys or pointers.

7 · Memory Hook

"Inside: pointers fence the keys (p and p−1). Leaves: pairs plus one bridge."

8 · Connect the Dots

Lesson 5.6.1 described B+ trees; this lesson sized their nodes from bytes. Last lesson of the phase: inserting into and deleting from a B+ tree (leaf splits copy a key up; internal splits move it up) and the B-tree vs B+ tree summary.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 2 mark(s) — Internal order

B = 512, K = 9, P = 6. B+ tree internal order p?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — Leaf order

B = 512, K = 9, Pr = 7, P = 6. B+ tree leaf order p_leaf?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Capacity

p = 34 and p_leaf = 31. Maximum records indexed by a B+ tree with 3 levels?

Numerical answer: ________

Q4 · NAT · 2 mark(s) — Internal order

B = 4096, K = 16, P = 8. B+ tree internal order p?

Numerical answer: ________

Q5 · MCQ · 1 mark(s) — Comparison

For the same block size, key size and pointer sizes, which has the larger internal-node order?

(A) They are equal
(B) B-tree
(C) B+ tree
(D) Depends on the number of records

10 · Rule Card

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".

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

B+ tree internal order equationB+ tree leaf order equationB+ tree capacity p^(h−1)·p_leafminimum B+ tree capacity

12 · Answer Vault

Reveal answers when you’re ready

Recall Warm-up

Record pointers.
p·P + (p − 1)(K + Pr) ≤ B.
t + 1.