In diesem Vortrag betrachten wir das Problem, zu einer gegebenen Menge
von Datensätzen eine neue externe Indexstruktur aufzubauen. Dabei gehen
wir davon aus, daß aufgrund des hohen Datenvolumens ein kompletter
Aufbau im Hauptspeicher nicht möglich ist. Diese Problemstellung tritt
insbesondere in großen Datenbanken auf. Es wird ein neues Verfahren zum
Aufbau von Indexstrukturen vorgestellt, das im Unterschied zu anderen
Verfahren auf eine Klasse von Strukturen anwendbar ist. In dieser Klasse
befinden sich klassische Indexstrukturen wie der B+-Baum, aber auch
mehrdimensionale und räumliche Indexstrukturen wie der R-Baum. Das
generische Verfahren basiert nicht auf externen Sortierverfahren (wie z.
B. Verfahren zum Aufbau von B+-Bäumen), sondern partitioniert die Daten
mittels der Routinen, die in der aufzubauenden Indexstruktur bereits
vollständig implementiert sind. Für Indexstrukturen, die über eine
effiziente Routine zum Einfügen eines Datensatzes verfügen, kann gezeigt
werden, daß die Laufzeit des Verfahrens im worst-case asymptotisch
optimal ist. Experimente mit einer Implementierung unseres Verfahrens
geben auch erste Hinweise auf die durchschnittliche Leistungsfähigkeit.