Index- und Speicherstrukturen

In vielen Informatikanwendungen treten extrem gro\xa7 e Datenmengen auf, die aus Kostengründen auf einem Externspeicher (z. B. Magnetplattenspeicher) oder sogar Tertiärspeicher (z. B. Magnetbänder) verwaltet werden müssen. Da Externspeicher wesentlich langsamer als Hauptspeicher ist, ergeben sich daraus aber auch Performanceprobleme für die Anwendungen. Deshalb hat in den letzten 10 Jahren die Entwicklung von effizienten externen Datenstrukturen und Algorithmen an Bedeutung gewonnen, die speziell für die Verwaltung von Daten auf dem Externspeicher entworfen werden.

In dieser Vorlesung werden wichtige externe Datenstrukturen vorgestellt. Es wird insbesondere auf externe Sortierverfahren, B-Bäume und mehrdimensionale Indexstrukturen eingegangen. Zudem wird auch die Architektur von parallelen Externspeichern (z. B. RAID-Platten) erläutert und entsprechende parallele Datenstrukturen vorgestellt.

Vorlesungstermin:

• freitags 8:30 - 10:00 Uhr

• Informatik II

• Datenbanksysteme I

• Erfolgreiche Abgabe von Übungsaufgaben und mündliches Kolloquium

• Betty Salzberg:''File Structures: An Analytical Approach'',Prentice-Hall
• Gio Wiederhold: ``Database Design'', McGraw-Hill
• D. Knuth: ``The Art of Computer Programming'', Vol. 3: Sorting and Searching, Addison-Weseley, 1973.
• R. Güting: ``Datenstrukturen und Algorithmen'', Teubner, 1982.
• T. Ottmnan, P. Widmayer: ``Algorithmen und Datenstrukturen'', BI Wissenschaftsverlag

Komplettes Skript zur Vorlesung (im pdf-Format)

Hilbertkurve (C-Prozedur)

Last Modified: 07:39pm MET DST, June 27, 1996