A · Compressed recap
An index is a sorted file of ⟨key, pointer⟩ entries: bfrᵢ = ⌊B/(K + P)⌋, bᵢ = ⌈entries/bfrᵢ⌉, one-level cost ⌈log₂ bᵢ⌉ + 1. Dense = entry per value (any file); sparse = entry per block (sorted file only). Primary (ordering key, sparse, entries = blocks), clustering (ordering non-key, sparse, entries = distinct values), secondary (non-ordering, dense, entries = records for a key; non-key adds an indirection block). At most one primary/clustering, many secondary.
Multilevel: index the index with fan-out fo until one block: t = ⌈log_fo r₁⌉ levels, cost t + 1. Static multilevel indexes are hard to update → B-trees.
B · Merged rule card
5.3.1 What an index is; index entries; dense vs sparse
- Index entry = ⟨key, pointer⟩; index sorted by key.
- bfrᵢ = ⌊B/(K + P)⌋; bᵢ = ⌈entries/bfrᵢ⌉; cost = ⌈log₂ bᵢ⌉ + 1.
- Dense: entry per search-key value (per record for a key); any file.
- Sparse: entry per block (anchor); data must be sorted on that field.
5.3.2 Primary, clustering, secondary indexes; counting index blocks and block accesses
- Primary: ordering key; sparse; entries = b.
- Clustering: ordering non-key; sparse; entries = distinct values (pointer to first block).
- Secondary: non-ordering field; dense; key → entries = r; non-key → indirection block (+1 access).
- At most one primary or clustering; many secondary.
- Cost = ⌈log₂ bᵢ⌉ + 1 (+1 for indirection).
5.3.3 Multilevel indexes; fan-out; logarithm primer
- 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.
C · Interleaved GATE-style questions
Q1 · NAT · 1 mark(s) — Index bfr
K = 12, P = 4, B = 2048. bfrᵢ?
Numerical answer: ________
Q2 · NAT · 2 mark(s) — Primary index
A file of 1,000,000 records with 40 records per block is sorted on its key. Primary index entries have bfrᵢ = 128. How many index blocks (single level)?
Numerical answer: ________
Q3 · NAT · 2 mark(s) — Multilevel
Same primary index made multilevel (fo = 128). How many block accesses to fetch a record?
Numerical answer: ________
Q4 · MCQ · 1 mark(s) — Types
A file sorted on dept (non-key) has an index on dept. It is a:
- (A) primary index
- (B) dense secondary index
- (C) clustering index
- (D) secondary index
Q5 · NAT · 2 mark(s) — Secondary
A secondary index on a key field of a file with 32,768 records has bfrᵢ = 128 and one level. Block accesses to fetch a record?
Numerical answer: ________
Q6 · NAT · 2 mark(s) — Multilevel
Same index made multilevel (fo = 128). Block accesses?
Numerical answer: ________
Q7 · MSQ · 2 mark(s) — Dense/sparse
Which are true?
- (A) A primary index is sparse.
- (B) Sparse indexes need the data sorted on the indexing field.
- (C) A secondary index on a key field is dense.
- (D) A clustering index has one entry per record.
Q8 · MCQ · 2 mark(s) — Cost
Compared with a single-level index of 442 blocks (fo = 68), a multilevel index on the same entries changes the search cost from:
- (A) 10 to 4
- (B) 442 to 4
- (C) 9 to 3
- (D) 10 to 3
D · Answer Vault
Reveal answers when you’re ready
Q1 Answer: 128 · 1 mark(s)
2048/16.
Re-read: Lesson 5.3.1 — What an index is; index entries; dense vs sparse
Q2 Answer: 196 · 2 mark(s)
b = 25,000; ⌈25000/128⌉ = 196 (128 × 195 = 24,960).
Re-read: Lesson 5.3.2 — Primary, clustering, secondary indexes; counting index blocks and block accesses
Q3 Answer: 4 · 2 mark(s)
Levels: 196 blocks, ⌈196/128⌉ = 2 blocks, then 1 block: 3 levels; 3 + 1 = 4.
Re-read: Lesson 5.3.3 — Multilevel indexes; fan-out; logarithm primer
Q4 Answer: (C) · 1 mark(s)
Ordering non-key.
- (A) is wrong: Needs a key.
- (B) is wrong: Clustering is sparse.
- (D) is wrong: Field is the ordering field.
Re-read: Lesson 5.3.2 — Primary, clustering, secondary indexes; counting index blocks and block accesses
Q5 Answer: 9 · 2 mark(s)
256 index blocks; ⌈log₂ 256⌉ + 1 = 9.
Re-read: Lesson 5.3.2 — Primary, clustering, secondary indexes; counting index blocks and block accesses
Q6 Answer: 4 · 2 mark(s)
Levels: 256, ⌈256/128⌉ = 2, then 1: 3 levels; 3 + 1 = 4.
Re-read: Lesson 5.3.3 — Multilevel indexes; fan-out; logarithm primer
Q7 Answer: (A) (B) (C) · 2 mark(s)
Clustering has one entry per distinct value.
- (D) is wrong: One per distinct value.
Re-read: Lesson 5.3.1 — What an index is; index entries; dense vs sparse
Q8 Answer: (A) · 2 mark(s)
Single: ⌈log₂ 442⌉ + 1 = 10. Multilevel: 3 levels + 1 = 4.
- (B) is wrong: Single level uses binary search, not a scan.
- (C) is wrong: Both forget the data block.
- (D) is wrong: Multilevel needs 3 index reads + 1.
Re-read: Lesson 5.3.3 — Multilevel indexes; fan-out; logarithm primer