B-Baum schneller als AVL oder RedBlack-Tree? [geschlossen]

https://stackoverflow.com/questions/647537

22-07-2019
|

Frage

Ich weiß, dass die Leistung nie schwarz und weiß, oft eine Implementierung ist schneller, falls X und langsamer, falls Y usw., aber im Allgemeinen - sind B-Bäume schneller als AVL oder RedBlack-Bäume? Sie sind wesentlich komplexer zu implementieren dann AVL-Bäume (und vielleicht sogar RedBlack-Bäume?), Aber sie sind schneller (nicht ihre Komplexität tilgen)?

Edit: Ich möchte auch hinzufügen, dass, wenn sie schneller als das Äquivalent AVL / RedBlack Baum (in Form von Knoten / content) sind - Warum sind sie schneller ?

Lösung

Seans Post (die derzeit akzeptierte ein) mehrere falsche Ansprüche. Leider Sean, meine ich nicht unhöflich sein; Ich hoffe, ich kann Sie davon überzeugen, dass meine Aussage in der Tat basiert.

Sie sind völlig verschieden in ihren Anwendungsfällen, so kann es nicht um einen Vergleich zu machen.

sind Sie beide verwendet für eine Reihe von völlig bestellten Artikel mit schnellen Nachschlagen, Einfügen und Löschen beibehalten wird. Sie haben die gleiche Schnittstelle und die gleiche Absicht.

RB Bäume sind in der Regel in-Speicherstrukturen verwendet einen schnellen Zugriff zur Verfügung zu stellen (im Idealfall O (log N)) auf die Daten. [...]

immer O (log n)

B-Bäume sind in der Regel Disk-basierten Strukturen, und so sind von Natur aus langsamer als im Speicher befindlichen Daten.

Unsinn. Wenn Sie Suchbäume auf der Festplatte zu speichern, verwenden Sie in der Regel B-Bäume. So viel ist wahr. Wenn Sie Daten auf der Festplatte speichern, dann ist es langsamer als in Speicherdaten zugreifen. Aber ein Rot-Schwarz-Baum auf der Festplatte gespeichert ist auch langsamer als ein Rot-Schwarz-Baum im Speicher gespeichert.

Du vergleichst Äpfel und Orangen hier. Was ist wirklich interessant ist ein Vergleich der In-Memory-B-Bäume und In-Memory-rot-schwarze Bäume.

[Als Nebenwirkung: B-Bäume, im Gegensatz zu Rot-Schwarz-Bäumen, sind theoretisch effizient in dem I / O-Modell. Ich habe experimentell getestet (und validiert), um das I / O-Modell zum Sortieren; Ich würde erwarten, dass es auch für B-Bäume zu arbeiten.]

B-Bäume sind selten Binärbäumen, die Zahl der Kinder ein Knoten haben kann, ist typischerweise eine große Zahl.

klar sein, der Größenbereich von B-Tree-Knoten ist ein Parameter des Baumes (in C ++ hat, können Sie einen Integer-Wert als Template-Parameter verwenden).

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

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

B-Baum versucht die Anzahl der Plattenzugriffe zu minimieren, so dass Datenabruf vernünftig deterministisch ist.

So viel ist wahr.

Es ist nicht ungewöhnlich, so etwas wie 4 B-Baum-Zugang zu sehen, notwendig, ein Bit an Daten in einer sehr Datenbank nachzuschlagen.

Haben Sie Daten?

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

Haben Sie Daten?

Da die Lookup-binär ist es sehr einfach, etwas zu finden. B-Baum kann mehrere Kinder pro Knoten, also auf jedem Knoten Sie den Knoten scannen für das entsprechende Kind zu suchen. Dies ist ein O (N) Betrieb.

Die Größe der einzelnen Knoten ist ein fester Parameter, so dass selbst wenn Sie einen linearen Scan tun, ist es O (1). Wenn wir groß-oh über die Größe der einzelnen Knoten, beachten Sie, dass Sie in der Regel das Array halten sortiert, so dass es O (log n) ist.

Auf einem RB-Baum würde es O (log N), da Sie einen Vergleich tust und dann verzweigen.

Du vergleichst Äpfel und Orangen. Der O (log n) ist, weil die Höhe des Baumes höchstens O (log n) ist, so wie es ist für einen B-Baum.

Auch wenn Sie böse Zuordnung Tricks mit den rot-schwarzen Bäumen spielen, scheint es vernünftig, dass B-Bäume besser Caching-Verhalten haben zu vermuten (es ein Array zugreift, keine Zeiger über der ganzen Ort verstreut und weniger Zuteilung hat Kopf Speicherlokalizität noch mehr) zu, was ihm in den Speed-Rennen helfen könnte.

kann ich auf experimentelle Beweise zeigen, dass B-Bäume (mit Größenparameter 32 und 64, insbesondere) mit für kleine Größen rot-schwarz Bäume sehr wettbewerbsfähig sind, und übertrifft es selbst für mäßig große Werte von n die Hände nach unten. Siehe http://idlebox.net/ 2007 / STX-btree / STX-btree-0.8.3 / doxygen-html / speedtest.html

B-Bäume sind schneller. Warum? ich conjecture, die es zu Speicherlokalizität fällig, besser Caching-Verhalten und weniger Zeiger chasing (die, wenn sie nicht die gleichen Dinge, bis zu einem gewissen Grad überlappend).

Andere Tipps

Eigentlich hat Wikipedia einen großen Artikel, die jeder RB-Baum zeigt einfach als B-Baum ausgedrückt werden. Nehmen Sie den folgenden Baum als Beispiel:

Jetzt wandelt es nur zu einem B-Baum (um dies deutlicher zu machen, Knoten noch R / B gefärbt ist, was Sie in der Regel nicht in einem B-Baum):

selben Baum als B-Baum

(kann nicht das Bild hinzufügen hier aus irgendeinem seltsamen Grund)

Das gleiche gilt für alle anderen RB-Baum. Es ist aus diesem Artikel entnommen:

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

aus diesem Artikel zitieren:

Der rot-schwarz-Baum ist dann strukturell äquivalent zu einem B-Baum von Ordnung 4, mit einem minimalen Füllfaktor 33% der Werte pro Cluster mit einem maximale Kapazität von 3 Werten.

Ich fand keine Daten, dass einer von beiden ist deutlich besser als die andere. Ich denke, eine der beiden hatte schon ausgestorben, wenn das der Fall war. Sie unterscheiden sich in Bezug auf, wie viele Daten, die sie im Speicher ablegen müssen und wie kompliziert es ist zum Hinzufügen / Entfernen von Knoten aus dem Baum.

Update:

Meine persönliche Tests legen nahe, dass B-Bäume besser sind, wenn der Suche nach Daten, da sie eine bessere Daten Lokalität haben und somit kann die CPU-Cache vergleicht etwas schneller tun. Je höher die Ordnung eines B-Baum (die Reihenfolge ist die Zahl der Kinder eine Note haben kann), desto schneller wird die Suche erhalten. Auf der anderen Seite haben sie schlechtere Leistung für das Hinzufügen und Entfernen von neuen Einträgen je höher ihre Ordnung ist. Dies wird durch die Tatsache verursacht, dass das Hinzufügen eines Wertes innerhalb eines Knotens lineare Komplexität aufweist. Da jeder Knoten eine sortierten Array, muss man viele Elemente um innerhalb dieser Anordnung bewegen sich, wenn ein Element in der Mitte Zugabe: alle Elemente auf der linken Seite des neuen Elements muss um eine Position nach links oder alle Elemente rechts von bewegt werden das neue Element muss um eine Position nach rechts verschoben werden. Wenn ein Wert eines Knotens nach oben bewegt während eines Einsatzes (die häufig in einem B-Baum geschieht), lässt es ein Loch, das auch entweder durch Bewegen aller Elemente von links um eine Position nach rechts oder durch Bewegen aller Elemente gefüllt werden müssen, um die richtige Position auf der linken Seite. Diese Operationen (in der Regel von C memmove durchgeführt) sind in der Tat O (n). So, je höher die Ordnung des B-Baumes, desto schneller ist die Lookup aber desto langsamer ist die Änderung. Auf der anderen Seite, wenn Sie die Bestellung zu niedrig (zum Beispiel 3), einem B-Baum zeigt nur geringe Vorteile oder Nachteile gegenüber anderen Baumstrukturen in der Praxis (in einem solchen Fall können Sie auch etwas anderes verwenden) wählen. So würde ich immer B-Bäume mit hohen Aufträgen (mindestens 4, 8 und up ist in Ordnung) erstellen.

Dateisysteme, die oft basieren auf B-Trees, verwenden viele höhere Aufträge (Auftrag 200 und sogar noch viel mehr) - das ist, weil sie in der Regel des hoch genug wählen, so dass eine Note (bei maximal zulässige Anzahl von Elementen ) gleich entweder die Größe eines Sektor auf Festplatte oder einen Clusters von dem Dateisystem. Dies ergibt eine optimale Leistung (da ein HD nur einen vollen Sektor zu einer Zeit schreiben kann, auch wenn nur ein Byte geändert wird, wird der gesamte Sektor neu geschrieben sowieso) und optimale Raumausnutzung (wie jede Dateneingabe auf dem Laufwerk mindestens gleich die Größe oder ein Cluster ist ein Vielfaches der Clustergrößen, egal wie groß die Daten wirklich ist). Bedingt durch die Tatsache, dass die Hardware sieht Daten als Sektoren und den Dateisystemgruppen Sektoren zu Clustern, B-Bäume ergeben können viel bessere Leistung und Raumausnutzung für Dateisysteme als jede andere Baumstruktur; das ist, warum sie so beliebt für Dateisysteme sind.

Wenn Ihre App wird ständig den Baum zu aktualisieren, Hinzufügen oder Entfernen von Werts von ihm, ein RB-Baum oder ein AVL-Baum kann eine bessere Leistung im Durchschnitt zeigt im Vergleich zu einer B-Struktur mit hohen Ordnung. Etwas schlechter für die Lookups und sie könnten auch mehr Speicher benötigen, aber in der Regel schnell hierfür Modifikationen sind. Eigentlich RB-Bäume sind noch schneller auf Änderungen als AVL-Bäume, dafür AVL-Bäume ein wenig schneller für Lookups sind, wie sie sind in der Regel weniger tief.

So wie immer es eine Menge hängt, was Ihre Anwendung tut. Meine Empfehlungen sind:

Viele Lookups, kleine Änderungen: B-Baum (mit hohen Ordnung)
Viele Lookups, viele modifiations: AVL-Baum
Little Lookups, viele Änderungen: RB-Baum

Eine Alternative zu all diesen Bäumen sind AA-Trees . Da diese PDF Papier schlägt , AA-Bäume (die sind Tatsache eine Untergruppe von RB-Bäumen) ist nahezu gleich in der Leistung in den normalen RB-Bäumen, aber sie sind viel einfacher als RB-Bäume, AVL-Bäume oder B-Bäume zu implementieren. Hier ist eine rel="noreferrer">, schauen , wie klein es ist (die Hauptfunktion ist nicht Teil der Umsetzung und die Hälfte der Umsetzung Linien tatsächlich Kommentare sind).

Als PDF-Papier zeigt ein Treap ist auch eine interessante Alternative zu klassischen Baum-Implementierung. Ein Treap ist auch ein binärer Baum, sondern eine, die nicht Ausgleich zu erzwingen nicht versuchen. Um den schlimmsten Fall zu vermeiden, dass Sie in unausgeglichen Binärbäumen bekommen kann (was Lookups O (n) anstelle von O (log n) werden), fügt eine Treap etwas Zufälligkeit zu dem Baum. Zufälligkeit kann nicht garantieren, dass der Baum gut ausgewogen ist, aber es macht es auch sehr unwahrscheinlich, dass der Baum extrem unausgewogen ist.

Nichts hindert eine B-Baum-Implementierung, die nur im Speicher arbeitet. wenn Schlüsselvergleiche billig sind, In-Memory-B-Baum kann in der Tat sein, schneller , weil seine Verpackung von mehreren Schlüsseln in einem Knoten verursachen weniger Cache-Misses bei der Durchsuchung. Siehe diesen Link für Leistungsvergleiche. Ein Zitat: „Die Geschwindigkeit Testergebnisse sind interessant und zeigen den B + Baum deutlich schneller für Bäume, um mehr als 16.000 Teile enthalten.“ (B + Tree ist nur eine Variante B-Baum).

Die Frage ist alt, aber ich denke, es ist immer noch relevant ist. Jonas Kölker und Mecki gab sehr gute Antworten, aber ich glaube nicht, die Antworten, die ganze Geschichte abdecken. Ich würde sogar behaupten, dass die ganze Diskussion den Punkt :-) fehlt.

Was ist B-Trees gesagt wurde, gilt, wenn Einträge sind relativ klein (ganze Zahlen, kleine Strings / Wörter, Schwimmern, etc.). Bei Eingaben groß sind (über 100B) die Unterschiede kleiner werden / unbedeutend.

Lassen Sie mich die wichtigsten Punkte über B-Trees Fazit:

Sie sind schneller als jeder binärer Suchbaum (BSTs) aufgrund Speicherlokalizität (was zu weniger Cache und TLB-Fehler).
B-Bäume sind in der Regel mehr Platz effizient, wenn Einträge relativ sind klein oder wenn Einträge sind von unterschiedlicher Größe. Freies Speicherplatz-Management einfacher (ordnen Sie größere Brocken von Speicher) und die zusätzliche Metadaten Overhead pro Eintrag ist geringer. B-Bäume werden etwas Platz als Knoten verschwenden jedoch sind nicht immer voll, landen sie immer noch sein bis kompaktere dass Binary Suchbäume.
Die große O-Leistung (O (log N)) ist für beide gleich. Außerdem, wenn Sie binäre Suche in jedem B-Tree-Knoten tun, werden Sie auch mit der gleichen Anzahl von Vergleich wie in einem BST am Ende (es ist eine schöne Mathe Übung dies zu überprüfen). Wenn die B-Baum-Knoten Größe sinnvoll ist (1-4x Cache-Zeilengröße), linear in jedem Knoten der Suche noch schneller, weil die die Hardware-Prefetching. Sie können auch SIMD-Befehle verwenden für Vergleichen grundlegenden Datentypen (z ganze Zahlen sind).
B-Bäume sind besser geeignet für die Kompression: mehr Daten pro Knoten zu komprimieren sind. In bestimmten Fällen kann dies ein großer Vorteil sein. Man denke nur an ein automatisch inkrementierende Schlüssel in einer relationalen Datenbanktabelle, die verwendet wird, einen Index zu erstellen. Die Blei Knoten eines B-Baum enthalten aufeinanderfolgenden ganzen Zahlen, die sehr komprimieren, sehr gut.
B-Bäume sind eindeutig viel, viel schneller, wenn auf dem Sekundärspeicher gespeichert (wo Sie brauchen Block IO zu tun).

Auf dem Papier B-Bäume haben viele Vorteile und in der Nähe keine Nachteile. Also sollte man nur B-Trees für die beste Leistung verwenden?

Die Antwort ist in der Regel NEIN - wenn der Baum in dem Speicher paßt. In den Fällen, in denen die Leistung ist entscheidend Sie eine Thread-sichere baumartigen Datenstruktur wollen (einfach ausgedrückt, können mehrere Threads mehr Arbeit als ein einziges tun). Es ist problematisch, einen B-Tree-Unterstützung gleichzeitige Zugriffe zu machen, als ein BST zu machen. Der direkteste Weg nach vorn einen Baum Unterstützung gleichzeitige Zugriffe zu machen ist, Knoten zu sperren, wie Sie durchqueren / ändern sie. In einer B-Struktur sperren Sie mehrere Einträge pro Knoten, was zu mehr Serialisierungspunkte und mehr stritten Schlösser.

Alle Baum Versionen (AVL, Rot / Schwarz, B-Baum, eine andere) haben unzählige Varianten, die in unterscheiden, wie sie die Parallelität unterstützen. Die Vanille-Algorithmen, die in einem Hochschulstudium oder lesen von einigen einleitenden Bücher gelehrt werden, sind so gut wie nie in der Praxis eingesetzt. So ist es schwer zu sagen, welcher Baum am besten führt, da es keine offizielle Vereinbarung ist auf die genauen Algorithmen hinter jedem Baum sind. Ich würde vorschlagen, die Bäume zu denken, eher wie Datenstruktur Klassen erwähnt, die bestimmten baumartige Invarianten gehorchen als präzise Datenstrukturen.

Nehmen Sie zum Beispiel die B-Baum. Der Vanille-B-Baum ist so gut wie nie in der Praxis eingesetzt - man es nicht machen kann gut Maßstab! Die häufigste B-Tree-Variante verwendet wird, ist das B + -Baum (weit verbreitet in der Datei-Systemen, Datenbanken). Die Hauptunterschiede zwischen dem B + -Baum und der B-Baum: 1) müssen Sie nicht speichern Einträge in dem inneren Knoten des Baums (also müssen Sie keine Schreibsperren hoch in dem Baum, wenn Sie einen Eintrag in einem inneren Knoten gespeichert zu ändern) ; 2) Sie haben Verbindungen zwischen den Knoten auf der gleichen Ebene (also müssen Sie die Eltern eines Knotens nicht sperren, wenn die Reichweite sucht tun).

Ich hoffe, das hilft.

Jungs von Google vor kurzem ihre Implementierung von STL-Container freigegeben, die auf B-Bäume basiert. Sie behaupten, ihre Version ist schneller und verbrauchen weniger Speicher im Vergleich zu Standard-STL-Containern, realisiert über rot-schwarze Bäume. Weitere Details hier

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

http://freshmeat.net/projects/bps

sind recht schnell. Sie verwenden auch weniger Speicher als normale BST-Implementierungen, da sie die BST-Infrastruktur von 2 oder 3 Zeiger pro Knoten nicht erforderlich ist, plus einige zusätzliche Felder die Ausgleichsinformation zu halten.

Sie sind in verschiedenen Umständen sed - B-Bäume verwendet werden, wenn die Baumknoten müssen zusammen in der Lagerung gehalten werden - in der Regel, da der Speicher eine Platte Seite ist und so die Neugewichtung Vey teuer sein könnte. RB Bäume verwendet werden, wenn Sie diese Einschränkung nicht haben. So B-Bäume wahrscheinlich schneller sein wird, wenn man (sagen wir) eine relationale Datenbankindex implementieren möchten, während RB Bäume wahrscheinlich wird fasterv (sagen wir) eine im Speicher suchen.

Sie haben alle das gleiche asymptotische Verhalten, so hängt die Leistung mehr über die Ausführung als welche Art von Baum Sie verwenden. Eine Kombination von Baumstrukturen könnte tatsächlich der schnellste Ansatz sein, wobei jeder Knoten eines B-Baum paßt genau in eine Cache-Zeile und eine Art von binärem Baum wird verwendet in jedem Knoten zu suchen. Verwalten des Speichers für die Knoten selbst auch Sie ermöglichen könnten noch größere Cache-Ort zu erreichen, aber zu einem sehr hohen Preis.

Persönlich benutze ich nur, was in der Standardbibliothek für die Sprache, die ich verwende, da es eine Menge Arbeit für einen sehr geringen Leistungsgewinn (falls vorhanden) ist.

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

Außerdem ... die Höhe eines Rot-Schwarz-Baum ist O (log [2] N), während die von B-Baum ist O (log [q] N), wobei ceiling [N] <= q <= N. Also, wenn wir Vergleiche in jedem Tastenfeld von B-Baum betrachten (das festgelegt ist, wie oben erwähnt), dann Zeit Komplexität des B-Baumes <= Zeitkomplexität von Rot-schwarz-Baum. (Gleich Fall für einzelne Aufzeichnung gleich in Größe einer Blockgröße)

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow