Database Management System (DBMS) / Importance of Indexing

Dense Index VS Sparse Index

📊 Dense Index

A Dense Index has one index entry for every record in the database file.

It directly maps each search key to a specific data record.

✅ Characteristics:

  • Every record has a corresponding index entry.

  • Fast for searching any value.

  • Uses more storage.

🧠 Example:

Consider a data table:

RollNo

Name

101

A

102

B

103

C

Dense index would be:

[101] → Record 1
[102] → Record 2
[103] → Record 3

Each row is indexed.

📊 Sparse Index

A Sparse Index has index entries for only some records — typically one per block/page.

It assumes data is sorted on the indexed column.

✅ Characteristics:

  • Not every record is indexed.

  • Requires less space.

  • Slower than dense index for point lookups (needs block scanning).

🧠 Example:

Suppose records are stored across disk blocks:

Block 1: 101, 102

Block 2: 103, 104

Block 3: 105, 106

Sparse index:

[101] → Block 1
[103] → Block 2
[105] → Block 3

Only first record of each block is indexed.

📊 Comparison Table: Dense vs Sparse Index

Feature

Dense Index

Sparse Index

🔁 Index Entries

One per record

One per data block/page

📚 Storage Overhead

High (more index entries)

Low (fewer entries)

🚀 Search Speed

Fastest (direct access to records)

Slower (may require scanning in block)

🧹 Maintenance

More expensive (due to many entries)

Easier to maintain

📦 Space Requirement

Larger index file

Smaller index file

📏 Ideal for

Small datasets or frequent exact lookups

Large datasets with sorted data

🧠 Summary Analogy:

Think of dense index like a dictionary where every word is listed.

Think of sparse index like a chapter summary — it tells you where sections start, but not every detail.

🧮 Bonus Tip:

  • Sparse index works only on ordered data.

  • Often, a sparse outer index is used on top of dense inner indexes for multi-level indexing (used in large DBs).