Data Warehouse Technologien

• Ein eindimensionaler (im Idealfall clusternder) Primärindex liest nicht

mehr alle Werte, sondern beschränkt dies auf einen Bereich in einer Di-

mension. Im Beispiel werden nur die angefragten Tage gelesen, aber eben

für alle Produkte.

• Mehrere Sekundärindexe auf den Dimensionsattributen können wie folgt

genutzt werden:

1. In jeder Dimension wird der Bereich ausgewertet. Resultat ist jeweils

eine TID-Liste.

2. Bildung der Schnittmenge dieser Listen.

3. Lese die zu den TID gehörigen Tupel.

Da TID deutlich kleiner sind als ganze Tupel, ist das eine effiziente Vorge-

hensweise, bei der aber trotzdem sehr viel TIDs (grafisch hervorgehoben)

zwischengespeichert und verarbeitet werden müssen. Genau genommen

müsste man daher für die graphische Hervorhebung einen abweichenden

Grauton wählen, da ja nicht ganze Tupel, sondern nur TID gelesen und

verarbeitet werden.

• Ein echt mehrdimensionaler Index liefert direkt den gesuchten Bereich.

In den folgenden Abschnitten werden wir exemplarisch einige in DW-Systemen

verwendete bzw. gut einsetzbare Indexverfahren betrachten.

7.2 B-Bäume und Varianten

B-Bäume und ihre Varianten sind die allgegenwärtigen Arbeitspferde in Daten-

banksystemen. B-Bäume sind eindimensionale Baumstrukturen und daher für

mehrdimensionale Anfragen nur indirekt nutzbar. Dem gegenüber steht ihre

Verfügbarkeit und ausgefeilte Implementierung in existierenden Systemen.

Wir werden B-Bäume nicht ausführlich behandeln, da dies ausführlicher

Stoff in allen Büchern zum Thema „Datenbankimplementierung“ ist (etwa im

Buch [SSH11]). Stattdessen werden wir nur kurz die Grundprinzipien reka-

pitulieren, und uns dann auf spezielle Aspekte im Zusammenhang mit DW-

Systemen beschränken.

Abbildung 7.2 zeigt einen B-Baum für ganze Zahlen der Ordnung 2. Die

Ordnung eines B-Baumes ist die minimale Anzahl der Einträge auf den In-

dexseiten (außer der Wurzelseite). Formal ist ein Indexbaum ein B-Baum der

Ordnung m, wenn

• jede Seite höchstens 2m Elemente enthält,

• jede Seite außer der Wurzelseite mindestens m Elemente enthält,

198 7 Indexstrukturen