Binäre Bäume
I.1.) Binäre Bäume Binäre Bäume sind geordnete Bäume bei denen jeder Knoten maximal 2 Kinder hat und die Ordnung der Knoten mit links und rechts festgelegt ist. Die Ordnung der...
463 Worte in "deutsch" als "hilfreich" bewertet
B-Bäume
1. Einführung: Der Begriff "Baum" Listen sind zwar relativ flexible Datenstrukturen, aber stets linear (eindimensional). Oft verwendet man auch zwei- oder dreidimensionale...
1353 Worte in "deutsch" als "hilfreich" bewertet
BCNF
1. Boyce/Codd Normalform (BCNF) 1.1 Definitionen Eine Relation ist dann, in der BCNF, wenn jede Determinante zugleich Schlüsselkandidat ist....
378 Worte in "deutsch" als "hilfreich" bewertet
B-Bäume
1 Einleitung
1 Einleitung
Auf Baumstrukturen trifft man im alltäglichen Leben häufig. Zum Beispiel forschen viele Leute nach ihren Vorfahren mit Hilfe eines Familienstammbaums. Ein weiteres Beispiel wäre bei der Organisation von Sporttunieren die Turnierpläne usw.
2 B-Baum (Bayer-Baum)
2.1 Allgemein
Durch die Größe der Datenbanken konnte man die nun auch größere Indexdatei nicht im Speicher behalten und musste so einzelne Knoten auf eine Seite zusammenfassen. Die Indexdatei wird somit zu einer Ansammlung von Seiten. Die erste Seite wird Quellseite genannt. Innere Seiten werden Knotenseiten genannt und die letzten Seiten bezeichnet man als Endseiten. Die Struktur wurde von R. Bayer - B-Baum genannt. Jede Seite enthält mehrere Schlüssel, von denen jeder auf einen Datensatz der Datendatei zeigt. Jede Knotenseite enthält überdies Zeiger auf weitere Seiten, die niedrigere und höhere Schlüssel besitzen. Endseiten enthalten keine Zeiger auf weitere Seiten.
2.2 Regeln
Um die Effizienz von B-Bäumen zu erhöhen, wurden einfache Regeln aufgestellt.
1. Eine Seite muss mindestens die Hälfte der maximal möglichen Elemente enthalten. Die höchste Anzahl an Elementen beträgt 2*n. Somit beträgt die Mindestanzahl n Elemente. Die Mindestanzahl n wird auch Ordnung des Baumes genannt. Die Quellseite darf allerdings zwischen 1 und 2*n Elementen enthalten.
2. Die zweite Regel verlangt, dass sich alle Endseiten auf der gleichen Ebene befinden, um eine ausgeglichene Baumstruktur zu erhalten und einen effizienten Suchweg zu ermöglichen.
2.3 Aufbauen eines B-Baumes:
Diese Elemente werden eingefügt: h a f g e b c d i (* bedeutet leer)
n=2 Þ max. Anzahl auf einer Seite = 4
1. Schritt: h einfügen
2. Schritt: a einfügen
3. Schritt f einfügen
4. Schritt g einfügen
5. Schritt e einfügen FEHLER !! max. Anzahl überschritten
Lösung: teilen
ß
6. Schritt b einfügen
7. Schritt c einfügen
8. Schritt d einfügen FEHLER !! max. Anzahl über-
schritten Lösung: teilen
ß
ß
9. Schritt i einfügen
2.4 Löschen eines Elements:
1. Art: Element aus einer Endseite
EF nach oben + DB nach unten
2. Art Element aus der Endseite, wenn die angrenzende und die zu löschende Seite zusammen weniger als 2*n Schlüssel haben
3. Art Element aus einer Knotenseite
Man sucht den direkten Vorgänger (39)
354 Worte in "deutsch" als "hilfreich" bewertet