5.3.1 · What an index is; index entries; dense vs sparse

0 · Recall Warm-up

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

Block accesses for binary search over 3,000 blocks? from Lesson 5.2.1
Why can a sorted file not be binary-searched on a non-ordering field? from Lesson 5.2.1
What is a blocking factor? from Lesson 5.1.1

1 · The Hook

A book has 900 pages. To find "B+ tree" you do not read every page: you open the index at the back, find "B+ tree … 412", and jump. The index is small, sorted, and full of page numbers. A database index is exactly that: a small sorted file of (key, pointer) pairs.

2 · Predict First

An index entry has a 9-byte key and a 6-byte block pointer. A block holds 1,024 bytes. How many index entries fit in one block, compared with 10 data records?

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

3 · Core Concept

Predict First — the answer

⌊1024 / 15⌋ = 68 entries: almost 7 times more than data records. A small entry means many entries per block, so the index has few blocks and is fast to search.

Index

An index on a field (the indexing field or search key) is an auxiliary file of index entries ⟨key value, pointer⟩, kept sorted by key. To find a record: search the index (binary search over its blocks), follow the pointer, read the data block.

Index entry size = K + P (key size + pointer size).
Index blocking factor bfrᵢ = ⌊B / (K + P)⌋.
Index blocks bᵢ = ⌈(number of entries) / bfrᵢ⌉.
Search cost with one index level = ⌈log₂ bᵢ⌉ + 1 (binary search in the index, then one data block).

Dense and sparse indexes

Dense: one entry for every search-key value (for a key field: every record). Works on any file.
Sparse (non-dense): entries for only some values, typically one per data block: the first key of the block (the anchor). Works only if the data file is sorted on the indexing field: you find the last anchor ≤ the key and read that block.

	Dense	Sparse
Entries	one per record (key field)	one per block
Data file must be sorted on the field	no	yes
Size	bigger	smaller
Can answer "does key exist?" from the index alone	yes	no

Example

STUDENT: 30,000 records, 3,000 blocks, sorted on roll. Index entry = 9 + 6 = 15 bytes, bfrᵢ = 68.

Sparse index on roll: 3,000 entries → ⌈3000/68⌉ = 45 index blocks; search ⌈log₂ 45⌉ + 1 = 6 + 1 = 7 accesses (instead of 12 by binary search on the data).
Dense index on roll: 30,000 entries → ⌈30000/68⌉ = 442 blocks; search ⌈log₂ 442⌉ + 1 = 9 + 1 = 10.

4 · Visual

Sparse index (one entry per data block, data sorted)       data blocks
 key  -> block
   1  -> b1        ---------------------------------->     b1: 1 .. 10
  11  -> b2        ---------------------------------->     b2: 11 .. 20
  21  -> b3        ---------------------------------->     b3: 21 .. 30
 ...                                                        ...
find 27: last anchor <= 27 is 21 -> read b3

5 · Worked Examples

Example 1 Easy

Key 10 bytes, block pointer 6 bytes, B = 512. bfrᵢ?

Solution

⌊512 / 16⌋ = 32.

Example 2 Medium

A file has 6,000 blocks, sorted on its key. A sparse index has entries of 16 bytes and B = 512 (bfrᵢ = 32). Index blocks? Accesses for a search?

Solution

⌈6000/32⌉ = 188 index blocks. ⌈log₂ 188⌉ + 1 = 8 + 1 = 9.

Example 3 GATE

Why can a sparse index not be built on a field the data file is not sorted on?

Solution

A sparse index records only block anchors and relies on all records between two anchors lying in one block. Without sorting, a key could be in any block, so every value needs its own entry: the index must be dense.

6 · GATE Traps

bfrᵢ uses K + P, not the data record size.
Sparse needs sorted data; dense works on anything.
Search cost = index search + 1 for the data block.
A dense index on a key has one entry per record, not per block.

7 · Memory Hook

"Sparse marks the shelves, dense marks every book." Shelves only work if the books are in order.

8 · Connect the Dots

Lesson 5.2.1 found records by scanning, halving or hashing the data; this lesson searched a small sorted index instead. Next: the three standard kinds of single-level index (primary, clustering, secondary) and how to count their blocks and accesses.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Index bfr

K = 8 bytes, P = 8 bytes, B = 1024. bfrᵢ?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — Index blocks

A dense index on a key of a file with 40,000 records. bfrᵢ = 64. How many index blocks?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Search cost

With 625 index blocks (single level, binary search) plus the data block, how many block accesses?

Numerical answer: ________

Q4 · MCQ · 1 mark(s) — Sparse

A sparse index requires:

(A) the indexing field to be numeric
(B) a hashed data file
(C) the data file to be sorted on the indexing field
(D) one entry per record

Q5 · MSQ · 2 mark(s) — Dense vs sparse

Which are true?

(A) A sparse index can be built on any field.
(B) A sparse index is usually smaller than a dense index on the same field.
(C) A dense index has an entry for every search-key value.
(D) Search cost through a one-level index is its binary-search cost plus one data access.

10 · Rule Card

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.

11 · Concept Ledger

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

indexindexing field (search key)index entryindex blocking factor bfrᵢdense indexsparse indexblock anchor

12 · Answer Vault

Reveal answers when you’re ready

Recall Warm-up

The records are not in order of that field.
The number of records per block, ⌊B/R⌋.