THE PHYSICAL DESIGN PROCESS - Database Design and Development: An Essential Guide for IT Professionals - page 369

The index file contains a lower number of records than the data file—only 1
index record for each index value. Retrieval of index value 101 results in
retrieval of just 1 index record, retrieval of the first corresponding data record,
and then retrieval of the other 2 data records by following the pointers in the
data records.
Bitmapped Indexing
Bitmapped indexes are ideally suitable for low-selectivity fields. A field with low
selectivity is one that consists of a small number of distinct values. If there are
only six different job codes for employee data, then JobCode is a low-selectivity
field. On the other hand, Zip is not a low-selectivity field; it can have many distinct
values.
A bitmap is an ordered series of bits, one for each distinct value of the indexed
column. Let us review a sales file containing data about sales of appliances. Assume
that the field for Color has three distinct values, namely, white, almond, and black.
Construct a bitmap with these three distinct values. Each entry in the bitmap
contains three bits. Let us say, the first bit refers to the value white, the second to
almond, and the third bit to black. If a product is white in color, the bitmap entry
for that product consists of three bits where the first bit is set to 1, the second bit is
set to 0, and the third bit is set to 0. If a product is almond in color, the bitmap entry
for that product consists of three bits where the first bit is set to 0, the second bit is
set to 1, and the third bit is set to 0. You get the picture. Now, please study the
bitmapped index example shown in Figure 12-17.
The figure presents an extract of the sales file and bitmapped indexes for the
three different fields. Note how each entry in an index contains the ordered bits to
represent the distinct values in the field. An entry is created for each record in the
sale file. Each entry carries the address of the record.
How do the bitmapped indexes work to retrieve the requested rows? Consider
the following data retrieval from the sales file:
Select the records from sales file
Where Product is “Washer” and
Color is “Almond” and
Division is “East” or “South”
Figure 12-18 illustrates how Boolean logic is applied to find the result set based
on the bitmapped indexes shown in Figure 12-17.
As you observe, bitmapped indexes support data retrievals using low-selectivity
fields. The strength of this technique rests on its effectiveness when you retrieve
data based on values in low-selectivity fields. Bitmapped indexes take significantly
less space than B-tree indexes for low-selectivity fields.
On the other hand, if new values are introduced for the indexed fields, bitmapped
indexes have to be reconstructed. Another disadvantage relates to the necessity to
access the data files all the time after the bitmapped indexes are accessed. B-tree
indexes do not require data file access if the requested information is already
contained in the index file.