5.3.2 · Primary, clustering, secondary indexes; counting index blocks and block accesses

0 · Recall Warm-up

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

What is bfrᵢ for K = 9, P = 6, B = 1024? from Lesson 5.3.1
Which index needs the data file sorted on the indexing field? from Lesson 5.3.1
How many block accesses does a heap search need on average for an existing key in 3,000 blocks? from Lesson 5.2.1

1 · The Hook

GATE index questions always name the index type: "a primary index", "a clustering index", "a secondary index on a non-key field". Each type fixes how many entries the index has, and from that everything else follows. Get the entry count right and the arithmetic is routine.

2 · Predict First

STUDENT (30,000 records, 3,000 blocks) is sorted on roll. You add an index on aadhaar (also unique, but the file is not sorted on it). How many entries does that index need: 3,000 or 30,000?

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

3 · Core Concept

Predict First — the answer

30,000. The file is not sorted on aadhaar, so the index must be dense: one entry per record. That is a secondary index.

The three single-level indexes

Index	Indexing field	Data file sorted on it?	Dense/sparse	Entries
Primary	ordering key field	yes	sparse	one per data block (b)
Clustering	ordering non-key field	yes	sparse	one per distinct value
Secondary	non-ordering field (key or not)	no	dense	key field: one per record (r)

Rules:

A file is sorted on at most one field, so it has at most one primary or clustering index (not both).
It can have many secondary indexes.

Clustering index details

The file is sorted on a non-key field (dept). Entry ⟨dept value, pointer to the first block containing that value⟩. Records with that value lie in consecutive blocks.

Secondary index on a non-key field

Several records share a value (many students in CS). Options: (a) one entry per record (repeated keys, dense); (b) variable-length entries holding all pointers; (c) one entry per distinct value, pointing to a block of record pointers (extra level of indirection). Option (c) is the textbook default; a search costs one extra access for the pointer block.

Counting: the running example

STUDENT: r = 30,000, B = 1024, R = 100 → b = 3,000. Index entry: K = 9, P = 6 → bfrᵢ = 68.

Index	Entries	Index blocks	Accesses to find one record
Primary on roll	3,000	⌈3000/68⌉ = 45	⌈log₂ 45⌉ + 1 = 6 + 1 = 7
Secondary on aadhaar	30,000	⌈30000/68⌉ = 442	⌈log₂ 442⌉ + 1 = 9 + 1 = 10
No index, linear on aadhaar			1,500 on average

Rules of thumb

Primary index entries = data blocks, not records.
Secondary index (key) entries = records.
Clustering index entries = distinct values of the field.
Each level of index search costs ⌈log₂ bᵢ⌉ with binary search; then +1 for the data block (+1 more for an indirection block, if any).

4 · Visual

PRIMARY (sparse)          CLUSTERING (sparse)           SECONDARY (dense)
data sorted on roll       data sorted on dept           data in any order
one entry per BLOCK       one entry per DEPT VALUE      one entry per RECORD
 1 -> b1                   CS -> first CS block           aadhaar 1001 -> rec ptr
11 -> b2                   EE -> first EE block           aadhaar 1002 -> rec ptr
...                        ME -> ...                      ...

5 · Worked Examples

Example 1 Easy

A file has 50,000 records in 5,000 blocks, sorted on the key. Primary index with bfrᵢ = 100. Index blocks? Accesses?

Solution

Entries 5,000 → 50 index blocks; ⌈log₂ 50⌉ + 1 = 6 + 1 = 7.

Example 2 Medium

Same file, a secondary index on another key field, bfrᵢ = 100. Index blocks? Accesses?

Solution

Entries 50,000 → 500 blocks; ⌈log₂ 500⌉ + 1 = 9 + 1 = 10.

Example 3 GATE

r = 16,384 records, R = 32 bytes, B = 1024, K = 6, P = 10 (unspanned). A secondary index on a key field. How many index blocks, and how many accesses to find a record?

Solution

Data: bfr = 32, b = 512. Index: bfrᵢ = ⌊1024/16⌋ = 64; entries 16,384 → 256 blocks; ⌈log₂ 256⌉ + 1 = 8 + 1 = 9.

6 · GATE Traps

Primary index: one entry per block. Secondary on key: one per record.
A file cannot have both a primary and a clustering index.
Primary index is on a key that the file is sorted on; clustering is on a sorted non-key field.
Secondary indexes do not require any ordering.

7 · Memory Hook

"Primary counts Blocks, Clustering counts Values, Secondary counts Records" → "B-V-R".

8 · Connect the Dots

Lesson 5.3.1 introduced dense and sparse indexes; this lesson named the three standard kinds and counted their blocks. A one-level index is still binary-searched. Next: index the index, again and again: multilevel indexes, the bridge to B-trees.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 2 mark(s) — Primary index

A file has 20,000 blocks sorted on its key; bfrᵢ = 50. How many blocks does the primary index have?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — Secondary index

The same file has 200,000 records; a secondary index on a key field has bfrᵢ = 50. Index blocks?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Accesses

With 4,000 secondary index blocks (single level), how many block accesses to fetch one record?

Numerical answer: ________

Q4 · MCQ · 1 mark(s) — Types

An index on the field the data file is sorted on, where that field is not a key, is a:

(A) hash index
(B) primary index
(C) clustering index
(D) secondary index

Q5 · MSQ · 2 mark(s) — Facts

Which are true?

(A) A primary index is sparse.
(B) A file can have several secondary indexes.
(C) A secondary index on a key field is dense.
(D) A file can have a primary and a clustering index at the same time.

10 · Rule Card

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

11 · Concept Ledger

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

primary indexclustering indexsecondary indexindirection blockat most one ordering index

12 · Answer Vault

Reveal answers when you’re ready

Recall Warm-up

A sparse index.
1,500.