Dr. Brigitte Mathiak
Kapitel 10
Physische Datenorganisation
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 2
Lernziele
• Indexe
• Wie sie funktionieren (B+ Bäumen, Hashing)
• Was sie bringen
• Wie man das misst
• Organisation von mehrdimensionalen Datenstrukturen
Motivation
Datenbanken sind nicht automatisch schnell
Um ein bestimmtes Datenelement zu finden muss im Zweifelsfall die gesamte Datenbank durchsucht werden. Im Falle eines Joins vielleicht sogar mehrmals.
Der größte bottle neck dabei ist in der Praxis die Festplatte*. Idealerweise kann jedes Datenelement mit nur einem Zugriff gefunden werden.
Um das zu realisieren gibt es eine Anzahl von algorithmischen „Tricks“ beispielsweise Indexe und Caching.
Wir betrachten hier Indexe, da Caching im Allgemeinen auch ohne Eingriffe gut funktioniert.
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 3
Wie schnell ist meine Suche?
Es gibt 2 Methoden die Geschwindigkeit eines Algorithmus zu messen:
1. Benchmarking: Dabei wird eine standardisierte Anfrage auf einem standardisierten System ausgeführt und dabei die Zeit gemessen. Nachteil: Es gibt relativ viele Störfaktoren, z.B. Betriebssystem, Hardwareweiterer Nachteil: Es kann nur eine Aussage zu genau dieser Konfiguration getroffen werden
2. Mathematische Laufzeitanalyse: Dabei wird untersucht wie der Algorithmus selbst sich verhältNachteil: Es gibt in der Realität Störfaktoren, die nicht mit einfließen (z.B. Festplattenzugriffe vs. RAM)Vorteil: Man erhält eine Einschätzung wie gut das System im Extremfall funktioniert (Achtung! Oft zu optimistisch)
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 4
O-Notation
Die O-Notation gibt eine Einschätzung der Komplexitätsklasse des Algorithmus. Formal ist es eine Funktion von n
Beispiele: O(n), O(n²), O(log n), …n ist dabei die Variable, normalerweise Länge der Eingabe Beispiel: Anzahl der Datenelemente, Länge des Textes, …Die Komplexitätsklasse bezieht sich normalerweise auf die
Laufzeit, manchmal auch auf den Speicherbedarf, oder was auch immer knapp ist
Definition: f(n) = O(g(n)) gdw. Es existiert K, n0, so dass |f(n)| = K |g(n)| für alle n > n0
Anschauung: Für ausreichend große n wächst g(n) wie f(n)
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 5
Beispiel
f(n) = 8n³ + n² + 76 ist O(n³) wegen f(n) < 85n³ für alle n > 1
Graphische Bedeutung:
O-Notation betont die dominante Größe im Wachstum
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 6
Rechenbeispiele
3n² = O(n²)
Regel: konstante Faktoren werden auf 1 gesetzt
n² + n = O(n²)
Regel: Bei f(n) = g(n)+ h(n) und O(g(n))>O(h(n)) gilt f(n) = O(g(n))
Dabei gilt O(1)<O(log n)<O(n)<O(n log n)<O(n)<O(n²) …
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 7
Laufzeitanalyse
Man zählt die Anzahl der Schritte in Abhängigkeit von n und unterwirft die der O-Notation. Dabei zählt stets der schlechteste Fall.
Beispiel:
int max = 0; // 1 Schrittfor (int i=0;i<n;i++) // n-malif (a[i]>max) max=a[i]; // 1 oder 2 Schritte
Läuft in 1+n*(1 oder 2) = O(1+2n) = O(2n) = O(n)
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 8
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 9
Einfacher Index: Binäre Suchbaum
Schlüssel (mit den ihnen zugeordneten Daten) bilden die Knoten eines binären Baumsmit der Invariante: für jeden Knoten t mit Schlüssel t.key und alle Knoten l im linken Teilbaum von t, t.left, und alle Knoten r im rechten Teilbaum von t gilt: l.key t.key r.key
Worst-Case-Suchzeit für n Schlüssel: O(n)bei geeigneten Rebalancierungsalgorithmen (AVL-Bäume, Rot-Schwarz-Bäume, usw.): O(log n)
Suchen eines Schlüssels k: Traversieren des Pfades von der Wurzel bis zu k bzw. einem BlattEinfügen eines Schlüssels k: Suchen von k und Anfügen eines neuen BlattsLöschen eines Schlüssel k: Ersetzen von k durch das „rechteste“ Blatt links von k
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 10
Beispiel für einen binären Suchbaum
London, Paris, Madrid, Kopenhagen, Lissabon, Zürich, Frankfurt, Wien, Amsterdam, Florenz
London
Paris
Madrid
Kopenhagen
Lissabon ZürichFrankfurt
WienAmsterdam
Florenz
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 11
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 12
S.. SuchschlüsselD..
Weitere Daten
V.. Verweise (SeitenNr)
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 13
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 14
Einfügen eines neuen Objekts (Datensatz) in einen B-Baum
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 15
Sukzessiver Aufbau eines B-Baums vom Grad k=2
10 13 19
7
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 16
Sukzessiver Aufbau eines B-Baums vom Grad k=2
7 10 13 19
3
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 17
Sukzessiver Aufbau eines B-Baums vom Grad k=2
7 10 13 19
3
?
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 18
Sukzessiver Aufbau eines B-Baums vom Grad k=2
7 10
3
13 19
?
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 19
Sukzessiver Aufbau eines B-Baums vom Grad k=2
3 7
3
13 19
?10
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 20
Sukzessiver Aufbau eines B-Baums vom Grad k=2
3 7 13 19
?10
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 21
Sukzessiver Aufbau eines B-Baums vom Grad k=2
3 7 13 19
?10
1
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 22
Sukzessiver Aufbau eines B-Baums vom Grad k=2
3 7 13 19
?10
1
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 23
Sukzessiver Aufbau eines B-Baums vom Grad k=2
3 7 13 19
?10
1
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 24
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 3 7 13 19
?10
1
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 25
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 3 7 13 19
?10
2
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 26
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 3 7 13 19
?10
2
2
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 27
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 3 7 13 19
?10
2
2
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 28
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 3 7 13 19
?10
4
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 29
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 3 7 13 19
?10
4
4
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 30
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 3 7 13 19
?10
4
4
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 31
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 3 7 13 19
?10
4
4
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 32
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 3 7 13 19
?3 10
4
4
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 33
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 13 19
?3 10
4 7
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 34
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 13 19
?3 10
11
4 7
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 35
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 11 13 19
?3 10
4 7
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 36
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 11 13 19
?3 10
21
4 7
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 37
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 11 13 19
?3 10
21
4 7
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 38
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 11 13 19 21
?3 10
12
4 7
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 39
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 11 13 19 21
?3 10
12
4 7 12
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 40
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 11 13 19 21
?3 10
12
4 7 12
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 41
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 11 13 19 21
?3 10
12
4 7 12
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 42
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 11 13 19 21
?3 10 13
12
4 7 12
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 43
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 11 19 21
?3 10 13
12
4 7 11 12
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 44
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 19 21
?3 10 13
12
4 7 11 12
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 45
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 19 21
?3 10 13
14
4 7 11 12
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 46
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 14 19 21
?3 10 13
14
4 7 11 12
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 47
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 14 19 21
?3 10 13
15
4 7 11 12
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 48
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 14 15 19 21
?3 10 13
20
4 7 11 12
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 49
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 14 15 19 21
?3 10 13
20
4 7 11 12
20
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 50
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 14 15 19 21
?3 10 13
20
4 7 11 12
20
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 51
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 14 15 19 21
?3 10 13 19
20
4 7 11 12
20
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 52
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 14 15
?3 10 13 19
20
4 7 11 12
20 21
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 53
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 14 15
?3 10 13 19
5
4 7 11 12
20 21
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 54
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 14 15
?3 10 13 19
5
4 7 11 12
20 21
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 55
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 14 15
?3 10 13 19
5
4 5 7 11 12
20 21
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 56
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 14 15
?3 10 13 19
6
4 5 7 11 12
20 21
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 57
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2 14 15
?3 10 13 19
6
4 5 6 7 11 12
20 21
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 58
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
14 15
?3 10 13 19
4 5 6 7 11 12
20 21
8
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 59
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
14 15
?3 10 13 19
4 5 6 7 11 12
20 21
8
8
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 60
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
14 15
?3 10 13 19
4 5 6 7 11 12
20 21
8
8
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 61
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
14 15
?3 10 13 19
4 5 6 7 11 12
20 21
8
8
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 62
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
14 15
?3 10 13 19
6 7 11 12
20 21
8
84 5
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 63
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
14 15
?3 10 13 19
7 8 11 12
20 21
6
64 5
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 64
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
14 15
?3 10 13 19
7 8 11 12
20 21
6
4 5
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 65
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
14 15
?3 10 13 19
7 8 11 12
20 21
6
4 5
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 66
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
14 15
?3 10 13 19
7 8 11 12
20 21
6
4 5
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 67
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
14 15
?3 10 13 19
7 8 11 12
20 21
6
4 5
3 6
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 68
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
14 15
?13 19
7 8 11 12
20 21
10
4 5
3 6
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 69
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
14 15
?13 19
7 8 11 12
20 21
4 5
3 6
10
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 70
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
14 15
?13 19
7 8 11 12
20 21
4 5
3 6
10
10
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 71
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
14 15
?13 19
7 8 11 12
20 21
4 5
3 6
10B-Baum mit Minimaler
Speicherplatz-ausnutzung
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 72
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
14 15
?13 19
7 8 11 12
20 21
4 5
3 6
10
23
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 73
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
14 15
?13 19
7 8 11 12
20 21 23
4 5
3 6
10
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 74
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
14 15
?13 19
7 8 11 12
20 21 23
4 5
3 6
10
14
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 75
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
14 15
?13 19
7 8 11 12
20 21 23
4 5
3 6
10
14
Unterlauf
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 76
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
15
?13 19
7 8 11 12
20 21 23
4 5
3 6
10
Unterlauf
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 77
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
15 19
?13 20
7 8 11 12
21 23
4 5
3 6
10
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 78
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
15 19
?13 20
7 8 11 12
21 23
4 5
3 6
10
5
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 79
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
15 19
?13 20
7 8 11 12
21 23
4 5
3 6
10
5
Unterlauf
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 80
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
15 19
?13 20
7 8 11 12
21 23
4
3 6
10
merge
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 81
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
15 19
?13 20
7 8 11 12
21 23
4
3 6
10
merge
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 82
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
15 19
?13 20
11 12
21 23
4 6 7 8
3
10Unterlauf
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 83
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
15 19
?13 20
11 12
21 23
4 6 7 8
3
10merge
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 84
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
15 19
?13 20
11 12
21 23
4 6 7 8
3
10merge
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 85
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
15 19
?
11 12
21 23
4 6 7 8
3 10 13 20
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 86
Sukzessiver Aufbau eines B-Baums vom Grad k=2
1 2
15 19
?
11 12
21 23
4 6 7 8
3 10 13 20
Schrumpfung,Freie Knoten
• Die Höhe h ist bei Grad t und n Einträgen
• Daher dauert die Suche O(log n)
• Beim Einfügen kommt evtl. ein split dazu O(1)• Beim Löschen ein evtl. merge O(1)
Alle Operationen dauern O(log n)
• Allerdings können so nur Zahlen gespeichert werden.
B-Baum (Eigenschaften)
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 87
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 88
B+-Baum
Referenz-schlüssel
Such-schlüssel
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 89
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 90
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 91
Hashing
Bäume: logk(n) viele Seitenzugriffe ..
Hashing: Fast eindeutige Zuordnung von Datum zu Bucket (Behälter) h: S → B
- S Schlüssel (in diesem Kontext hier: nicht notwendigerweise Schlüssel im Sinne eines logischen Schema)
- B: Nummerierung von n Behältern- Zugriff innerhalb von 1-2 Schritten
- Charakteristiken der gesuchten Hash-Funktion• Fester vs flexibler Wertebereich• Gute Verteilung über den Wertebereich, auch bei schlechter Verteilung
der Datencharakteristiken über den Eingabebereich
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 92
Hashing
Abbildung h: D [0..m-1], genannt Hash-Funktion,von Schlüsseln x1, ..., xn aus Domain D (z.B. Strings)
auf Positionenh(x1), ..., h(xn) in Array a[0..m-1], genannt Hash-Tabelle
Speicherung von Schlüssel xi in a[h(xi)]
Anforderungen an h: sehr effiziente Berechenbarkeit gute „Streuung“ (Pseudo-Randomisierung) von x1, ..., xn auf [0..m-1] Urbilder von j1, j2 [0..m-1] annähernd gleich groß für alle j1, j2 und alle möglichen
x1, ..., xn
für geordnete Schlüssel x1 < x2 < ... < xn sollte die Ordnung von h(x1), h(x2), ..., h(xn) eine zufällige Permutation sein
Pearson hashingIst eine häufig benutzte Hashfunktion um Nachrichten xi auf 8 Bit abzubildenh=0for each byte b in xi loop
h = T[h xor b];T ist dabei eine ein Array gefüllt mit einer zufälligen Permutation der Zahlen 0 bis 256
Kollisionsbehandlung
Trotz der möglichst gleichen Verteilung, ist es recht wahrscheinlich, dass es zu einer Kollision kommt O(Wurzel n)
Um diese aufzufangen, haben die einzelnen Buckets eine Liste
von Werten
Ist diese Liste voll, wird dynamisch eine neue Liste erstellt, in die dann die zusätzlichen Werte kommen.
Damit werden die Buckets zur „Verketteten Liste“
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 93
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 94
Statisches Hashing
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 95
Hashfunktion für erweiterbares Hashing
h: Schlüsselmenge {0,1}*Der Bitstring muss lang genug sein, um alle Objekte auf ihre
Buckets abbilden zu könnenAnfangs wird nur ein (kurzer) Präfix des Hashwertes (Bitstrings)
benötigtWenn die Hashtabelle wächst wird aber sukzessive ein längerer
Präfix benötigtBeispiel-Hashfunktion: gespiegelte binäre PersNr
h(004) = 001000000... (4=0..0100) h(006) = 011000000... (6=0..0110) h(007) = 111000000... (7 =0..0111) h(013) = 101100000... (13 =0..01101) h(018) = 0100100000... (18 =0..010010) h(032) = 000001000... (32 =0..0100000) h(048) = 000011000... (48 =0..0110000)
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 96
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 97
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 98
0 1
0 1
0 1
Bucket
Bucket
Bucket
Bucket
Bucket
Bucket
1
1 11
0
0007 13
6 18
32 48
4
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 99
0 1
0 1
0 1
Bucket
Bucket
Bucket
Bucket
Bucket
Bucket
1
1 11
0
000
001 110
Präfix001
Präfix1
7 13
6 1832 48
4
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 100
SQL: Create Index
Grobsyntax:
CREATE [UNIQUE] INDEX Indexname ON Tabellenname (Attribut1, Attribut2 ..)
DROP INDEX Indexname
Primary Key hat immer einen Index (muss nicht explizit indexiert werden)
.. Oracle: default-Indextyp ist ein B+ Baum
Beispiele:
CREATE INDEX Studenten_idx1 ON Studenten(Semester)
DROP INDEX Studenten_idx1
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 101
Oracle Clusters und Indexierung
Mit einem B+ Baum:
CREATE CLUSTER cluster name ( attribute type, ... );CREATE INDEX index name ON cluster name;CREATE TABLE table name ( usual parameters)
CLUSTER cluster name ( attribute name );
Mit Hashing:
CREATE CLUSTER cluster name ( attribute type, ... ) [HASH IS hashfunktion] HASHKEYS anzahl;
CREATE TABLE table name ( usual parameters) CLUSTER cluster name ( attribute name );
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 102
Oracle Clusters: Beispiel
CREATE CLUSTER ProfessorenVorlesungen (PersNo NUMBER) HASH IS PersNo HASHKEYS 150;
CREATE TABLE Vorlesungen (GelesenVon NUMBER, ... ) CLUSTER ProfessorenVorlesungen (GelesenVon);
Fazit
Indexe beschleunigen die Zugriffszeiten auf große Datenmengen
Nachteil ist der zusätzlich benötigte Speicherplatz
B-Bäume sind optimal geeignet für Bereichsabfragen… WHERE value > 465Und verbrauchen recht wenig Extraspeicher.
Hashing ist optimal geeignet für Einzelwertabfragen… WHERE value = 465Sie verdoppeln für den Speicherverbrauch in etwa.
Primary Keys werden in dem meisten DBs automatisch mit Index versehen. Mit welchem?
Datenbanken für Mathematiker, WS 11/12 Kapitel 10: Datenorganisation 103