Bitmap Indexing
It is a special type of indexing built on a single key. But, it is designed to fire queries on multiple keys quickly. We need to arrange the records in sequential order before applying bitmap indexing on it. It makes it simple to fetch a particular record from the block. Also, it becomes easy to allocate them in the block of a file.
Bitmap Index Structure
The word ‘bitmap’ comprises of ‘bit’ and ‘map’. A bit is the smallest unit of data in a computer system. A map means organizing things. Thus, a bitmap is simply mapping of bits in the form of an array. In a relation, each attribute carries one bitmap for its value. A bitmap has sufficient bits for numbering each record in the block.
For example, consider a relation Student_record where we wish to find out the female and male students whose score in English is greater than 40. The bitmaps for gender are given in the below image.
If the value of a record iis set to Mr, it means the ithbit of the bitmap will be set to 1. Remaining all other bits for Mr in the bitmap will be set to 0. Similarly, the same step proceeds in the case of female students. If for a particular j record, the value is set to Ms, it means the jth bit in the bitmap will be set to 1. All other bits for Ms will be set to 0. Now, if a user wishes to retrieve either a single or all records for female students or male students, i.e., value as Mr or Ms, only need to read all the records of the relation. After reading, select the required records either for Mr or Ms.
However, the bitmap indexing does not allow to select the records quickly. But, it enables the users to read and choose only the required records. As seen in the above example that the user only selected the required records either for female students or for male students.
Uses of Bitmap Indexing
Including one from the above example, there are following uses of Bitmap indexing:
- It enables the user to read and select only the required records or data from a relation.
- It is useful for making selections on multiple keys.
- Bitmap indexing helps in counting the number of records falling under the selection requirement. It means it makes it easy to count those tuples which are under the selection criteria of the user.
- Bitmap indexing is useful as well as necessary in performing queries for data analysis.
- The size of a single bitmap is smaller than 1 percent. Thus, its size is smaller than a relation. For example, a record in a relation is of 100 Bytes, and the relation occupies 1% of memory space. Consequently, a single bitmap occupies 1/8th of the space occupied by the relation.
Deletion and Insertion of Records
- Deleting a record from the relation disturbs the sequence of records. The record which gets deleted creates space or gaps in between other records.
- Filling such gaps is possible by shifting other records, but it is an expensive task.
- Existence bitmap is a solution to this problem. By storing an existence bitmap, we can recognize the deleted records.
- In existence bitmap, if a record does not exist, its bit value will be 0-otherwise 1.
- Insertion of records is cost-effective. It is because the insertion of a record does not affect the sequence of other records.
- Either by merely replacing the deleted records or by appending records to the EOF (end of file), a user can proceed to insert the records.
Implementation of Bitmap Operations
It is better to implement bitmap operations efficiently.
- Intersection Operation
The intersection of two bitmaps is possible by using for loop. The ithiteration of the loop performs the AND operation of the ith bits of both bitmaps. For speeding up the intersection operation, use bitwise AND instructions. It is because a word consists of either 32 or 64-bits, depending on the computer architecture. So, it is easy for a single bitwise AND to perform the intersection of 32 or 64-bits at once.
- Union Operation
Bitmap union is used for calculating the OR of two bitmaps. For performing union operation, we use bitwise OR instructions on 32 or 64-bits at once.
- Negation Operation
The complement operation is used for performing the negation operation. It is done by complementing each bit of the bitmap. However, if some records have been deleted, then the complement of the bitmap is insufficient. It happens because, in the original bitmap, bits corresponding to such non-existing records will be 0. But would become 1 in the complement. For this, perform the intersection of the complement bitmap with the existence bitmap to ensure that the bits corresponding to the deleted records must turn off to 0. The same problem occurs with the null values. So, perform the intersection operation of the complement bitmap with the complement of the bitmap for the null value.
Note:We can use bitmaps with B+ trees as a compressed storage mechanism for the values that occurs very frequently at the leaf nodes of B+ trees.