Bitmap indexes in DBMS Theory - Mini Project: Build & Apply

Understanding Bitmap Indexes in Databases

📖 Scenario: You are working with a database that stores information about employees and their department assignments. To speed up queries that filter employees by department, you want to understand how bitmap indexes work.

🎯 Goal: Build a simple conceptual bitmap index representation for employee departments and learn how to use it to quickly find employees in a specific department.

📋 What You'll Learn

Create a list of employees with their department IDs

Create a list of unique department IDs

Build a bitmap index for each department showing which employees belong to it

Use the bitmap index to find employees in a specific department

💡 Why This Matters

🌍 Real World

Bitmap indexes are used in databases to speed up queries on columns with low distinct values, like department IDs, gender, or status flags.

💼 Career

Understanding bitmap indexes helps database administrators and developers optimize query performance and design efficient indexing strategies.

1

Create the employee data list

Create a list called employees with these exact entries representing employee IDs and their department IDs as tuples: (101, 1), (102, 2), (103, 1), (104, 3), (105, 2).

DBMS Theory

# Create the list called employees with given tuples
# Your code here

Need a hint?

Use a list of tuples where each tuple has employee ID and department ID.

2

Create the list of unique departments

Create a list called departments that contains the unique department IDs 1, 2, and 3.

DBMS Theory

employees = [(101, 1), (102, 2), (103, 1), (104, 3), (105, 2)]
# Create the list called departments with unique IDs 1, 2, 3
# Your code here

Need a hint?

List the unique department IDs exactly as numbers in a list.

3

Build the bitmap index for departments

Create a dictionary called bitmap_index where each key is a department ID from departments and the value is a list of bits (0 or 1). Each bit corresponds to an employee in employees in order. Use 1 if the employee belongs to that department, otherwise 0.

DBMS Theory

employees = [(101, 1), (102, 2), (103, 1), (104, 3), (105, 2)]
departments = [1, 2, 3]
# Create bitmap_index dictionary with department keys and bit lists
# Your code here

Need a hint?

Use a dictionary comprehension or a for loop to create bit lists for each department.

4

Find employees in a specific department using the bitmap index

Create a variable called dept_to_find and set it to 2. Then create a list called employees_in_dept that contains the employee IDs from employees where the corresponding bit in bitmap_index[dept_to_find] is 1.

DBMS Theory

employees = [(101, 1), (102, 2), (103, 1), (104, 3), (105, 2)]
departments = [1, 2, 3]
bitmap_index = {}
for dept in departments:
    bitmap_index[dept] = [1 if emp[1] == dept else 0 for emp in employees]
# Set dept_to_find to 2 and create employees_in_dept list using bitmap_index
# Your code here

Need a hint?

Use enumerate on the bitmap list to find indexes where bit is 1, then get employee IDs at those indexes.