Data Warehouse Technologien

dass mehrere Dimensionen derart kodiert werden, und ein nachbarschaftser-

haltender mehrdimensionaler Index eingesetzt wird. Im konkreten Fall des

MDH handelt es sich dabei um den UB-Baum.

7.7 Vertiefende Literatur

Die meisten präsentierten Indexstrukturen werden in [SSH11] ausführlich vor-

gestellt. B-Bäume wurden von Bayer und McCreight in [BM72] eingeführt. Vie-

le Datenbanklehrbücher enthalten Abschnitte über Zugriffsstrukturen, so die

Bücher von Kemper und Eickler [KE04], von Elmasri und Navathe [EN02] und

von Silberschatz, Korth und Sudarshan [SKS97].

Tharp [Tha88] präsentiert ausführlich Dateistrukturen bis hin zu Grid-

Files und die zugehörigen Operationen wie Einfügen, Suchen und Sortieren.

Auf Bitmaps basierende Indexe wurden bereits früh vorgeschlagen, und wer-

den zum Beispiel im Buch von Wedekind und Härder diskutiert [WH76]. Der

Einsatz von Bitmap-Indexen in Oracle8 wird zum Beispiel in [CHRS98] disku-

tiert. Wu und Buchmann beschreiben in [WB98] den Einsatz kodierter Bitmap-

Indexe. Mehrkomponentenindexe werden von Chan und Ioannidis in [CI99]

vorgestellt. Der klassische Verbundindex stammt von Valduriez[Val87].

Eine frühe umfassende Aufbereitung des Standes der Forschung und eine

Klassifikation mehrdimensionaler Zugriffsmethoden geben Gaede und Günther

in [GG98]. Vorschläge für dynamische, multidimensionale Hash-Verfahren wur-

den insbesondere von Lloyd und Ramamohanarao [LR82] sowie Otoo [Oto84]

veröffentlicht. Auch Kriegel und Seeger behandeln mehrdimensionale dynami-

sche Hash-Verfahren [KS86]. Die von uns vorgestellte Variante MDH wurde

von Kuchen im Rahmen des MEMODAX-Projekts an der RWTH Aachen entwi-

ckelt und prototypisch realisiert [Kuc85]. Das Buch von Samet [Sam89] behan-

delt mehrere mehrdimensionale Zugriffsverfahren im Detail.

Grid-Files als dynamische und mehrdimensionale Zugriffsverfahren wur-

den von Nievergelt et al. in [NHS84] eingeführt. Hinrichs [Hin85] behandelt

als Erweiterung mehrstufige Grid-Files.

Der K-D-B-Baum als Vorläufer des vorgestellten KdB-Baums stammt von

Robinson [Rob81]. Der KdB-Baum ist die Erweiterung nach Kuchen [Kuc85].

Die R-Bäume wurden von Guttman in [Gut84] vorgeschlagen und seit-

dem vielfältig variiert. Für weiterführende Erläuterungen wird das Buch „R-

Trees: Theory and Applications (Advanced Information and Knowledge Pro-

cessing)“ [MNPT05] angeraten. Der R

∗

a

-Baum wurde von Jürgens und Lenz

1998 vorgeschlagen [JL98]. Der UB-Baum wurde von Bayer unter anderem in

[Bay97, BM98] beschrieben.

Das multidimensionale hierarchische Clustern MHC wurde von Markl et

al. unter anderem in [MRB99] beschrieben.

228 7 Indexstrukturen