5.3.3 · Multilevel indexes; fan-out; logarithm primer

0 · Recall Warm-up

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

How many entries does a primary index have? from Lesson 5.3.2
How many entries does a secondary index on a key field have? from Lesson 5.3.2
What is ⌈log₂ 442⌉? from Lesson 5.2.1

1 · The Hook

A 442-block index still costs 9 binary-search reads. But an index is itself a sorted file, so it can have its own sparse index: 442 blocks need only 7 index blocks above them, and those 7 need 1 block above them. Now a search reads one block per level: 3 levels + the data block = 4. This is a multilevel index, and a B+ tree is just a multilevel index that stays balanced as data changes.

2 · Predict First

The secondary index on aadhaar has 442 blocks; each index block holds 68 entries (the fan-out). How many blocks does the second level need? The third?

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

3 · Core Concept

Predict First — the answer

Level 2: ⌈442 / 68⌉ = 7 blocks. Level 3: ⌈7 / 68⌉ = 1 block (the top). Three levels in all.

Logarithms in any base (primer)

log_b x is the power of b that gives x: log₆₈ 4624 = 2 because 68² = 4624.

⌈log_b x⌉ = the smallest k with bᵏ ≥ x.
Change of base: log_b x = log₂ x / log₂ b. (log₁₆ 65536 = 16 / 4 = 4.)
For index questions, compare with powers directly: 68¹ = 68, 68² = 4,624, 68³ = 314,432.

Multilevel index

Level 1 (bottom): the ordinary index on the data (any of the three kinds).
Level 2: a primary (sparse) index on level 1: one entry per level-1 block.
Repeat until a level fits in one block (the top level).

The fan-out fo = bfrᵢ = number of entries per index block. Each level is fo times smaller.

Number of levels t:

b₁ = ⌈r₁ / fo⌉ (r₁ = entries at level 1), b₂ = ⌈b₁ / fo⌉, … stop when bₜ = 1.
Equivalently t = ⌈log_fo r₁⌉.

Search cost = t + 1 block accesses (one per level + the data block). Compare with ⌈log₂ b₁⌉ + 1 for a single level.

Running example

Base index	r₁ (entries)	Levels	Blocks per level	Cost
Primary on roll	3,000	2	45, 1	2 + 1 = 3
Secondary on aadhaar	30,000	3	442, 7, 1	3 + 1 = 4

Check with logs: 68¹ = 68 < 3000 ≤ 4624 = 68² → t = 2. 68² < 30000 ≤ 68³ → t = 3.

Total index blocks for the secondary multilevel index = 442 + 7 + 1 = 450.

The problem with static multilevel indexes

Inserting and deleting records forces every level to be rewritten (each level is a sorted file). Leaving free space in index blocks helps for a while. The real fix is a dynamic, balanced multilevel index: the B-tree and B+ tree of Chapters 5.5–5.6. First we need tree vocabulary (Lesson 5.4.1).

4 · Visual

Multilevel secondary index (fan-out 68), 30,000 entries at level 1

level 3:  [ 1 block ]                         <- top: 1 access
level 2:  [ 7 blocks ]                        <- 1 access
level 1:  [ 442 blocks ]                      <- 1 access
data:     [ 3000 blocks ]                     <- 1 access     total 4  (vs 10 with one level)

5 · Worked Examples

Example 1 Easy

fo = 100, level-1 index has 50,000 entries. Number of levels and search cost?

Solution

100² = 10,000 < 50,000 ≤ 10⁶ = 100³ → 3 levels; cost 4.

Example 2 Medium

A primary index on a file of 20,000 blocks, fo = 50. Blocks at each level and total index blocks?

Solution

Level 1: 20,000/50 = 400; level 2: 400/50 = 8; level 3: 1. Total 409 index blocks, 3 levels, search cost 4.

Example 3 GATE

r = 300,000 records, a secondary index on a key, K = 9, P = 6, B = 512. Number of levels in the multilevel index and block accesses for a search?

Solution

fo = ⌊512/15⌋ = 34. 34³ = 39,304 < 300,000 ≤ 1,336,336 = 34⁴ → 4 levels; cost 5. (Blocks: 8,824 → 260 → 8 → 1.)

6 · GATE Traps

Level 1 entries depend on the index type (blocks for primary, records for secondary key).
Levels above level 1 are always sparse primary indexes on the level below.
Cost = number of levels + 1 (data block).
⌈log_fo r₁⌉, compared through powers of fo, not log₂.

7 · Memory Hook

"Index the index until one block is left; one read per floor, plus the ground."

8 · Connect the Dots

Lesson 5.3.2 built single-level indexes; this lesson stacked them into multilevel indexes with cost t + 1. They are fast but painful to update. Next: tree vocabulary, needed for the balanced, self-adjusting version: the B-tree.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Levels

fo = 50, level 1 has 2,000 entries. How many levels?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — Cost

fo = 64, a secondary index on a key field of a file with 100,000 records. Block accesses to fetch one record through the multilevel index?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Total blocks

fo = 64, 100,000 level-1 entries. Total number of index blocks in all levels?

Numerical answer: ________

Q4 · NAT · 1 mark(s) — Logs

What is ⌈log₁₀₀ 1,000,000⌉?

Numerical answer: ________

Q5 · MCQ · 1 mark(s) — Upper levels

Every level above the first in a multilevel index is a:

(A) hash index
(B) clustering index on the data
(C) dense secondary index on the level below
(D) sparse primary index on the level below

10 · Rule Card

log_b x: power of b giving x; ⌈log_b x⌉ = smallest k with bᵏ ≥ x; log_b x = log₂ x / log₂ b.
Multilevel: level 1 = base index; each higher level = sparse primary index on the one below; stop at one block.
fo = bfrᵢ; t = ⌈log_fo r₁⌉; cost = t + 1.
Static multilevel indexes are costly to update → B-trees.

11 · Concept Ledger

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

logarithm base b (primer)change of basemultilevel indexfan-out (fo)top levellevels t = ⌈log_fo r₁⌉static vs dynamic index

12 · Answer Vault

Reveal answers when you’re ready

Recall Warm-up

One per data block.
One per record.