Aufgabe 1. Herausforderungen I Persistente Datenspeicherung: Möchte man jeden Morgen alle Käufe und Verkäufe neu zusammensuchen? Sehr große Datenmengen:

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?


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?


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


4 (00100)

0…

1

1…

42

1

B1

165

1

B2


4 (00100)

16 (10000)

0…

1

1…

42

1

B1

165

1

211B2


4 (00100)

16 (10000)

21 (10101)

0…

1

1…

42

1

B1

165

1

211

233

B2


4 (00100)

16 (10000)

21 (10101)23 (10111)

0…

1

1…

42

1

B1

165

1

211

233

B2


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


16 (10000)

10..

01..

00..

11..

2

42

1

B1

165

2

211B2

4 (00100)

2

B3


16 (10000)

21 (10101)

10..

01..

00..

11..

2

42

1

B1

165

2

211

233

B2

4 (00100)

2

B3


16 (10000)

21 (10101)23 (10111)

10..

01..

00..

11..

2

42

1

B1

165

2

211

233

B2

4 (00100)

255

2

B3


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


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


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

Documents

Aufgabe 1. Herausforderungen I Persistente Datenspeicherung: Möchte man jeden Morgen alle Käufe und Verkäufe neu zusammensuchen? Sehr große Datenmengen: