← 🌲 File Organisation & Indexing
Subtopic 2 of 5

7.2Indexing: dense, sparse and multilevel

The idea

An index is a small table of (key, block pointer) used to find records quickly. Dense: one entry per record. Sparse: one per block. Multilevel: an index on the index.

Think of it like this: A book's index lists words and pages; a sparse index lists only the first word of each page.

Why it exists

Questions ask the size of an index or the number of block accesses to find a record.

How it works

  1. Entries per index block = ⌊B / (key + pointer)⌋.
  2. Sparse (primary) index: b entries, one per data block. Dense (secondary): r entries.
  3. Single level: binary search the index, then read the data block.
  4. Multilevel: keep indexing until one block is left; accesses = number of levels + 1.

Worked example: B = 1024, key 9, pointer 6, 5000 data blocks.

Entries per block 68; level 1 = 5000/68 = 74 blocks; level 2 = 2 blocks; level 3 = 1 block. 3 levels, 4 accesses.

Now play with it

  • →Open the second calculator and compare dense and sparse index sizes.
  • →Change the key size and see the number of levels change.
Data blocks3000
Index entries per block68
Sparse index: entries / blocks3000 / 45
Dense index: entries / blocks30000 / 442
Sparse, single level: block accesses7 (binary search on the index, +1 data block)
Multilevel (sparse) index levels2
Multilevel: block accesses3

A multilevel index keeps indexing the previous level until a single block is left. Accesses = levels + 1 data block.

Check yourself

A secondary index on a non-ordering key must be

Remember: Sparse: one entry per block. Dense: one per record. Accesses = levels + 1.
Exam notes (the dense version)

A dense index has an entry for every record; a sparse index has one per block (data file must be sorted). A primary index is on the ordering key, a clustering index on a non-key ordering field, a secondary index on any other field (always dense). Index entries per block = ⌊B / (key + pointer)⌋. A multilevel index is an index on the index: levels continue until one block remains; search cost = levels + 1 block accesses.

Previous year questions: File Organisation & Indexing (9)

PYQs are grouped by topic, so this is the full set for File Organisation & Indexing; try the ones that match this subtopic. Open all 9 on the topic page.