index is a special kind of database
uses bitmaps, Oracle bitmap indexes are very different from
standard b-tree indexes , Bitmap Indexes were first introduced by O’Neil
and implemented in the Model 204 DBMS. The bitmap technique is largely used for
typical data warehouse applications, which are mainly characterized and Used by complex query
types and read-mostly environments that are more or less static.
In data warehouse
environments insert, delete or update operations are not common, therefore, the
bitmap index is coming up to optimizes the query performance rather than others.
are used by DBMS to accelerate decision support queries. The main advantage of
Bitmap indexes is that complex logical selection operations can be performed
very quickly and faster than B-tree by applying low-cost Boolean operations
such as OR, AND, and NOT, this will reduce search space before going to the
primary source data.
Characteristic of Bitmap indexing
· For columns with very few unique values (low
· Columns that have low cardinality are
· Tables that have no or little
insert/update are good candidates
· Stream of bits: each bit relates to a
column value in a single row of table
Advantage of Bitmap Indexes
The main advantage of the Bitmap indexes that are high compressed structure,
which will make the read is really fast. in addition, the bitmap structure
makes the system merge multiple indexes together for faster access to the
Compressed indexes are like a bitmap indexes, its represent a
trade-off between CPU and Disk usage. The compressed structure is faster to
read-only from disk but unfortunately it takes
additional CPU cycles to decompress for access an uncompressed structure.
concerning bitmap indexes is that they are only suitable for indexing
low-cardinality data. This is not necessarily true, because by compressing the
indexes in bitmap indexes, it can be used very successfully for indexing
columns with many millions of different values.
Disadvantage of Bitmap
The main disadvantage is the
modification on bitmap indexing which is really dreadful, because it requires a
huge deal work on behalf of the system which is worst than modification on
B-tree index, on other hand the overhead on maintaining the bits is enormous.
Bitmap index Design
Basic Bitmap Index
Bitmap indices are one of the most efficient indexing
methods available for speeding up multi-dimensional range queries for reading
only (projection), the queries are evaluated with bitwise logical
operations that are well supported by computer hardware,” for an attribute with
C distinct values, the basic bitmap index generates C bitmaps
with N bits each, where N is the number of records in the data
set. Each bit in a bitmap is set to “1” if the attribute in the record is
of a specific
value; otherwise the bit is set to “0””.
Figure 1 below
will demonstrate a simple bitmap index with 6 bitmaps. “Each bitmap represents
a distinct attribute value. For instance, the attribute value 3 is highlighted
to demonstrate the encoding. In this case, bitmap 3 is set to “1”, all other
bits on the same horizontal position are set to “0””.
Figure 1 Basic Bitmap Index Example
The basic bitmap
index introduced above is also called equality encoded bitmap index
since each bitmap indicates whether or not an attribute value equals to the
key. This strategy is the most efficient for equality queries such as “temperature
= 100.” Chan and Ioannidis (1998; 1999) developed two other encoding strategies
that are called
range encoding and interval encoding. These
bitmap indices are optimized for one-sided and two-sided range queries,
example of a
one-sided range query is “pressure