B+ tree: internal vs leaf nodes, leaf chaining, range queries

0 · Recall Warm-up

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

1. What is the maximum number of keys in a B-tree of order p and height h? from Lesson 5.5.3
2. In a B-tree, can a search stop at an internal node? from Lesson 5.5.2
3. What is a sparse index? from Lesson 5.3.1

1 · The Hook

"All students with roll between 1,200 and 1,450." In a B-tree, the keys in that range are scattered over internal nodes and leaves: you must walk up and down the tree. A B+ tree keeps every key in the leaves, in order, and links the leaves left to right. A range query becomes: one descent, then a walk along the leaf chain. That is why real database systems use B+ trees.

2 · Predict First

In a B+ tree, the key 40 appears in an internal node. Must it also appear in a leaf?

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

3 · Core Concept

Predict First — the answer

Yes. In a B+ tree, internal nodes only guide the search; every key (with its record pointer) is stored in a leaf. Internal keys are copies used as separators.

Structure (order p for internal nodes, p_leaf for leaves)

Internal nodes

• Up to p child pointers and p − 1 keys; no record pointers.
• Non-root internal nodes have at least ⌈p/2⌉ children; the root at least 2 (unless it is the only node).
• Keys are separators: for a separator k, keys ≥ k go right (a common convention).

Leaf nodes

• Up to p_leaf entries ⟨key, record pointer⟩, sorted, plus one next-leaf pointer.
• Non-root leaves hold at least ⌈p_leaf/2⌉ entries.
• All leaves are on the same level and together contain every key in sorted order.

Search

Every search goes from the root down to a leaf (internal nodes never hold the record pointer). Cost = height (levels) + 1 block for the data record, unless the leaf stores the records themselves.

Range queries

1. Search for the low end of the range: reach the first leaf that may contain it.
2. Read entries and follow next-leaf pointers until a key exceeds the high end.

Cost = height + (number of extra leaves read) (+ data blocks).

B+ tree as a multilevel index

The leaf level is a dense index (one entry per record, sorted), and the internal levels form a sparse multilevel index over the leaves: exactly Lesson 5.3.3, made dynamic and balanced.

4 · Visual

A B+ tree (max 2 keys per node). Internal keys 30, 50, 70 are copies; every key appears in a leaf, and the leaves are chained left to right (dashed arrows) for range scans.

5 · Worked Examples

Example 1 Easy

In the tree above, which nodes are visited to find 60? To list all keys from 25 to 65?

Solution

60: [50] → [70] → leaf [50 60]: 3 nodes. Range 25–65: descend [50] → [30] → leaf [10 20] (25 < 30), skip 10 and 20, then follow the chain: [30 40], [50 60], and [70] (70 > 65 stops). 4 leaves read; output 30, 40, 50, 60.

Example 2 Medium

Why does a B+ tree usually have a smaller height than a B-tree on the same block size?

Solution

Internal B+ nodes hold no record pointers, so more keys and child pointers fit per block: higher fan-out → fewer levels.

Example 3 GATE

A B+ tree has 3 levels; each leaf holds about 60 entries. A range query matches 600 records whose keys are consecutive. About how many index block accesses are needed (excluding data blocks)?

Solution

3 to reach the first leaf, then about 600/60 = 10 leaves in all, so about 2 + 10 = 12 (the first leaf counted once). The exact count depends on where the range starts inside the first leaf.

8 · Connect the Dots

Chapter 5.5 built B-trees; this lesson moved all data to linked leaves. Next: computing the two orders of a B+ tree (internal and leaf) from block, key and pointer sizes, GATE's most common B+ tree question.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — Structure

In a B+ tree, record pointers are stored in:

1. (A) both internal and leaf nodes
2. (B) internal nodes only
3. (C) the root only
4. (D) leaf nodes only

Q2 · MCQ · 1 mark(s) — Search

In a B+ tree of height 4, a successful search for a key reads how many tree nodes?

1. (A) at most 3
2. (B) exactly 4
3. (C) exactly 1
4. (D) between 1 and 4

Q3 · MSQ · 2 mark(s) — Properties

Which are true of B+ trees?

1. (A) Internal node keys may also appear in leaves.
2. (B) A key can appear only once in the whole tree.
3. (C) Leaves are linked for sequential access.
4. (D) Every key appears in some leaf.

Q4 · NAT · 2 mark(s) — Range

In the 3-level example tree (leaves [10 20], [30 40], [50 60], [70]), how many leaves are read to answer "keys from 15 to 55"?

Numerical answer: ________

Q5 · MCQ · 1 mark(s) — Why

B+ trees are preferred for range queries because:

1. (A) they use hashing
2. (B) they have no root
3. (C) their internal nodes store records
4. (D) their leaves are sorted and chained

11 · Concept Ledger

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

B+ treeinternal (index) nodeleaf nodeseparator keynext-leaf pointerleaf chainrange query in B+ treep and p_leaf