Bitmap index
A bitmap index is a database index that is used to efficiently index multi-dimensional data . Due to its properties, the bitmap index is mainly used in data warehouses .
Hence the designation is because the bitmap index one or more attributes in the form of a bit pattern ( engl. Bitmap ) stores. It is especially useful for indexing table columns with a low cardinality (number of different values in this column). This is precisely the area in which a conventional index, implemented by a B-tree , does not bring about any increase in access performance.
example
A simple example: the attributes gender (two possible values, cardinality = 2) and marital status (cardinality = 3) are entered in an index of a personal database. The index table could look like this:
| Surname | male | Female | single | married | divorced |
|---|---|---|---|---|---|
| Anne | 0 | 1 | 0 | 1 | 0 |
| Emil | 1 | 0 | 0 | 0 | 1 |
| Fritz | 1 | 0 | 0 | 1 | 0 |
| Hans | 1 | 0 | 0 | 1 | 0 |
| Willi | 1 | 0 | 1 | 0 | 0 |
functionality
As with all database indexes, each of these entries has a reference to an (external) database entry.
The search of the (preferably internally stored) index table is done using simple binary operations, in the example using an AND link with a search mask. If you search for people in the example who are male and married, the search mask is 10 010 (the references to the hits lead to Fritz and Hans).
Use of the binary operations at the processor level offers a speed advantage for comparison operations. This representation exchanges computing effort for storage space.
Illustration of the range of values
The assignment of a value of a value range to a bit vector is done by choosing the base of the bit vector. If a single bit vector is uniquely assigned to each value of the value range, the length of the bit vector in the simple case corresponds exactly to the cardinality of the value range and is at the same time the basis of the bit vector. One advantage of this display is the possibility of leaving out individual values of a value range if they do not appear in the available data. It is also possible to specify a non-uniform basis.
literature
- Chee-Yong Chan and Yannis Ioannidis: Bitmap Index Design and Evaluation . Proceedings of the 1998 ACM SIGMOD Conference.