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
| 1969 | 2002 | Faktor |
|---|
| Hauptspeicher | 200 KB | 2 GB | 104 |
|---|
| Festplattengröße | 7,5 MB | 75 GB | 104 |
|---|
| Übertragungsrate | 150 KB/s | 15 MB/s | 103 |
|---|
| Zugriffszeit | 50 ms | 5 ms | 10−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
- Haupteinsatzgebiet für Datenbanksysteme: Luft- und Raumfahrtindustrie (Teileverwaltung, Explosionszeichnungen …)
- Geschäftsprozesse papierbasiert
- keine Buchungen (Zahlungen, Reservierungen …) in Echtzeit
![[Illustration] Binärbaum](bintree.gif)
- Problem: Im ungünstigsten Fall wächst ein Binärbaum nur in eine Richtung und mutiert praktisch zu einer verketteten Liste; die Suchkomplexität beträgt dann O(n) statt O(ld n).
- → Regelmäßiges »Aufräumen« ist erforderlich, um den Binärbaum wieder auszubalancieren.
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](btree.gif)
- B-Bäume wachsen im Gegensatz zu natürlichen Bäumen und herkömmlichen Baumstrukturen nicht von der Wurzel weg
- stattdessen werden Knoten aufgespaltet; diese Aufspaltung setzt sich gegebenenfalls bis zur Wurzel fort
- → automatische Ausgeglichenheit
B-Bäume: Eigenschaften
- Speicherplatzausnutzung im schlechtesten Fall nur 50 %; (später auf rund 83 % verbessert)
- das Problem des Platzbedarfs und das eigenartige Wachstum führten dazu, daß das Konzept erst 1972 mit Unterstützung von Don Knuth akzeptiert wurde
- Komplexität von Elementaroperationen: O(logk n)
- heutzutage typische Werte für k: über 400 (auf die Größe eines Festplattenblocks abgestimmt)
Beispiel: B-Baum mit Seitengröße 8 KB
| Höhe | Knoten | Größe |
|---|
| 1 | 1 | 8 KB |
|---|
| 2 | 400 | 3,2 MB |
|---|
| 3 | 160 000 | 1,3 GB |
|---|
| 4 | 64 000 000 | 512 GB |
|---|
- sehr wenige Lese- und Schreibzugriffe je Elementaroperation (Suchen, Einfügen, Löschen) nötig
- nur die untersten Ebenen müssen auf Festplatte ausgelagert werden; dadurch noch weniger Zugriffe
Datenbankmodelle
1969 gab es im wesentlichen zwei Datenbanksysteme:
- Für Speicherung auf Magnetbändern ausgelegt; Datenbanksprache DL/I, eingebettet in COBOL-, Fortran- oder PL/I-Programme
- wirtschaftlich bis heute sehr erfolgreich
CODASYL-Datenbank
- Ersetzung von Hierarchien durch Netzwerke
- Datenbanksprache beruht auf Manipulation von Zeigern; dadurch sehr unübersichtliche Programme
Relationales Datenbankmodell
- Ted Codd, 1969
- Verknüpfung mehrerer Datentabellen über relationale Algebra
- Anfängliche Schwierigkeiten durch IBM-interne (IMS) und externe Konkurrenz (CODASYL)
- Entwicklung von IBM Research Storage System (B-Baum-basiert) – bald in »Relational Storage System« umbenannt – als datenbankunabhängige Plattform; dadurch umgingen die IBM-Manager die vorzeitige Entscheidung für ein Datenbanksystem
- Heutige Popularität relationaler Datenbanken durch SQL (Don Chamberlin, Ray Boyce)
Quellen und weitere Informationen
