Entwurf des Data Warehouse
Die Grundidee bei dieser Technik ist das Nutzen eines einfachen Bits. Für jeden existierenden Attributwert wird eine Bitliste angelegt, die so viele Positionen enthält, wie es Tupel in der Faktentabelle gibt. Dabei weist eine Eins (1) auf den entsprechenden Attributwert in einem Datensatz hin und zeigt eine Null (0) das Nichtvorhandensein des Attributwerts an (siehe Abbildung 6).
Im Gegensatz zum B-Baum wird die Bitmap-Indexierung speziell für Daten mit geringer Kardinalität und mit großer Anzahl von Datensätzen verwendet. Sie unterstützt insbesondere die Verarbeitung von komplexen Anfragen mit logischen Verknüpfungen wie AND, OR, NOT und COUNT. Dadurch können Sparse-Daten auf ähnlicher Weise wie Dense-Daten behandelt werden. Abbildung 7 zeigt ein Beispiel für die Verknüpfung von zwei Bitslisten P und LZ, dadurch werden alle Angestellten, die als Programmierer tätig sind und aus Leipzig kommen, ausgesucht.
Daneben gibt es natürlich auch Nachteile bei dieser Technik. Sie ist ungeeignet für Datenbanken mit hoher Kardinalität wie in meisten Datenbank-Implementierungen, da sich die Gefahr des erhöhten Speicherüberlaufs ergibt. Sie erweist sich auch als unpraktisch für konventionelle Daten wie Namen, Adresse, Einkommen usw. Darüberhinaus ist sie beschränkt in der Fähigkeit, Daten zu aggregieren und relationale Joins zu implementieren . Ein weiteres Problem liegt in der Änderungsperformanz: durch Einfügen neuer Tupeln müssen alle Bitmap-Indizes modifiziert werden.
Während B-Baum für OLTP-Anwendungen angepaßt ist, ist im DW-Bereich die Bitmap-Indexierung vorteilhafter. Das ergibt sich aus der geringeren Zeit- und Platzkomplexität und der Möglichkeit, komplexe Anfragen und große Menge von Daten, was in DW sehr typisch ist, zu verarbeiten.
Um das Problem der Einschränkungen bei der Bitmap-Indexierung zu lösen, wurden verschiedene Varianten von vielen DB-Anbietern eingesetzt.
Zur Reduzierung des Speicherkostens werden Bitlisten oft komprimiert, insbesondere wenn die Häufigkeit der Attributwerte sehr ungleichmäßig verteilt wird. Jedoch muß sich die Komprimierung mit den AND-, OR-, NOT- und COUNT-Operationen anpassen.
Diese Methode beruht auf der Kombination von B-Baum und Bitmap-Index und wurde von den Anbietern bei der Entwicklung verschiedener Indexierungstechniken verwendet. Die einfache B-Baum-Indexierung wird verwendet, wenn die Liste der qualifizierten RIDs pro Eintrag klein ist. Andernfalls wird die Bitmap-Indexierung in Form einer B-Baum Struktur mit den Blättern als komprimierte oder nicht-komprimierte Bitlisten genutzt.
Für Daten mit hoher Kardinalität können Bitlisten dynamisch aus vertikal partitionierter Faktentabelle konstruiert werden. Wenn es n unterschiedliche Attributwerte gibt, werden sie zu n (log n)-bit kontinuierlichen binären Integer codiert.
Als eine Erweiterung des einfachen Bitmap-Indexes wird diese Technik ausführlich in [WB97] behandelt. Der Ansatz liegt darin, daß Bitmap-Vektoren nicht einzeln genutzt werden, sondern sie zusammen mit anderen Werten codiert werden. Angenommen, es gäbe eine Faktentabelle mit N Tupeln und eine Dimensionstabelle (Attribut) mit einer Domain von n Werten. Während bei der einfachen Bitmap-Indexierung n Bitmap-Vektoren benutzt werden sollen, benötigt die codierte Technik nur (log n) Bitmap-Vektoren und eine zusätzliche Maptabelle. Im allgemeinen ist die Konstruktion/Aufrechterhaltung der codierten Bitmap-Indies ökonomischer als die der einfachen, wenn die Kardinalität der indexierten Attribute erhöht wird. Jedoch muß die Verwaltung der Bitlisten bei der Änderung von Attribut-domains berücksichtigt werden, insbesondere wenn neue Bitmap-Vektoren eingefügt werden.
Wie Abbildung 8 zeigt, werden 3 Bitmap-Vektoren (P, I, M) im Falle einer einfachen Bitmap-Indexierung benötigt, dagegen für die codierte Bitmap-Indexierung nur 2 (B0, B1).
[Next] [Previous] [Up] [Top] [Contents] [Index]