What is Database Indexing by Bitmap Indexing approach?
Published: 2023-04-21 20:20:43

---
title: What is Database Indexing by Bitmap Indexing approach?
published: true
date: 2023-04-14 17:10:38 UTC
tags: 
canonical_url: https://harshmange.hashnode.dev/what-is-database-indexing-by-bitmap-indexing-approach
---

## Introduction

Bitmap indexing is a type of database indexing that uses bitmap vectors to represent the values of attributes in a table. In this approach, each attribute value is mapped to a bit in a bitmap vector. If the value is present in a record, the corresponding bit is set to 1 otherwise, the bit is set to 0.

## Under the Hood Structure

Under the hood, a bitmap index is typically implemented as a set of bitmap vectors, one for each attribute that is indexed. Each bit in a bitmap vector represents a value of the indexed attribute, and each record in the table is represented by a set of bits that correspond to the values of the indexed attributes in the record.

Bitmap indexing is particularly useful for columns with a small number of distinct values, as the bitmap vectors can be compressed to save space. It is also very efficient for queries that involve multiple columns, as the bitwise operations can be performed quickly using modern CPUs. However, it can be less efficient for columns with a large number of distinct values, as the bitmap vectors can become very large and slow down query performance.

## Example

To retrieve records from the bitmap index, a query is expressed as a set of conditions on the indexed attributes. For example, a query might ask for all records where the `Department` attribute is "Sales" and the `Salary` attribute is greater than $50,000. To answer this query, the bitmap vectors for the `Department` and `Salary` attributes are combined using bitwise operations to produce a bitmap vector that represents the set of records that satisfy the query conditions. The set of records is then retrieved by scanning the table and selecting the records that have a corresponding bit set in the bitmap vector.

Suppose we have a table of employees with the following attributes:

```
EmployeeID
FirstName
LastName
Department
Salary

```

We want to create a bitmap index on the `Department` and `Salary` attributes. We start by creating a bitmap vector for each attribute:

```
Department:
----------
Sales: 00000000
Marketing: 00000000

Salary:
------
0-49999: 00000000
50000-99999: 00000000

```

Each bit in the bitmap vectors represents a possible value of the attribute. In this case, the `Department` attribute has two possible values, "Sales" and "Marketing", and the `Salary` attribute is divided into two ranges, $0-$49,999 and $50,000-$99,999.

When a record is inserted into the table, the bitmap vectors are updated to reflect the presence of the record. For example, if we insert a record with `EmployeeID` 123456, `FirstName` "John", `LastName` "Smith", `Department` "Sales", and `Salary` $50,000, the bitmap vectors would be updated as follows:

```
Department:
----------
Sales: 10000000
Marketing: 00000000

Salary:
------
0-49999: 00000000
50000-99999: 10000000

```

To retrieve records from the bitmap index, a query is expressed as a set of conditions on the indexed attributes. For example, if we want to retrieve all records where the `Department` attribute is "Sales" and the `Salary` attribute is greater than $50,000, we perform the following steps:

1. Look up the bitmap vectors for the `Department` and `Salary` attributes.

2. Perform a bitwise AND operation on the two bitmap vectors to produce a new bitmap vector that represents the set of records that satisfy both conditions:

```
Department:
----------
Sales: 10000000
Marketing: 00000000

Salary:
------
0-49999: 00000000
50000-99999: 10000000

Result:
-------
Sales & 50000-99999: 10000000

```

1. Scan the table and select the records that have a corresponding bit set in the result bitmap vector:

```
EmployeeID FirstName LastName Department Salary
----------------------------------------------------------------
123456 John Smith Sales $50,000

```