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:
Deletion and Insertion of Records
Implementation of Bitmap Operations
It is better to implement bitmap operations efficiently.
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.
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.
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.
Next TopicBuffer Replacement Strategies