[Next] [Previous] [Up] [Top] [Contents] [Index]
Entwurf des Data Warehouse
4.1. B-Baum
4.1.1. Standardisierter B-Baum
Im Vergleich mit sequentiellem Zugriff hilft eine B-Baum Indexierung zum schnellen Durchsuchen der Tabelle, da nur eine Teilmenge der Struktur zugegriffen werden muß. Die Indexe können auf einer oder mehreren Spalten (Attribute) der Tabelle definiert werden. Jedoch wird diese Technik bevorzugt für Attribute mit höherer Kardinalität verwendet, d.h. die Anzahl der Attributwerte ist sehr groß. Als Beispiele für solche Attribute sind Kunde-Nachname, Kunde-ID, ... Sie ist außerdem nur sinnvoll, wenn die Tabellle nur eine kleine Anzahl von Datensätzen enthält.
Wie jede Baumstruktur besitzt ein B-Baum einen Wurzel, viele Zwischenknoten und mehrere Blätter. Der Wurzel und jeder Zwischenknoten haben Zeiger (Verweiser) auf andere Knoten in niedrigerer Ebene. Ein wichtiges Merkmal des B-Baumes besteht in seiner Strukturbalancierung, d.h. der Abstand vom Wurzel zu irgendeinem Blatt ist gleich und bleibt auch konstant trotz Einfügen und Löschen der Einträge.
Obwohl für OLTP-Systeme standardisierte B-Baum-Indexierung gut geeignet sein kann, erweist sie sich als nicht ausreichende Wahl für DSS bzw. DW aufgrund folgender Charakteristika:
- Sie ist nicht sinnvoll bei Daten mit geringer Kardinalität wie männlich/weiblich, verheiratet/geschieden/ledig, ...
- Sie erfordert Kosten für Erstellung und Verwaltung von Indizes, da sie durch Einfüge- und Änderungs-Operationen leicht unbalanciert werden kann.
- Sie ist insbesondere für Umgebungen entworfen, in denen Anfragen relativ einfach und Zugriffspfade bekannt sind, deshalb entstehen Probleme bei komplizierten Bedingungsanfragen.
4.1.2. Mehrdimensionaler B-Baum
Diese erweiterte Variante der B-Baum-Technik wurde von der Firma Tandem entwickelt. Ein mehrdimensionaler B-Baum ist auf mehreren Spalten (Dimensionen) definiert. Mehrdimensionaler Zugriff mittels B-Baumes ermöglicht einen effizienten Clustered-Zugriff auf Datenbanken, während andere DB-Managmentsysteme mit der üblichen B-Baum Technik die gesamte Tabelle zu lesen haben oder eine sekundäre Indexierung erfordern.
In [Les95] haben die Autoren mehrere Vorteile von MDAM dem standardisierten B-Baum entgegenstellt:
- Anordnen der Prädikate auf Schlüsselattributen
- Fehlen der Prädikate auf Schlüsselattributen
- IN-Liste auf mehreren Schlüsselattributen
- NOT-Prädikate
- Mehrwertige Prädikate
- Reduzierung der redundanten Prädikate
- Reduzierung der Nullmenge
- Direkter (sparse) und indirekter (dense) Zugriff
...
05.06.98
[Next] [Previous] [Up] [Top] [Contents] [Index]