Ü8 B-Bäume, B*-Bäume, Normalisierung Flashcards
1
Q
GDB Ü8 B-Bäume, B*-Bäume, Normalisierung
B-Bäume: Definition
A
Definition: Seien k, h ganze Zahlen, h > 0, k > 0. Ein B-Baum B der Klasse τ(k,h) ist entweder ein leerer Baum oder ein geordneter Suchbaum mit folgenden Eigenschaften:
- Jeder Pfad von der Wurzel zu einem Blatt hat die gleiche Länge h-1.
- Jeder Knoten außer der Wurzel und den Blättern hat mindestens k+1 Söhne.
- Die Wurzel ist ein Blatt oder hat mindestens 2 Söhne.
- Jeder Knoten hat höchstens 2k+1 Söhne.
- Jeder Knoten mit Ausnahme der Wurzel hat mindestens k und höchstens 2k Einträge.
- In jedem Knoten stehen die Schlüssel in aufsteigender Ordnung mit K1<k>2<...<k>b.</k></k>
- Jeder Schlüssel hat eine Doppelrolle als Identifikator eines Datensatzes und als Wegweiser im Baum.
2
Q
A
3
Q
A
4
Q
A
5
Q
A
6
Q
A
7
Q
GDB Ü8 B-Bäume, B*-Bäume, Normalisierung
B*-Bäume: Definition
A
Seien k, k* und h* ganze Zahlen, h* ≥ 0, k, k* > 0. Ein B*-Baum B der Klasse τ(k,k*,h*) ist entweder ein leerer Baum oder ein geordneter Suchbaum, für den gilt:
- Jeder Pfad von der Wurzel zu einem Blatt besitzt die gleiche Länge h*-1.
- Jeder Knoten außer der Wurzel und den Blättern hat mindestens k+1 Söhne, die Wurzel mindestens 2 Söhne, außer wenn sie ein Blatt ist.
- Jeder innere Knoten hat höchstens 2k+1 Söhne.
- Jeder Blattknoten mit Ausnahme der Wurzel als Blatt hat mindestens k* und höchstens 2k* Einträge.
8
Q
A
9
Q
A
10
Q
A
11
Q
A
12
Q
A
13
Q
GDB Ü8 B-Bäume, B*-Bäume, Normalisierung
Normalisierung: Änderungsanomalien
A
Einfüge-Anomalie:
- Es ist nicht möglich ein neues Buch einzufügen, wenn dieses nicht von einem Kunden ausgeliehen wird.
- ODER Es ist nicht möglich, einen Kunden anzulegen ohne dass dieser ein Buch ausleiht.
Lösch-Anomalie:
- Wenn der Kunde das letzte Buch zurückgibt, gehen auch die Kundeninformationen verloren.
- ODER Mit dem Löschen eines Kunden gehen auch die Informationen über ein Buch verloren, wenn dies von keinem anderen Kunden ausgeliehen ist.
Modifikations-Anomalie:
- Um den Titel eines Buches zu korrigieren, müssen die Tupel für alle Leihverhältnisse desselben Buches aktualisiert werden.
- ODER: Ändert sich der Name eines Kunden, müssen die Tupel für alle Ausleihverhältnisse des Kunden aktualisiert werden.
14
Q
GDB Ü8 B-Bäume, B*-Bäume, Normalisierung
Normalisierung: Normalform
A
15
Q
A
16
Q
A
17
Q
A
18
Q
A
19
Q
A
20
Q
A
22
Q
A
23
Q
A
24
Q
A
25
Q
A
