wake-up-neo.com

B-Tree schneller als AVL oder RedBlack-Tree?

Ich weiß, dass Leistung niemals schwarz und weiß ist. Oft ist eine Implementierung schneller für X und langsamer für Y usw., aber im Allgemeinen - sind B-Bäume schneller als AVL oder RedBlack-Trees? Sie sind erheblich komplexer zu implementieren als AVL-Bäume (und vielleicht sogar RedBlack-Bäume?), Aber sind sie schneller (lohnt sich ihre Komplexität)?

Edit: Ich möchte auch hinzufügen, dass, wenn sie schneller sind als der entsprechende AVL/RedBlack-Baum (in Bezug auf Knoten/Inhalt) - warum sind sie schneller?

63
thr

Seans Post (der derzeit akzeptierte) enthält mehrere falsche Behauptungen. Tut mir leid, Sean, ich will nicht unhöflich sein; Ich hoffe, ich kann Sie davon überzeugen, dass meine Aussage tatsächlich basiert.

Sie sind in ihren Anwendungsfällen völlig unterschiedlich, daher ist es nicht möglich, einen Vergleich anzustellen.

Beide werden für die Verwaltung eines Satzes von vollständig geordneten Artikeln mit schnellem Nachschlagen, Einfügen und Löschen verwendet. Sie haben dieselbe Schnittstelle und dieselbe Absicht.

RB-Bäume sind typischerweise In-Memory-Strukturen, die einen schnellen Zugriff (idealerweise O(logN)) auf Daten ermöglichen. [...]

immer O (log n)

B-Trees sind normalerweise plattenbasierte Strukturen und daher inhärent langsamer als In-Memory-Daten.

Unsinn. Wenn Sie Suchbäume auf der Festplatte speichern, verwenden Sie normalerweise B-Bäume. So viel stimmt. Wenn Sie Daten auf der Festplatte speichern, ist der Zugriff langsamer als auf Daten im Speicher. Ein auf der Festplatte gespeicherter rot-schwarzer Baum ist jedoch auch langsamer als ein rot-schwarzer Baum, der im Speicher gespeichert ist.

Sie vergleichen hier Äpfel und Orangen. Was wirklich interessant ist, ist ein Vergleich von In-Memory-B-Bäumen und In-Memory-Rot-Schwarz-Bäumen.

[Nebenbei bemerkt: B-Bäume sind im Gegensatz zu rot-schwarzen Bäumen im I/O-Modell theoretisch effizient. Ich habe das E/A-Modell zum Sortieren experimentell getestet (und validiert); Ich würde erwarten, dass es auch für B-Bäume funktioniert.]

B-Bäume sind selten binäre Bäume, die Anzahl der Kinder, die ein Knoten haben kann, ist normalerweise groß.

Der Größenbereich der B-Tree-Knoten ist ein Parameter der Baumstruktur (in C++ möchten Sie möglicherweise einen ganzzahligen Wert als Vorlagenparameter verwenden).

Die Verwaltung der B-Baumstruktur kann ziemlich kompliziert sein, wenn sich die Daten ändern.

Ich erinnere mich, dass sie viel einfacher zu verstehen (und zu implementieren) sind als rot-schwarze Bäume.

B-Tree versucht, die Anzahl der Festplattenzugriffe zu minimieren, so dass der Datenabruf einigermaßen deterministisch ist.

So viel stimmt.

Es ist nicht ungewöhnlich, dass so etwas wie der 4-B-Tree-Zugriff erforderlich ist, um ein wenig Daten in einer Datenbank nachzuschlagen.

Daten erhalten?

In den meisten Fällen würde ich sagen, dass In-Memory-RB-Bäume schneller sind.

Daten erhalten?

Da die Suche binär ist, ist es sehr leicht, etwas zu finden. Der B-Baum kann mehrere untergeordnete Elemente pro Knoten haben. Daher müssen Sie auf jedem Knoten den Knoten scannen, um nach dem entsprechenden untergeordneten Element zu suchen. Dies ist eine O(N) - Operation.

Die Größe jedes Knotens ist ein fester Parameter. Wenn Sie also einen linearen Scan durchführen, ist dies O (1). Wenn die Größe jedes Knotens groß ist, beachten Sie, dass Sie das Array normalerweise sortiert halten, sodass es O (log n) ist.

In einem RB-Baum wäre dies O(logN), da Sie einen Vergleich durchführen und dann verzweigen.

Sie vergleichen Äpfel und Orangen. Das O (log n) ist, weil die Höhe des Baums höchstens O (log n) ist, genau wie bei einem B-Baum.

Wenn Sie nicht böse Zuordnungs-Tricks mit den rot-schwarzen Bäumen spielen, ist es vernünftig, zu vermuten, dass B-Bäume ein besseres Caching-Verhalten aufweisen (es greift auf ein Array zu und nicht auf Zeiger, die überall verteilt sind, und hat weniger Speicher für die Zuweisung noch mehr), was im Speed-Rennen helfen könnte.

Ich kann auf experimentelle Beweise verweisen, dass B-Bäume (speziell mit den Größenparametern 32 und 64) mit rot-schwarzen Bäumen für kleine Größen sehr konkurrenzfähig sind, und übertrifft sie sogar bei mäßig großen Werten von n. Siehe http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html

B-Bäume sind schneller. Warum? Ich vermute, dass dies auf Speicherlokalisierung, besseres Caching-Verhalten und weniger Verfolgung von Zeigern zurückzuführen ist (die sich, wenn nicht die gleichen Dinge, in gewissem Maße überlappen).

111
Jonas Kölker

Tatsächlich hat Wikipedia einen großartigen Artikel, der zeigt, dass jeder RB-Baum leicht als B-Baum ausgedrückt werden kann. Nehmen Sie den folgenden Baum als Beispiel:

RB-Tree

jetzt konvertieren Sie es einfach in einen B-Baum (um dies deutlicher zu machen, sind die Knoten immer noch R/B-farbig, was Sie normalerweise in einem B-Baum nicht haben):

Gleicher Baum wie B-Baum

(Das Bild kann hier aus irgendeinem Grund nicht hinzugefügt werden.)

Gleiches gilt für jeden anderen RB-Baum. Es ist aus diesem Artikel entnommen:

http://en.wikipedia.org/wiki/Red-black_tree

Um aus diesem Artikel zu zitieren:

Der rot-schwarze Baum entspricht dann strukturell einem B-Baum der Ordnung 4 mit einem minimalen Füllfaktor von 33% der Werte pro Cluster mit einer maximalen Kapazität von 3 Werten.

Ich fand keine Daten, dass einer von beiden signifikant besser ist als der andere. Ich denke, einer von beiden war bereits ausgestorben, wenn das der Fall war. Sie unterscheiden sich darin, wie viele Daten sie im Speicher speichern müssen und wie kompliziert das Hinzufügen/Entfernen von Knoten zum Baum ist.

Aktualisieren:

Meine persönlichen Tests legen nahe, dass B-Trees bei der Suche nach Daten besser sind, da sie eine bessere Datenlokalität aufweisen und der CPU-Cache daher einen etwas schnelleren Vergleich durchführen kann. Je höher die Reihenfolge eines B-Baums (die Reihenfolge ist die Anzahl der Kinder, die eine Notiz haben kann), desto schneller wird die Suche. Andererseits haben sie eine schlechtere Leistung beim Hinzufügen und Entfernen neuer Einträge, je höher ihre Reihenfolge ist. Dies wird dadurch verursacht, dass das Hinzufügen eines Werts innerhalb eines Knotens eine lineare Komplexität aufweist. Da jeder Knoten ein sortiertes Array ist, müssen Sie viele Elemente innerhalb dieses Arrays verschieben, wenn Sie ein Element in die Mitte einfügen: Alle Elemente links vom neuen Element müssen um eine Position nach links oder alle Elemente rechts davon verschoben werden Das neue Element muss um eine Position nach rechts verschoben werden. Wenn ein Wert während eines Einfügens um einen Knoten nach oben verschoben wird (was in einem B-Tree häufig vorkommt), verbleibt ein Loch, das ebenfalls gefüllt werden muss, indem entweder alle Elemente von der linken Position nach rechts verschoben werden oder indem alle Elemente nach verschoben werden die rechte Position nach links. Diese Operationen (in C normalerweise von memmove ausgeführt) sind in der Tat O (n). Je höher die Ordnung des B-Baums ist, desto schneller ist die Suche, desto langsamer ist jedoch die Änderung. Wenn Sie dagegen die Reihenfolge zu niedrig wählen (z. B. 3), zeigt ein B-Tree in der Praxis nur geringe Vor- oder Nachteile gegenüber anderen Baumstrukturen (in diesem Fall können Sie auch etwas anderes verwenden). Daher würde ich immer B-Bäume mit hohen Aufträgen erstellen (mindestens 4, 8 und höher sind in Ordnung).

Dateisysteme, die häufig auf B-Bäumen basieren, verwenden viel höhere Ordnungen (Ordnung 200 und sogar viel mehr) - dies liegt daran, dass sie die Ordnung normalerweise so hoch wählen, dass eine Note (wenn sie die maximale Anzahl zulässiger Elemente enthält) entweder gleich ist die Größe eines Sektors auf der Festplatte oder eines Clusters des Dateisystems. Dies bietet eine optimale Leistung (da eine Festplatte immer nur einen vollständigen Sektor auf einmal schreiben kann, auch wenn nur ein Byte geändert wird, wird der vollständige Sektor trotzdem neu geschrieben) und eine optimale Speicherplatznutzung (da jeder Dateneintrag auf dem Laufwerk mindestens der Größe von entspricht) ein Cluster oder ist ein Vielfaches der Clustergröße, unabhängig davon, wie groß die Daten tatsächlich sind. Aufgrund der Tatsache, dass die Hardware Daten als Sektoren ansieht und das Dateisystem Sektoren zu Clustern gruppiert, können B-Trees eine viel bessere Leistung und Speicherplatznutzung für Dateisysteme erzielen als jede andere Baumstruktur. Deshalb sind sie für Dateisysteme so beliebt.

Wenn Ihre App den Baum ständig aktualisiert und Werte hinzufügt oder daraus entfernt, zeigt ein RB-Baum oder ein AVL-Baum im Durchschnitt eine bessere Leistung als ein B-Baum mit hoher Ordnung. Etwas schlimmer für die Lookups und sie benötigen möglicherweise auch mehr Speicher, aber dafür sind Änderungen normalerweise schnell. Tatsächlich sind RB-Bäume für Änderungen sogar noch schneller als AVL-Bäume, daher sind AVL-Bäume für Suchvorgänge etwas schneller, da sie normalerweise weniger tief sind.

Wie immer kommt es also sehr darauf an, was Ihre App macht. Meine Empfehlungen sind:

  1. Viele Lookups, kleine Modifikationen: B-Tree (mit hoher Ordnung)
  2. Viele Lookups, viele Modifikationen: AVL-Tree
  3. Kleine Lookups, viele Modifikationen: RB-Tree

Eine Alternative zu all diesen Bäumen sind AA-Bäume . Wie dieses PDF-Papier schlägt vor , sind AA-Bäume (die tatsächlich eine Untergruppe von RB-Bäumen sind) in der Leistung fast gleich wie normale RB-Bäume, aber sie sind viel einfacher zu implementieren als RB -Bäume, AVL-Bäume oder B-Bäume. Hier ist eine vollständige Implementierung , schauen Sie , wie klein es ist (die Hauptfunktion ist nicht Teil der Implementierung und die Hälfte davon Die Implementierungszeilen sind eigentlich Kommentare.

Wie das Papier PDF zeigt, ist a Treap auch eine interessante Alternative zur klassischen Baumimplementierung. Ein Treap ist auch ein binärer Baum, der jedoch nicht versucht, das Balancing zu erzwingen. Um Worst-Case-Szenarien zu vermeiden, die in unausgeglichenen Binärbäumen auftreten können (die Lookups werden zu O(n) anstelle von O (log n)), fügt ein Treap dem Baum eine gewisse Zufälligkeit hinzu. Der Zufall kann nicht garantieren, dass der Baum gut ausbalanciert ist, aber es ist auch höchst unwahrscheinlich, dass der Baum extrem aus dem Gleichgewicht gerät.

91
Mecki

Nichts hindert eine B-Tree-Implementierung, die nur im Speicher funktioniert. Wenn Schlüsselvergleiche billig sind, kann der B-Tree im Speicher schneller sein, da durch das Packen mehrerer Schlüssel in einem Knoten less Cache-Fehler während der Suche verursacht werden. Siehe this link für Leistungsvergleiche. Ein Zitat: "Die Ergebnisse des Geschwindigkeitstests sind interessant und zeigen, dass der B + -Baum bei Bäumen mit mehr als 16.000 Objekten deutlich schneller ist." (B + Tree ist nur eine Variation von B-Tree).

27
zvrba

Die Frage ist alt, aber ich denke, dass sie immer noch relevant ist. Jonas Kölker und Mecki haben sehr gute Antworten gegeben, aber ich denke nicht, dass die Antworten die ganze Geschichte abdecken. Ich würde sogar argumentieren, dass der ganzen Diskussion der Punkt fehlt :-). 

Was über B-Trees gesagt wurde, ist wahr, wenn die Einträge relativ klein sind (ganze Zahlen, kleine Strings/Wörter, Floats usw.). Wenn die Einträge groß sind (über 100 B), werden die Unterschiede kleiner/unbedeutender.

Lassen Sie mich die wichtigsten Punkte zu B-Trees zusammenfassen:

  • Sie sind schneller als alle Binary Search Tree (BSTs) aufgrund der Speicherlokalität (was zu weniger Cache- und TLB-Fehlern führt).

  • B-Trees sind normalerweise platzsparender, wenn die Einträge relativ klein sind oder die Einträge variabel sind. Die Verwaltung des freien Speicherplatzes ist Einfacher (Sie weisen größere Speicherbereiche zu) und der zusätzliche Metadatenwert Pro Eintrag ist geringer. B-Trees verschwenden etwas Platz, da die Knoten Nicht immer voll sind, sie werden jedoch immer noch kompakter Die binären Suchbäume.

  • Die große O-Leistung (O(logN)) ist für beide gleich. Wenn Sie die binäre Suche in jedem B-Tree-Knoten durchführen, erhalten Sie sogar die gleiche Anzahl von Vergleichen wie in einer BST (dies ist eine nette mathematische Übung, um dies zu überprüfen). Wenn die B-Tree-Knotengröße sinnvoll ist (1-4x Cachezeilengröße), ist die lineare Suche in jedem Knoten aufgrund des Hardware-Prefetching noch schneller. Sie können auch SIMD-Anweisungen zum Vergleich von Basisdatentypen (z. B. Ganzzahlen) verwenden. 

  • B-Trees eignen sich besser für die Komprimierung: Es gibt mehr Daten pro Knoten zum Komprimieren. In bestimmten Fällen kann dies ein großer Vorteil sein. Denken Sie nur an einen automatisch inkrementierenden Schlüssel in einer relationalen Datenbanktabelle, der zum Erstellen eines Index verwendet wird. Die Hauptknoten eines B-Baums enthalten aufeinanderfolgende Ganzzahlen, die sehr, sehr gut komprimiert werden.

  • B-Trees sind deutlich viel schneller, wenn sie im sekundären Speicher gespeichert werden (wo IO-Blockierungen erforderlich sind).

Auf dem Papier haben B-Trees viele Vorteile und fast keine Nachteile. Sollte man also B-Trees verwenden, um die beste Leistung zu erzielen?

Die Antwort lautet normalerweise NEIN - wenn der Baum in den Speicher passt. In Fällen, in denen Leistung von entscheidender Bedeutung ist, möchten Sie eine thread-sichere, baumartige Datenstruktur (einfach ausgedrückt, mehrere Threads können mehr Arbeit als ein einzelner ausführen). Es ist problematischer, eine B-Tree-Unterstützung für gleichzeitige Zugriffe zu erstellen, als eine BST. Der einfachste Weg, um zuzulassen, dass ein Baum gleichzeitige Zugriffe unterstützt, ist das Sperren von Knoten, während Sie diese durchlaufen oder ändern. In einem B-Tree sperren Sie mehr Einträge pro Knoten, was zu mehr Serialisierungspunkten und mehr umstrittenen Sperren führt.

Alle Tree-Versionen (AVL, Red/Black, B-Tree und andere) haben unzählige Varianten, die sich in der Unterstützung von Parallelität unterscheiden. Die Vanilla-Algorithmen, die in einem Universitätskurs unterrichtet werden oder aus einleitenden Büchern gelesen werden, werden in der Praxis fast nie eingesetzt. Es ist daher schwer zu sagen, welcher Baum die beste Leistung bringt, da es keine offizielle Vereinbarung darüber gibt, welche Algorithmen hinter jedem Baum stehen. Ich würde anregen, die genannten Bäume eher als Datenstrukturklassen zu betrachten, die bestimmten baumartigen Invarianten statt präzisen Datenstrukturen gehorchen.

Nehmen Sie zum Beispiel den B-Baum. Der Vanille-B-Baum wird in der Praxis fast nie verwendet - man kann es nicht schaffen, gut zu skalieren! Die am häufigsten verwendete B-Tree-Variante ist der B + -Tree (weit verbreitet in Dateisystemen und Datenbanken). Die Hauptunterschiede zwischen dem B + -Baum und dem B-Baum: 1) Sie speichern keine Einträge in den inneren Knoten des Baums (daher benötigen Sie keine Schreibsperren im Baum, wenn Sie einen Eintrag ändern, der in einem inneren Knoten gespeichert ist.) ; 2) Sie haben Verknüpfungen zwischen Knoten auf derselben Ebene (Sie müssen also nicht den übergeordneten Knoten eines Knotens sperren, wenn Sie eine Bereichssuche durchführen).

Ich hoffe das hilft.

10
Radu

Jungs von Google haben kürzlich die Implementierung von STL-Containern veröffentlicht, die auf B-Bäumen basieren. Sie behaupten, ihre Version sei schneller und verbraucht weniger Speicherplatz als Standard-STL-Container, die über rot-schwarze Bäume implementiert werden .. _ Weitere Informationen hier

8

Für einige Anwendungen sind B-Bäume deutlich schneller als BSTs . Die Bäume finden Sie hier:

http://freshmeat.net/projects/bps

sind ziemlich schnell Sie benötigen auch weniger Speicher als reguläre BST-Implementierungen, da sie keine BST-Infrastruktur mit zwei oder drei Zeigern pro Knoten sowie einige zusätzliche Felder zum Speichern der Abgleichinformationen benötigen.

2

Sie haben alle das gleiche asymptotische Verhalten, daher hängt die Leistung mehr von der Implementierung ab als von der Art des Baums, den Sie verwenden. Eine Kombination von Baumstrukturen ist möglicherweise der schnellste Ansatz, bei dem jeder Knoten eines B-Baums genau passt in eine Cache-Zeile und eine Art binärer Baum wird für die Suche in jedem Knoten verwendet. Durch die Verwaltung des Arbeitsspeichers für die Knoten können Sie möglicherweise auch eine noch größere Cache-Lokalität erzielen, jedoch zu einem sehr hohen Preis.

Ich persönlich benutze nur das, was sich in der Standardbibliothek befindet, für die Sprache, die ich verwende, da dies eine Menge Arbeit für einen sehr geringen Leistungsgewinn (wenn überhaupt) bedeutet.

Theoretisch ... RB-Bäume sind B-Bäumen eigentlich sehr ähnlich, da sie das Verhalten von 2-3-4 Bäumen simulieren. AA-Bäume haben eine ähnliche Struktur, die stattdessen 2-3 Bäume simuliert.

0
Jørgen Fogh

außerdem ... die Höhe eines roten schwarzen Baums ist O (log [2] N), während die Höhe des B-Baums O (log [q] N) ist, wobei die Decke [N] <= q <= N ist. Wenn wir also Vergleiche in jedem Schlüsselfeld des B-Baums betrachten (das ist wie oben erwähnt festgelegt), dann ist die Zeitkomplexität des B-Baums <= Zeitkomplexität des Rot-Schwarz-Baums. (Gleicher Fall für einen einzelnen Datensatz mit der Größe einer Blockgröße)

0
mohit

Sie werden unter verschiedenen Umständen eingestellt. B-Bäume werden verwendet, wenn die Baumknoten im Speicher zusammengehalten werden müssen. Dies ist in der Regel der Fall, da es sich bei dem Speicher um eine Festplattenseite handelt und der Neuausgleich daher sehr teuer sein kann. RB-Bäume werden verwendet, wenn Sie diese Einschränkung nicht haben. B-Trees werden also wahrscheinlich schneller sein, wenn Sie einen relationalen Datenbankindex implementieren möchten, während RB-Trees für eine In-Memory-Suche wahrscheinlich am schnellsten sind.

0
anon