Dr. Brigitte Mathiak Kapitel 10 Physische Datenorganisation

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