Data Warehouse Technologien

ein Bit-Vektor angelegt. Hierbei steht für jedes Tupel ein Bit; dieses wird

auf 1 gesetzt, wenn das indexierte Attribut in dem Tupel den Referenzwert

dieses Bit-Vektors enthält, ansonsten auf 0. Die Anzahl der entstehenden

Bit-Vektoren pro Dimension entspricht somit der Anzahl der unterschiedlichen

Werte, die für das Attribut vorkommen, also der Kardinalität dieses Attributs.

Bitmap-Indexe werden in [SSH11] im Abschnitt 5.4 ausführlich behandelt,

sodass wir hier den Schwerpunkt auf spezielle Erweiterungen legen.

7.3.1 Prinzip von Bitmap-Indexen

Das Prinzip von Bitmap-Indexen läßt sich am besten an einem Beispiel ver-

deutlichen.

JBeispiel 7-3I Die Basisidee von Bitmap-Indexen verdeutlicht ein Bitmap-

Index für ein Attribut Bestellstatus einer Relation bestellung, das nur die

Werte B für „in Bearbeitung“, F für „fertig“ und O für „offen“ annehmen kann.

TID B F O

tid

1

0 0 1

tid

2

0 1 0

tid

3

0 0 1

tid

4

1 0 0

tid

5

1 0 0

tid

6

0 1 0

tid

7

0 0 1

.

.

.

.

.

.

.

.

.

.

.

.

Abbildung 7.6: Ein Bitmap-Index

2

Der Bitmap-Index in Abbildung 7.6 zeigt die kompakte Darstellung als Bit-

Array. Die TIDs müssen nicht bei jedem Bitmap-Index für eine Relation explizit

abgespeichert werden, sofern die Reihenfolge bei allen Indexen und der Rela-

tion garantiert identisch ist. Tatsächlich gespeichert werden dann nur die Bit-

Werte.

Neben der Reduzierung des Platzbedarfs ist eine effiziente Auswertung von

Selektionen möglich.

JBeispiel 7-4I Für eine Selektion

Bestellstatus = ’B’ AND Region IN ("Süd", "West")

204 7 Indexstrukturen