Aufgabe 1. Herausforderungen I Persistente Datenspeicherung: Möchte man jeden Morgen alle Käufe...

Aufgabe 1

2DBIS

Herausforderungen I

• Persistente Datenspeicherung: Möchte man jeden Morgen alle

Käufe und Verkäufe neu zusammensuchen?

• Sehr große Datenmengen: Welche Papierberge ergeben sich

wohl für alle Käufe und Verkäufe aller Aktien seit Beginn des

Aktienhandels?

• Sehr schneller Zugriff auf alle Daten: Wie lange Wartezeiten

sind akzeptierbar, wenn Sie Aktien kaufen wollen und den

aktuellen Kurs benötigen?

• Hohe Verfügbarkeit der Daten: Welche Geschäftszeiten sind im

internationalen Aktienmarkt vereinbar?

Wintersemester 15/16

3DBIS

Herausforderungen II

• Hohe Flexibilität beim Datenzugriff inklusive (automatischer)

Auswertung: Wer überwacht alle Käufe und Verkäufe und erstellt

dann die Charts über den Kursverlauf?

• Hohe Flexibilität bezüglich der Datenverteilung: Können alle

Daten im internationalen Aktienmarkt zentral verwaltet werden?

• Hohe Flexibilität bezüglich der Lastverteilung: Kann ein PC das

ganze Aktienwesen steuern? Was passiert, wenn dieser ausfällt?

• Hohe Benutzerfreundlichkeit des Datenhaltungssystems:

Möchten alle Käufer komplizierte Formeln (Code) eingeben, um z.B.

die aktuellen Kurse einzusehen?

Wintersemester 15/16

4DBIS

Herausforderungen III

• Sicherheit vor Datenverlust: Ist es akzeptabel, dass ein Aktienkauf auch mal

verloren geht? Was ist bei technischen Störungen?

• Sicherheit vor unberechtigtem Datenzugriff: Darf mein Nachbar wissen,

welche Aktien ich besitze?

• Paralleler Zugriff ohne Konflikte: Ist es vertretbar, dass immer nur eine Person

pro Zeiteinheit Aktien kaufen kann?

• Automatische Garantie semantischer Integrität: Kann ein Aktienkurs negativ

werden? Was passiert mit den Aktien eines Unternehmens, wenn es aufgekauft

wird?

• Hoher Grad an Datenunabhängigkeit: Muss/Kann man alle Anwendungen

ändern, wenn z.B. durch Gesetze neue Informationen zu Aktienkäufen

gespeichert werden müssen?

Wintersemester 15/16

Aufgabe 2

• 1-elementige Knoten haben maximal 2 Kinder (links, rechts)

• 2-elementige Knoten haben maximal 3 Kinder (da sie sich ein Kind teilen)

• 3-elementige Knoten haben maximal 4 Kinder

• Definition eines B-Baums mit Ordnung n:

• Jeder Weg von der Wurzel zum Blatt hat die gleiche Länge h.

• Jeder Knoten (außer Wurzel und Blätter) hat mindestens n+1 Söhne.

• Die Wurzel hat mindestens 2 Söhne.

• Jedes Blatt besitzt mindestens n Einträge.

• Jeder Knoten hat höchstens 2n+1 Söhne.

• Während der Entstehungsphase des Baumes kann es zu Verletzungen dieser

Bedingungen kommen (Initialfüllphase).

• Rückschluss aus „Regel für Höchstanzahl der Söhne:

• Gegeben: n = 3 Jeder Weg von der Wurzel zum Blatt hat die gleiche Länge h.

Jeder Knoten (außer Wurzel und Blätter) hat mindestens 4 Söhne.

Die Wurzel hat mindestens 2 Söhne.

Jedes Blatt besitzt mindestens 3 Einträge.

Jeder Knoten hat höchstens 7 Söhne.

Auf jeden Knoten passen maximal 6 Elemente.

7

Beginn der Füllung mit den Werten 5,7 und 21

5 21

5

Hinzufügen der Werte 2, 10, 76

2 7 21

52 7 10 21

52 7 10 21

77 Zu voll, umsortieren

76

Hinzufügen des Wertes 77

52 7 10 21 76

Mittleres Element

10

52 7 7621 77

Hinzufügen der Werte 3, 4, 9, 78

10

32 5 7 7621 77

10

32 4 5 7 7621 77

10

32 4 5 7 9 7621 77

10

32 4 5 7 9 7621 77 78

Hinzufügen des Wertes 1

10

32 4 5 7 9 7621 77 781

Zu voll, umsortieren Mittleres Element

4

21 3 75 9

Neuer Vater landet in übergeordneter Ebene

104

21 3 75 9 7621 77 78

Löschen des Wertes 76

104

21 3 75 9 7721 78

Löschen des Wertes 77

104

21 3 75 9 7821

Zu leer, umsortieren

104

21 3 75 9 7821

Nachbar bietet ausreichend Platz verschmelzen

75 9 10 21 78

4

21 3

Beispiel Kleine Rotation

Beispiel große Rotation

Aufgabe 3

Schritt 1 – Berechnung der Hashwerte

h(x) = x DIV 10

Werte: 42, 165, 211, 233, 255 und 82

42 DIV 10 = 4 R 2 4

165 DIV 10 = 16 R 5 16

211 DIV 10 = 21 R 1 21

233 DIV 10 = 23 R 3 23

255 DIV 10 = 25 R 5 25

82 DIV 10 = 8 R 2 8

Schritt 2 – Berechnung der Binärwerte zu den Hashwerten

Werte h(x): 4, 16, 21, 23, 25 und 8

Zahlen in Binär:

4 ≙ 0 0 1 0 0

24 23 22 21 20

0 * 16 + 0 * 8 + 1 * 4 + 0 * 2 + 0 * 1

Umrechnung z.B. über Divisionsrestverfahren:

4 MOD 2 = 2 R 0

2 MOD 2 = 1 R 0

1 MOD 2 = 0 R 1

100

vorn Nullen anstellen bis zur gegeben Länge: 00100

Leserichtung

4 = 00100

16 = 10000

21 = 10101

23 = 10111

25 = 11001

8 = 01000

Schritt 3 – Schrittweises Einfügen der Werte in den Bucket

Gegeben: Bucket-Kapazität b=3

Startsituation: leerer Bucket, lokale Tiefe 0

0

0

B1

042

0

B1

Einfügen der Werte 42, 165, 211

4 (00100)

042

0

165B1

4 (00100)16 (10000)

042

0

165

211

B1

4 (00100)16 (10000)

21 (10101)

Einfügen des Wertes 233

042

0

165

211

B1

4 (00100)16 (10000)

21 (10101)

Voll! Neuer Bucket, neue Tiefe(n)

0

1

1

1

B1

1

B2

0…

1

1…

1

B1

1

B2

Hashwerte, die binär mit 0 beginnen, kommen in Bucket 1.Hashwerte, die binär mit 1 beginnen, kommen in Bucket 2.

0…

1

1…

42

1

B1

1

B2

Hashwerte, die binär mit 0 beginnen, kommen in Bucket 1.Hashwerte, die binär mit 1 beginnen, kommen in Bucket 2.

4 (00100)

0…

1

1…

42

1

B1

165

1

B2

Hashwerte, die binär mit 0 beginnen, kommen in Bucket 1.Hashwerte, die binär mit 1 beginnen, kommen in Bucket 2.

4 (00100)

16 (10000)

0…

1

1…

42

1

B1

165

1

211B2

Hashwerte, die binär mit 0 beginnen, kommen in Bucket 1.Hashwerte, die binär mit 1 beginnen, kommen in Bucket 2.

4 (00100)

16 (10000)

21 (10101)

0…

1

1…

42

1

B1

165

1

211

233

B2

Hashwerte, die binär mit 0 beginnen, kommen in Bucket 1.Hashwerte, die binär mit 1 beginnen, kommen in Bucket 2.

4 (00100)

16 (10000)

21 (10101)23 (10111)

0…

1

1…

42

1

B1

165

1

211

233

B2

Einfügen des Wertes 255

4 (00100)

16 (10000)

21 (10101)23 (10111)

Voll! Neuer Bucket, neue Tiefe(n)

10..

01..

00..

11..

2

42

1

B1

2

B2

4 (00100)

2

B3

Hashwerte, die binär mit 0 beginnen, kommen in Bucket 1.Hashwerte, die binär mit 10 beginnen, kommen in Bucket 2.Hashwerte, die binär mit 11 beginnen, kommen in Bucket 3.

Magic! Unterschiedliche lokale Tiefen.

10..

01..

00..

11..

2

42

1

B1

165

2

B2

4 (00100)

2

B3

Hashwerte, die binär mit 0 beginnen, kommen in Bucket 1.Hashwerte, die binär mit 10 beginnen, kommen in Bucket 2.Hashwerte, die binär mit 11 beginnen, kommen in Bucket 3.

16 (10000)

10..

01..

00..

11..

2

42

1

B1

165

2

211B2

4 (00100)

2

B3

Hashwerte, die binär mit 0 beginnen, kommen in Bucket 1.Hashwerte, die binär mit 10 beginnen, kommen in Bucket 2.Hashwerte, die binär mit 11 beginnen, kommen in Bucket 3.

16 (10000)

21 (10101)

10..

01..

00..

11..

2

42

1

B1

165

2

211

233

B2

4 (00100)

2

B3

Hashwerte, die binär mit 0 beginnen, kommen in Bucket 1.Hashwerte, die binär mit 10 beginnen, kommen in Bucket 2.Hashwerte, die binär mit 11 beginnen, kommen in Bucket 3.

16 (10000)

21 (10101)23 (10111)

10..

01..

00..

11..

2

42

1

B1

165

2

211

233

B2

4 (00100)

255

2

B3

Hashwerte, die binär mit 0 beginnen, kommen in Bucket 1.Hashwerte, die binär mit 10 beginnen, kommen in Bucket 2.Hashwerte, die binär mit 11 beginnen, kommen in Bucket 3.

16 (10000)

21 (10101)23 (10111)

25 (11001)

10..

01..

00..

11..

2

42

1

B1

165

2

211

233

B2

4 (00100)

255

2

B3

Hashwerte, die binär mit 0 beginnen, kommen in Bucket 1.Hashwerte, die binär mit 10 beginnen, kommen in Bucket 2.Hashwerte, die binär mit 11 beginnen, kommen in Bucket 3.

16 (10000)

21 (10101)23 (10111)

25 (11001)

10..

01..

00..

11..

2

42

1

82B1

165

2

211

233

B2

4 (00100)

255

2

B3

Einfügen des Wertes 82

16 (10000)

21 (10101)23 (10111)

25 (11001)

8 (01000)

Aufgabe 4

Wie viele Datensätze kann ein komplett gefüllter B+-Baum mit obigen Vorgaben aufnehmen? Beginnen Sie mit der Berechnung der maximalen Werte für n und n*.

B+-Baum = Daten liegen nur in den Blättern, Wurzel und innere Knoten sind ohne Daten

Wie viele Elemente passen in einen Knoten?

Innere Knoten (n):4000 Byte – 96 Byte Overhead = 3904 Byte2 Pointer = 24 Byte1 Schlüsselwert = 8 Byte

Seite mit einem Knoten: 96 + 24 + 8 = 128 Byte

Jeder weitere Knoten: 12 + 8 = 20 Byte2 Knoten: 148 Byte3 Knoten: 168 Byte…194 Knoten: 128 Byte + (193*20 Byte) = 128 Byte + 3860 Byte = 3988 Byte

n = 97

Äußere Knoten (n*):4000 Byte – 96 Byte Overhead = 3904 Byte2 Pointer = 24 Byte1 Schlüsselwert = 8 Byte1 Datenteil = 80 Byte

Seite mit einem Knoten: 96 + 24 + 8 + 80 = 208 Byte

Jeder weitere Knoten: 12 + 8 + 80 = 100 Byte2 Knoten: 308 Byte3 Knoten: 408 Byte…38 Knoten: 208 Byte + (37*100 Byte) = 208 Byte + 3700 Byte = 3908 Byte

n* = 19

Gegeben: h = 3

Wurzel

h = 1

h = 2

h = 3

Jeweils 194 Elemente pro Blatt

Jeweils 38 Elemente pro Blatt

Ebene 0 (Wurzel): 194 Elemente195 ausgehenden Kanten

Ebene 1: 195 * 194 = 37.830 Elemente195 * 195 = 38.025 ausgehende Kanten

Ebene 2: 38.025 * 194 = 7.376.850 Elemente38.025 * 195 = 7.414.875 ausgehende Kanten

Ebene 3: Blätter haben Datenteile, daher nur 38 Elemente pro Blatt! 7.414.875 * 38 = 281.765.250Daten liegen nur in den Blättern~ 282 Mio. Datenelemente im Baum

Wie viele Datensätze kann ein komplett gefüllter B-Baum mit obigen Vorgaben aufnehmen?

B-Baum: Daten in allen Knoten

Ebene 0 (Wurzel): 38 Elemente39 ausgehenden Kanten

Ebene 1: 39 * 38 = 1.482 Elemente39 * 39 = 1.521 ausgehende Kanten

Ebene 2: 1.521 * 38 = 57.798 Elemente1.521 * 39 = 59.319 ausgehende Kanten

Ebene 3: 59.319 * 38 = 2.257.122 ElementeDaten liegen in allen Elementen: 2.257.122 + 57.798 + 1.482 + 38~ 2,3 Mio. Datenelemente im Baum