Dense vs sparse indexes in DBMS Theory - Practice Questions

Challenge - 5 Problems

🧠 Conceptual

intermediate

Difference between dense and sparse indexes

Which statement correctly describes the difference between dense and sparse indexes in database systems?

A A sparse index has an index entry for every search key value in the data file, while a dense index has entries only for some of the search key values.

B A dense index has an index entry for every search key value in the data file, while a sparse index has entries only for some of the search key values.

C Both dense and sparse indexes have entries for every search key value, but sparse indexes store less data per entry.

D Dense indexes are used only for unordered data, while sparse indexes are used only for ordered data.

💡 Hint

Think about how many entries each index type contains relative to the data file.

Dense indexes contain an entry for every record in the data file, making lookups fast but requiring more space. Sparse indexes contain entries for only some records, typically one per data block, saving space but requiring extra steps to find records.

🚀 Application

intermediate

Choosing index type for sorted data

You have a large sorted data file stored on disk. Which type of index is generally more space-efficient and suitable for this data?

A Dense index, because it stores only the first record of each block.

B Dense index, because it stores an entry for every record making searches faster.

C Sparse index, because it stores fewer entries by indexing only some records, reducing space usage.

D Sparse index, because it stores entries for every record to speed up access.

💡 Hint

Consider how indexing fewer records affects space and search efficiency for sorted files.

Sparse indexes are more space-efficient for sorted files because they store entries only for some records, usually one per block. This reduces index size while still allowing efficient block-level searching.

🔍 Analysis

advanced

Impact of index type on search performance

Consider a database with a dense index and another with a sparse index on the same sorted data file. Which statement best explains the difference in search performance?

A The dense index allows direct access to every record, so searches are faster than with a sparse index which requires an extra step to locate the block.

B The sparse index allows direct access to every record, so searches are faster than with a dense index which requires scanning blocks.

C Both indexes provide the same search speed because they index the same data.

D Sparse indexes are always slower because they store more entries than dense indexes.

💡 Hint

Think about how many steps are needed to find a record using each index type.

Dense indexes have an entry for every record, allowing direct access without extra block scanning. Sparse indexes have fewer entries, so after locating the block, a search within the block is needed, making it slightly slower.

❓ Comparison

advanced

When to prefer sparse index over dense index

In which scenario is a sparse index generally preferred over a dense index?

A When the data file is sorted and space efficiency is important.

B When the data file is unsorted and random access is required.

C When every record must be accessed quickly without scanning.

D When the data file is very small and fits entirely in memory.

💡 Hint

Consider the trade-off between space and access speed for sorted data.

Sparse indexes are preferred for sorted data files where saving space is important. They index fewer records, reducing index size, while still allowing efficient block-level searching.

❓ Reasoning

expert

Effect of block size on sparse index entries

How does increasing the block size of a sorted data file affect the number of entries in a sparse index built on it?

A The number of sparse index entries increases because more records fit in each block.

B The number of sparse index entries becomes equal to the number of records.

C The number of sparse index entries stays the same regardless of block size.

D The number of sparse index entries decreases because fewer blocks exist, so fewer entries are needed.

💡 Hint

Think about how block size affects the total number of blocks and index entries.

Increasing block size means each block holds more records, so the total number of blocks decreases. Since sparse indexes have one entry per block, the number of index entries decreases.

Practice

1. What is the main difference between a dense index and a sparse index in a database?

easy

A. Dense index stores data physically; sparse index stores data logically.

B. Sparse index has an entry for every record; dense index has entries for some records only.

C. Dense index has an entry for every record; sparse index has entries for some records only.

D. Sparse index is faster than dense index in all cases.

Solution

1. Step 1: Understand dense index definition

   A dense index contains an index entry for every record in the data file, making lookups very fast.

2. Step 2: Understand sparse index definition

   A sparse index contains entries only for some records, usually one per data block, saving space but requiring extra searching inside blocks.

3. Final Answer:

   Dense index has an entry for every record; sparse index has entries for some records only. -> Option C

4. Quick Check:

   Dense = every record, Sparse = some records [OK]

Hint: Dense = all entries, sparse = fewer entries [OK]

Common Mistakes:

• Confusing which index has entries for every record
• Thinking sparse index is always faster
• Assuming dense index saves more space

2. Which of the following is the correct syntax to describe a sparse index in a database textbook?

easy

A. "An index with entries for every record in the data file."

B. "An index that duplicates all data entries."

C. "An index that stores the entire data file."

D. "An index with entries only for some records, typically one per block."

Solution

1. Step 1: Recall sparse index definition

   Sparse index contains entries only for some records, usually one per block, to save space.

2. Step 2: Match options with definition

   "An index with entries only for some records, typically one per block." correctly describes sparse index as having entries only for some records.

3. Final Answer:

   "An index with entries only for some records, typically one per block." -> Option D

4. Quick Check:

   Sparse index = fewer entries per block [OK]

Hint: Sparse index = fewer entries, usually one per block [OK]

Common Mistakes:

• Choosing dense index description for sparse index
• Confusing sparse index with full data storage
• Selecting options that describe dense index

3. Consider a database with 1000 records stored in 100 blocks. If a sparse index has one entry per block, how many entries does the sparse index have?

medium

A. 100

B. 1000

C. 10

D. 1

Solution

1. Step 1: Understand sparse index entry count

   Sparse index has one entry per block, not per record.

2. Step 2: Calculate entries based on blocks

   Given 100 blocks, sparse index will have 100 entries.

3. Final Answer:

   100 -> Option A

4. Quick Check:

   Entries = blocks = 100 [OK]

Hint: Sparse index entries = number of blocks [OK]

Common Mistakes:

• Confusing entries with total records
• Assuming sparse index has one entry per record
• Choosing a number unrelated to blocks

4. A database administrator created an index with entries for every record but calls it a sparse index. What is the error in this scenario?

medium

A. The index is actually a dense index, not sparse.

B. Sparse index must have entries for every record.

C. Sparse index stores data physically, not index entries.

D. There is no error; this is a valid sparse index.

Solution

1. Step 1: Identify index type by entry count

   An index with entries for every record is a dense index by definition.

2. Step 2: Understand sparse index definition

   Sparse index has fewer entries, not one per record.

3. Final Answer:

   The index is actually a dense index, not sparse. -> Option A

4. Quick Check:

   Entries per record = dense, not sparse [OK]

Hint: Entries for every record means dense index [OK]

Common Mistakes:

• Thinking sparse index can have all entries
• Confusing physical data storage with index entries
• Believing no error exists in naming

5. You have a large database where fast search is critical, but storage space is limited. Which index type should you choose and why?

hard

A. Sparse index, because it uses less space and is always faster.

B. Dense index, because it provides faster search at the cost of more space.

C. Dense index, because it uses less space and slower search.

D. Sparse index, because it provides faster search and uses more space.

Solution

1. Step 1: Analyze speed vs space trade-off

   Dense index has an entry for every record, making search very fast but uses more space.

2. Step 2: Match requirement with index type

   Since fast search is critical, dense index is preferred despite higher space usage.

3. Final Answer:

   Dense index, because it provides faster search at the cost of more space. -> Option B

4. Quick Check:

   Fast search needs dense index [OK]

Hint: Fast search needs dense index, space saving needs sparse [OK]

Common Mistakes:

• Choosing sparse index for fastest search
• Confusing space usage of dense vs sparse
• Ignoring trade-offs between speed and storage