Mehrwegbäume Flashcards
GDB Mehrwegbäume
Was sind die Ziele beim Entwurf eines Baumes und warum?
breit und geringe Höhe
Die Durchsuchung eine Seite die sich bereits im Hauptspeicher befindet ist deutlich schneller, als das holen einer referenzierten Seite (Externspeicherzugriffe).
breit und geringe Höhe => weniger Knoten die durchlaufen werden müssen => schnellerer Zugriff
“Leistungsgewinne werden dardurch erzeilt, dass die Ein-/Ausgabe beim Baumzugriff minimiert wird und zwar duch große Zugriffsgranulate und damit “breite” Bäume”
GDB Mehrwegbäume
Wie viele ursprüngliche Knoten sind als Einträge im neuen Knoten (Seite) untergebracht?
bis zu m-1
GDB Mehrwegbäume
Definition: m-Wege-Suchbaum
Die Di können Daten oder Zeiger auf die Daten repräsentieren
GDB Mehrwegbäume
Einfügen und Erkenntnis
GDB Mehrwegbäume
Welches sind die Balacierungsmechanismen für m-Wege-Suchbäume?
Es gibt keine
Es wurden mechanismen Entwickelt, jedoch hätten diese bei dem stricktesten Kriterium einen Wartungsaufwand von O(n) und wären damit zu teuer.
Deshalb Entwicklung von B-Bäumen, welche fast ausgegelichene Mehrwegbäume sind
GDB Mehrwegbäume
Definition des Knotenformats
GDB Mehrwegbäume
Was sind B-Bäume?
- B-Bäume sind fast ausgeglichene Mehrwegbäume
- In Bezug auf Knotenstruktur (Seiten) vollständig ausgeglichen
- nicht immer minimale, aber geringe Höhe
- Zugriffsverhalten weitgehend unabhängig von Menge der verwalteten Elemente
GDB Mehrwegbäume
Definition: B-Baum
Seinen k, h, ganze Zahlen, h ≥ 0, k >0. Ein B-Baum B der Klasse τ(k,h) ist eintwerde ein leerer Baum oder ein geordneter Suchbaum mit folgenden Eigenschaften:
- Jeder Pfad von der Wurzel zu einem Blatt hat die gleiche Länge.
- Jeder Knoten außer der Wurzel und den Blaättern hat mindestens k+1 Söhne. die Wurzel ist ein Blatt oder hat mindestes 2 Söhne.
GDB Mehrwegbäume
Höhe des B-Baums
GDB Mehrwegbäume
Einfügen in B-Bäumen
GDB Mehrwegbäume
Kostenanalyse für Einfügen und Suchen in B-Bäumen
Mit Gleichung (2) erhalten wir als gesamte Zugriffskosten bei maximaler Belegung eines Baumes, wenn auf jeden Schlüssel genau einaml zugegriffen wird,
GDB Mehrwegbäume
Löschen in B-Bäumen
Ziel: verhindern, dass Anzahl der Elemente in Knoten kleiner als k
durch Ausgeleich oder Mischen(Konkatenation)
GDB Mehrwegbäume
Löschen in B-Bäumen durch Ausgeleich
…gende Löschungen im gleichen Knoten würden nicht sofort wieder einen Ausgleichsvorgang nach sich ziehen.
GDB Mehrwegbäume
Löschen in B-Bäumen durch Mischen
GDB Mehrwegbäume
Löschalgorithmus
GDB Mehrwegbäume
Lösche 21
Lösche 11
Mische
GDB Mehrwegbäume
Kostenanalyse für das Löschen in B-Bäumen
GDB Mehrwegbäume
Optimierungsmaßnahmen in B-Bäumen: Verallgemeinerte Überlaufbehandlung
Im Originalvorschlag des B-Baum-Konzeptes verlangt Einefügen von Schlüsseln Split-Vorgang. Dieser wird von einer vollen Seite ausgelöst (m=1). Danach Speicherplatzbelegung beiden Seiten β = m/(m+1) = 1/2. => Es kann sein, dass in genzem Baum (außer) nur 50% belegt
GDB Mehrwegbäume
Einfügen mit doppeltem Überlauf:
8
10
6
GDB Mehrwegbäume
Optimierungsmaßnahmen in B-Bäumen: Suche in der Seite eines Mehrwegbaumes
Systematische Suche
- Seite eintragsweise sequentiell durchlaufen
- bei 2k Einträgen durchsnittlich k mal vergleichen
Sprungsuche
- geordnete Folge von 2k Einträgen wird in j gleichgroße Intervalle eingeteilt
- Die höchsten Einträge im Intervall werden geprüft
- Dann Intervall wieder unterteilen…
- durchschnittlich j/2+k/j Vergleiche
- j = √2 Optimum (Quadratwurzelsuche)
Binäre Suche
- geordnete Folge
- Bereiche immer halbieren
- ideale Halbierung bei 2k = 2j -1 (j > 1)
- durchschnittlich angenähert log2(2k)-1
GDB Mehrwegbäume
Optimierungsmaßnahmen in B-Bäumen: Einsatz von variabel langen Schlüsseln
GDB Mehrwegbäume
B*-Bäume und Definition
GDB Mehrwegbäume
Höhe des B*-Baumes
GDB Mehrwegbäume
Wie kann der B*-Baum aufgefasst werden?
GDB Mehrwegbäume
Grundoperationen beim B*-Baum
GDB Mehrwegbäume
Vergleich von B- und B*-Baum
