Was sind die Vorteile von T-Bäumen gegenüber B+/--Bäumen?

Question

Ich habe mich mit den Definitionen von T-Bäume und B-/B+ Bäume. Aus Veröffentlichungen im Internet habe ich entnommen, dass B-Bäume in hierarchischen Speichern wie Festplattenlaufwerken und Cache-Speicher besser funktionieren.

Was ich nicht verstehen kann, ist, warum T-Bäume auch für flache Speicher verwendet wurden/werden?

Sie werden als platzsparende Alternative zu RBL-Bäumen angepriesen.

Im ungünstigsten Fall enthalten alle Blattknoten eines T-Baums nur ein Element, und alle internen Knoten enthalten die zulässige Mindestmenge, die nahezu voll ist. Dies bedeutet, dass im Durchschnitt nur die Hälfte des zugewiesenen Platzes genutzt wird. Wenn ich mich nicht irre, ist dies die gleiche Auslastung wie im schlimmsten Fall von B-Bäumen, wenn die Knoten eines B-Baums zur Hälfte gefüllt sind.

Unter der Annahme, dass beide Bäume die Schlüssel lokal in den Knoten speichern, aber Zeiger verwenden, um auf die Datensätze zu verweisen, besteht der einzige Unterschied darin, dass B-Bäume Zeiger für jeden der Zweige speichern müssen. Dies würde im Allgemeinen einen Overhead von bis zu 50 % oder weniger verursachen (im Vergleich zu T-Bäumen), je nach Größe der Schlüssel. Dies entspricht in etwa dem Aufwand, der bei AVL-Bäumen zu erwarten ist, wenn man davon ausgeht, dass es keine übergeordneten Zeiger gibt, die Datensätze in den Knoten eingebettet sind und die Schlüssel in den Datensätzen eingebettet sind. Ist dies der erwartete Effizienzgewinn, der uns davon abhält, stattdessen B-Bäume zu verwenden?

T-Bäume werden normalerweise auf AVL-Bäumen implementiert. AVL-Bäume sind ausgeglichener als B-Bäume. Kann dies mit der Anwendung von T-Bäumen in Verbindung gebracht werden?

Answer 1

Ich kann Ihnen eine persönliche Geschichte erzählen, die die Hälfte der Antwort abdeckt, nämlich warum ich einen Pascal-Code geschrieben habe, um zu programmieren B+ Bäume vor etwa 18 Jahren.

Mein Zielsystem war ein PC mit zwei Festplatten, ich musste einen Index in einem nicht flüchtigen Speicher ablegen und ich wollte besser verstehen, was ich an der Universität gelernt hatte. Ich war sehr unzufrieden mit der Leistung eines kommerziellen Pakets, wahrscheinlich DBase III oder irgendein Fox-Produkt, ich kann mich nicht mehr erinnern.

wie auch immer: Ich brauchte diese Operationen:

• Nachschlagen

• Einfügung

• Löschung

• nächster Punkt

• vorherige Position

• die maximale Größe des Index war nicht bekannt

• daher mussten die Daten auf der Festplatte gespeichert werden

• jeder Zugang zur Unterstützung war mit hohen Kosten verbunden

• das Lesen eines ganzen Blocks kostet dasselbe wie das Lesen eines Bytes

B+-Bäume ließen den kleinen, langsamen PC regelrecht durch die Daten fliegen!

die Blätter hatten zwei zusätzliche Zeiger, so dass sie eine doppelt verknüpfte Liste für die sequentielle Suche bildeten.

Answer 2

In Wirklichkeit liegt der Unterschied in dem von Ihnen verwendeten System. Wie mein Tutor an der Universität sagte: Ob Ihr Problem in Speicherknappheit oder in Festplattenknappheit liegt, wird bestimmen, welchen Baum und welche Implementierung Sie verwenden werden. Höchstwahrscheinlich wird es der B+ Baum sein.

Da es Hunderte von Implementierungen gibt, z. B. mit 2-Richtungs-Warteschlangen und Ein-Richtungs-Warteschlangen, bei denen Sie gedachte Elemente in einer Schleife speichern müssen, und es auch mehrere Möglichkeiten gibt, den Index zu speichern und abzurufen, werden die wirklichen Nachteile und Vorteile jeder Implementierung bestimmt.