Data Warehouse Technologien

Abbildung 7.8 zeigt einen derartigen B-Baum, der faktisch nur aus dem

Wurzelknoten mit drei Einträgen besteht. Der Vorteil der Bitmap-Indexe ist

auch hier der geringere Speicherbedarf.

JBeispiel 7-5I Werden im Beispiel etwa 150.000 Tupel bei drei verschiedenen

Schlüsselwerten indexiert und 4 Byte für einen TID genutzt, so benötigt ein

klassischer B

+

-Baum etwa 600 KB, während der Bitmap-Index mit 3 · 18750

Byte = 56 KB auskommt. 2

Die Definition von Bitmap-Indexen in relationalen Datenbanksystemen ist

nicht standardisiert, aber die Hersteller nutzen Notationen ähnlich zur Dekla-

ration von Standardindexen. In Oracle-Syntax lautet die Deklaration etwa wie

folgt:

CREATE BITMAP INDEX bestellstatus

_

idx

ON bestellung(status);

Genutzt werden derartige Indexe speziell zur Star-Query-Transformation (Ver-

bund zwischen Dimensions- und Faktentabelle). Die Speicherung erfolgt in

komprimierter Form.

7.3.3 Standard-Bitmap-Index

Standardmäßig wird in einem Bitmap-Index jede Dimension getrennt abgespei-

chert. Für jede Ausprägung eines Attributs wird ein Bit-Vektor angelegt.

JBeispiel 7-6I Das Attribut Geschlecht mit zwei Wertausprägungen (m/w)

resultiert also in zwei Bit-Vektoren, wie in Tabelle 7.1 abgebildet. 2

PersId Name Geschlecht Bitmap-w Bitmap-m

007 James Bond M 0 1

008 Amelie Lux W 1 0

010 Harald Schmidt M 0 1

011 Heike Drechsler W 1 0

Tabelle 7.1: Standard-Bitmap-Index für Attribut Geschlecht

Wie bereits gezeigt, erfolgt die Selektion von Tupeln nun durch entspre-

chende Verknüpfung von Bit-Vektoren. Im Beispiel werden Bitmap-Indexe über

die Attribute Geschlecht und Geburtsmonat angelegt. Es gibt also zwei Bit-

Vektoren B-w und B-m für Geschlecht und zwölf Bit-Vektoren B-1, ..., B-12 für

die Monate, wenn alle Monate vorkommen.

Die Anfrage „alle im März geborenen Frauen“ wird nun berechnet, indem

B-w ∧ B-3 berechnet wird (also die Vektoren bitweise konjunktiv verknüpft wer-

206 7 Indexstrukturen