Dense vs sparse indexes in DBMS Theory - Hands-On Comparison

Understanding Dense vs Sparse Indexes

📖 Scenario: You are managing a small library database. You want to organize the book records so that searching for a book by its ID is faster. You will create two types of index structures: dense and sparse indexes, to understand how they differ.

🎯 Goal: Build simple examples of dense and sparse indexes using dictionaries to represent the index structures. This will help you see how each index type stores keys and pointers differently.

📋 What You'll Learn

Create a dictionary called book_records with 5 book IDs as keys and their titles as values.

Create a variable called index_block_size and set it to 2 to simulate block size for sparse index.

Create a dictionary called dense_index that contains every book ID from book_records as keys and their record locations as values.

Create a dictionary called sparse_index that contains only the first book ID of each block (based on index_block_size) as keys and their record locations as values.

💡 Why This Matters

🌍 Real World

Database systems use dense and sparse indexes to speed up data retrieval while balancing storage space.

💼 Career

Understanding indexing helps in database design, optimization, and improving application performance.

1

Create the book records dictionary

Create a dictionary called book_records with these exact entries: 101: 'The Hobbit', 102: '1984', 103: 'Pride and Prejudice', 104: 'To Kill a Mockingbird', 105: 'The Great Gatsby'.

DBMS Theory

# Create the book_records dictionary with given book IDs and titles
# Your code here

Need a hint?

Use curly braces to create a dictionary with the exact keys and values.

2

Set the index block size for sparse index

Create a variable called index_block_size and set it to 2 to represent the number of records per block in the sparse index.

DBMS Theory

book_records = {
    101: 'The Hobbit',
    102: '1984',
    103: 'Pride and Prejudice',
    104: 'To Kill a Mockingbird',
    105: 'The Great Gatsby'
}

# Create index_block_size variable and set it to 2
# Your code here

Need a hint?

Just assign the number 2 to the variable index_block_size.

3

Create the dense index dictionary

Create a dictionary called dense_index that contains every book ID from book_records as keys and their record locations as values. Use the string format "Record at position {id}" for the values, where {id} is the book ID.

DBMS Theory

book_records = {
    101: 'The Hobbit',
    102: '1984',
    103: 'Pride and Prejudice',
    104: 'To Kill a Mockingbird',
    105: 'The Great Gatsby'
}

index_block_size = 2

# Create dense_index dictionary with all book IDs and their record locations
# Your code here

Need a hint?

Use a dictionary comprehension to include all book IDs with their record locations formatted as strings.

4

Create the sparse index dictionary

Create a dictionary called sparse_index that contains only the first book ID of each block (based on index_block_size) as keys and their record locations as values. Use the same string format "Record at position {id}" for the values.

DBMS Theory

book_records = {
    101: 'The Hobbit',
    102: '1984',
    103: 'Pride and Prejudice',
    104: 'To Kill a Mockingbird',
    105: 'The Great Gatsby'
}

index_block_size = 2

dense_index = {book_id: f"Record at position {book_id}" for book_id in book_records}

# Create sparse_index dictionary with first book ID of each block and their record locations
# Your code here

Need a hint?

Use a dictionary comprehension with a range stepping by index_block_size to pick the first book ID of each block.