5.5.1 · B-tree structure and order (order conventions and the GATE trap)

0 · Recall Warm-up

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

How many keys and children can a node of an m-way search tree hold? from Lesson 5.4.1
What does "balanced" mean for a tree? from Lesson 5.4.1
Fan-out 68, 30,000 entries: how many index levels? from Lesson 5.3.3

1 · The Hook

A B-tree is a balanced m-way search tree in which every node except the root is at least half full. That rule keeps the tree shallow no matter how records are inserted or deleted. The word "order" sets the size of the nodes, and GATE uses it in two different ways. Read the question's definition before computing.

2 · Predict First

A B-tree has order p = 5, meaning a node has at most 5 children. At most how many keys can a node hold? At least how many children must a non-root internal node have?

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

3 · Core Concept

Predict First — the answer

At most p − 1 = 4 keys. At least ⌈p/2⌉ = 3 children (so at least 2 keys).

B-tree of order p (p = maximum number of children)

Every node holds up to p − 1 keys in sorted order and up to p child pointers, plus, for each key, a data (record) pointer.
Every internal node except the root has at least ⌈p/2⌉ children (so at least ⌈p/2⌉ − 1 keys).
The root has at least 2 children, unless it is a leaf (then it may hold just 1 key).
An internal node with k keys has k + 1 children.
All leaves are at the same level (balanced).
Search-tree order: keys in the i-th subtree lie between the (i−1)-th and i-th keys of the node.

Every key appears exactly once in the tree, with its data pointer, in internal nodes or leaves.

The order trap: three conventions

Convention	Who uses it	"Order" means	Keys per non-root node
Max children p	Knuth, Elmasri–Navathe, most GATE block-size questions	max children	⌈p/2⌉ − 1 to p − 1
Min keys d	Bayer–McCreight, some older papers	min keys	d to 2d (max children 2d + 1)
Min degree t	CLRS	min children	t − 1 to 2t − 1

How to tell: if the question says "order p … at most p pointers" or computes order from block size with p pointers, it is max children. If it says "each node has between d and 2d keys", it is min keys. When a GATE question is ambiguous, the official answers have used the max-children convention for size-based questions.

Order from the block size (B-tree)

A node with order p has p block pointers (P bytes each), p − 1 keys (K bytes each) and p − 1 record pointers (Pr bytes each):

p·P + (p − 1)(K + Pr) ≤ B → take the largest whole p.

Example: B = 1024, K = 9, P = 6, Pr = 7: 6p + 16(p − 1) ≤ 1024 → 22p ≤ 1040 → p = 47.

Leaves

Leaves have the same layout; their child pointers are NULL. (Some textbooks store data only in leaves; that is the B+ tree of Chapter 5.6.)

4 · Visual

A B-tree of order 5 (at most 4 keys, at most 5 children). Every non-root node has at least 2 keys (3 children); all leaves are on level 2. Each key also carries a pointer to its record.

5 · Worked Examples

Example 1 Easy

Order p = 7 (max children). Max keys per node? Min children and min keys for a non-root internal node? Min keys in the root?

Solution

Max keys 6. Min children ⌈7/2⌉ = 4, min keys 3. Root: at least 1 key (2 children).

Example 2 Medium

B = 512, K = 10, P = 8, Pr = 8. Order p of a B-tree (max children)?

Solution

8p + 18(p − 1) ≤ 512 → 26p ≤ 530 → p = 20.

Example 3 GATE

A question says: "a B-tree of order 3 in which every non-root node holds between 3 and 6 keys". Which convention is it, and what is the maximum number of children?

Solution

"Between d and 2d keys" with d = 3: the min-keys convention. Max keys 6 → max children 7.

6 · GATE Traps

Order p (max children) → max keys p − 1, min children ⌈p/2⌉ (non-root), min keys ⌈p/2⌉ − 1.
The root is exempt from the minimum: it may have 2 children (1 key).
B-tree nodes carry record pointers for every key; forget them and the order comes out too big.
Check the convention: max children, min keys, or min degree.

7 · Memory Hook

"Half-full or better, except the boss." Every node but the root is at least half full; all leaves stand on the same floor.

8 · Connect the Dots

Lesson 5.4.1 gave tree vocabulary; this lesson defined the B-tree and its order. Next: how a B-tree grows: searching, inserting, and splitting a full node, which is how the tree stays balanced.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Keys

B-tree of order 9 (max children). Maximum keys in a node?

Numerical answer: ________

Q2 · NAT · 1 mark(s) — Min keys

B-tree of order 9 (max children). Minimum keys in a non-root node?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Order

B = 1024, K = 9, P = 6, Pr = 7. Largest order p (max children) of a B-tree node?

Numerical answer: ________

Q4 · MCQ · 1 mark(s) — Root

The root of a B-tree (when it is not a leaf) must have at least:

(A) 2 children
(B) ⌈p/2⌉ children
(C) 1 child
(D) p − 1 children

Q5 · MCQ · 2 mark(s) — Convention

"A B-tree where each node except the root has between t − 1 and 2t − 1 keys" uses:

(A) Knuth's max-children order
(B) CLRS minimum degree t
(C) Bayer–McCreight minimum keys d
(D) B+ tree order

10 · Rule Card

B-tree order p (max children): ≤ p − 1 keys; non-root internal ≥ ⌈p/2⌉ children; root ≥ 2 children unless leaf; all leaves same level.
Each key appears once, with a record pointer.
Node size: p·P + (p − 1)(K + Pr) ≤ B.
Conventions: max children p; min keys d (d..2d keys); min degree t (t−1..2t−1 keys).

11 · Concept Ledger

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

B-treeorder (max children)minimum fill (⌈p/2⌉)root exemptionrecord pointer in B-tree nodesB-tree node size equationorder conventions (Knuth, Bayer–McCreight, CLRS)

12 · Answer Vault

Reveal answers when you’re ready

Recall Warm-up

At most m − 1 keys and m children.
All leaves are at the same level.