Bitmap-Index

A bitmap index is a database index that is used to index multidimensional data efficiently. Due to its properties, the bitmap index is used primarily for data warehouse applications.

The term stems from the fact that the bitmap index stores one or more attributes in the form of a bit pattern (English bitmap). It is mainly intended to build the indexing table columns with a low cardinality (number of distinct values ​​present in this column ). This is precisely the area in which a conventional index, realized by a B- tree, no increase in access performance brings.

Example

A simple example: in an index of a personnel database, the attributes gender ( two possible values ​​, cardinality = 2), and marital status are ( cardinality = 3) registered. The index table might look like this:

Operation

As with all database indexes exist of each of these entries is a reference to an ( external ) database entry.

Searching the (preferably internally stored ) index table is done through simple binary operations, in the example above AND operation with a search engine. If you look in the example for people who are male and married, so the search is 10 010 ( the references of the results lead to Fritz and Hans).

Use of binary operations on the processor level offers a speed advantage in comparison operations. Through this representation against computational effort space is exchanged.

Illustration of the range of values

Assigning a value of a range of values ​​to a bit vector is done by the choice of the base of the bit vector. If each value of the range of values ​​uniquely associated with a single bit vector, the length of the bit vector in the simple case corresponds exactly to the cardinality of the range and also provides the basis of the bit vector. One advantage of this representation is the ability to omit individual values ​​of a range of values, if this does not occur in the present data. It is also possible to provide a non-uniform basis.