Vorlesung Datenbanksysteme vom
11.10.2004
Physische Datenorganisation
Speicherhierarchie
Hintergrundspeicher / RAID
B-Bäume
Hashing
R-Bäume
Architektur eines DBMS
Interactive Abfrage
API/Präcompiler
Verwaltungswerkzeug
DML-Compiler
DDL-Compiler
Abfrageoptimierung
Datenbankmanager
Schemaverwaltung
Mehrbenutzersynchronisation
Fehlerbehandlung
Dateiverwaltung
Logdateien
Indexe
Datenbasis
Data Dictionary
2
Überblick: Speicherhierarchie
1-10ns
Register
10-100ns
Cache
100-1000ns
Hauptspeicher
10 ms
Plattenspeicher
Zugriffslücke
105
sec
3
Random versus Chained IO
 1000 Blöcke à 4KB sind zu lesen
 Random I/O
Jedesmal Arm positionieren
Jedesmal Latenzzeit
 1000 * (5 ms + 3 ms) + Transferzeit von 4 MB
 > 8000 ms + 300ms  8s
 Chained IO
Einmal positionieren, dann „von der Platte kratzen“
 5 ms + 3ms + Transferzeit von 4 MB
 8ms + 300 ms  1/3 s
 Also ist chained IO ein bis zwei Größenordnungen
schneller als random IO
 in Datenbank-Algorithmen unbedingt beachten !
4
Disk Arrays  RAID-Systeme
5
Systempuffer-Verwaltung
einlagern
Hauptspeicher
verdrängen
Platte ~ persistente DB
6
B-Bäume
Balancierte Mehrwege-Suchbäume
Für den Hintergrundspeicher
D..
Weitere Daten
S..
Suchschlüssel
V..
Verweise
(SeitenNr)
8
9
Speicherstruktur eines B-Baums
auf dem Hintergrundspeicher
8 KB-Blöcke
0*8KB
1*8KB
2*8KB
3*8KB
4*8KB
3
0
BlockNummer
1
1
0
1
0
0
1
1
0
Datei
10
Zusammenspiel:
Hintergrundspeicher -- Hauptspeicher
Hintergrundspeicher
HauptspeicherPuffer
4
4
Zugriffslücke 105
11
B+-Baum
Referenzschlüssel
Suchschlüssel
12
13
Mehrere Indexe auf denselben
Objekten
B-Baum
Mit
(PersNr, Daten)
Einträgen
Name, Alter, Gehalt ...
B-Baum
Mit
(Alter, ???)
Einträgen
Alter, PersNr
14
Eine andere Möglichkeit:
Referenzierung über Speicheradressen
PersNr
007,...
Alter
20,...
007, Bond, 20, ...
15
16
Statisches
Hashing
17
Erweiterbares
Hashing
1
0
1
0
1
0
binärer
Trie,
Entscheidungsbaum
Directory
Bucket
Bucket
Bucket
Bucket
Bucket
Bucket
18
19
20
R-Baum: Urvater der baum-strukturierten
mehrdimensionalen Zugriffsstrukturen
[18,60]
[60,120]
60
120K
Bond
20
80K
Mini
43
70K
Mickey
18
60K
Duck
60
Bond
Mickey
40
Alter
Duck
20
40K
60K
Mini
80K
Gehalt
100K
120K
21
Gute versus schlechte
Partitionierung
gute Partitionierung
schlechte Partitionierung
Bond
Bond
Mickey
Mickey
Duck
Mini
Gehalt
Alter
Alter
Speedy
Speedy
Duck
Mini
Gehalt
22
Nächste Phase in der
Entstehungsgeschichte des R-Baums
[18,43]
[40,60]
[60,80] [100,120]
20
80K
Mini
60
120K
Bond
43
70K
Mickey
18
60K
Duck
Bert
40
100K
Speedy
(noch nicht
eingefügt)
Bond
Mickey
Alter
Speedy
Duck
Mini
Gehalt
23
Bereichsanfragen auf dem R-Baum
Anfragefenster
[18,50] [25,65]
[45,80] [95,120]
Lucie
Bond
Sepp
Bert
[41,45]
[41,50]
[60,80]
[45,55]
[60,70]
Mickey
[25,60]
[40,65]
[110,120] [95,100]
Alter
[18,20]
Ernie
Jan
Speedy
Urmel
Duck
Mini
43
70K
Mickey
41
60K
Jan
50
65K
Sepp
Bill
Gehalt
...
40
100K
Speedy
65
95K
Lucie
24
Objektballung / Clustering logisch
verwandter Daten
25
26
Clustering von Professoren mit ihren Vorlesungen
27
Unterstützung eines
Anwendungsverhaltens
Select Name
From Professoren
Where PersNr = 2136
Select Name
From Professoren
Where Gehalt >= 90000 and Gehalt <= 100000
28
Indexe in SQL
Create index SemsterInd
on Studenten
(Semester)
drop index SemsterInd
29

Wiederholung vom 11.10.2004