B-Bäume und Datenbanken

Proseminar »Meilensteine aus 60 Jahren Softwareentwicklung«

Lars Trebing, 17. 12. 2002


Überblick


Vorbemerkung

Diese Seite entspricht im wesentlichen den Vortragsfolien zu meinem Seminarvortrag »B-Bäume und Datenbanken« am 17. Dezember 2002. Stellenweise habe ich sie noch um ein, zwei ausformulierte Sätze ergänzt; dennoch ist sie für »Außenstehende«, die den Vortrag nicht gehört haben und denen das Thema nicht geläufig ist, vermutlich nicht sehr hilfreich.

Voraussetzungen: Technik

19692002Faktor
Hauptspeicher200 KB2 GB104
Festplattengröße7,5 MB75 GB104
Übertragungsrate150 KB/s15 MB/s103
Zugriffszeit50 ms5 ms10−1

Bislang waren als Massenspeicher praktisch nur Magnetbänder eingesetzt worden. Die ersten Festplatten kamen auf den Markt (ursprünglich zur Speicherung des Betriebssystems); die weitere Verbreitung von Festplatten-Speichertechnik war aber absehbar.


Voraussetzungen: Anwendungsgebiete


»Herkömmliche« sortierte Binärbäume

[Illustration] Binärbaum


B-Bäume: Grundidee

1969 konzipierten Rudolf Bayer und Edward McCreight bei Boeing die selbstausgleichenden B-Bäume. (»B-Bäume« sind keine Binärbäume – das »B« kann z. B. als »Bayer« oder »Balanced« aufgefaßt werden.)

[Illustration] B-Baum


B-Bäume: Eigenschaften


Beispiel: B-Baum mit Seitengröße 8 KB

HöheKnotenGröße
118 KB
24003,2 MB
3160 0001,3 GB
464 000 000512 GB

Datenbankmodelle

1969 gab es im wesentlichen zwei Datenbanksysteme:

IMS (IBM)

CODASYL-Datenbank


Relationales Datenbankmodell


Entwicklung bis heute