Data Warehouse Technologien

Abbildung 7.3 zeigt einen B

+

-Baum der Ordnung 2. Der Eintrag 59 taucht

zweimal im Baum auf: einmal in einem inneren Blatt als Vergleichselement

und einmal im Blatt als Platzhalter für das referenzierte Datenelement.

B- und B

+

-Bäume sind eindimensionale Strukturen, und besonders für

eindimensionale Bereichsanfragen geeignet. Als Primärindexe unterstützen

insbesondere B

+

-Bäume sehr gut das Clustering auf der Blattebene. Der Re-

organisationsaufwand bei Änderung der Daten ist für DW-Systeme eher von

untergeordneter Bedeutung.

Der Nutzen von B-Bäumen für mehrdimensionale Fensteranfragen wurde

bereits kurz skizziert. Da B-Bäume in den meisten Systemen schon effizient

vorimplementiert sind, ist dieser Ansatz oft konkurrenzfähig zu eventuell neu

zu implementierenden mehrdimensionalen Indexstrukturen.

Als Fazit handelt es sich hier beim B

+

-Baum um eine robuste und generi-

sche Datenstruktur, die unabhängig vom konkreten Datentyp realisierbar ist –

nur eine Ordnung auf den Datenwerten ist erforderlich. Er zeichnet sich durch

effiziente Aktualisierungsalgorithmen aus und ist kompakt speicherbar. Gera-

de im DW-Bereich gibt es allerdings zwei Probleme, die wir im Folgenden ge-

nauer betrachten werden:

• Attribute mit geringer Kardinalität führen zu degenerierten Bäumen.

• Zusammengesetzte Indexe sind ordnungssensitiv bezüglich der Reihenfolge

der Attribute.

7.2.2 Degenerierte B-Bäume

B-Bäume für Attribute mit einer geringen Kardinalität führen zu Datenstruk-

turen, die zwar korrekt die Daten speichern, aber die Vorteile einer Baumstruk-

tur nicht mehr aufweisen. Man spricht dann von degenerierten B-Bäumen.

JBeispiel 7-1I Als Beispiel betrachten wir eine Tabelle Kunde unter anderem

mit einem Attribut geschlecht (m, w) für die Angabe des Geschlechts des Kun-

dens. Mittels

CREATE INDEX s

_

idx ON Kunde(geschlecht)

können wir jetzt einen Index anlegen, der als B-Baum realisiert wird. 2

Abbildung 7.4 zeigt den resultierenden, degenerierten Baum. Er besteht

nur aus einem Blatt mit zwei Vergleichselementen, jedem Element ist eine

(sehr lange) Liste von TIDs zugeordnet.

Ähnlich degenerierte Bäume würde man bei einem Index über ein Attribut

Bundesland erhalten.

200 7 Indexstrukturen