B + Baum Datenstruktur in Erlang

Question

Gibt es eine Open Source bekannte Implementierung der B+ Tree Datenstruktur in Erlang?

Answer 1

Ich würde auf jeden Fall empfehlen, in die eleveldb Anwendung zu suchen, wenn Sie wirklich einen B + Baum brauchen. Der Punkt ist, dass Sie Daten in Blättern eines Baumes, offline auf der Festplatte speichern möchten, da dies B + -Bäume normalerweise eine Option sind. Es gibt auch eine Variante in reinem Erlang von LevelDB namens hanoidb, die ebenfalls sehr nett ist, geschrieben von Kresten Krab Thorup. Gleicher Einsatzbereich.

Wenn Sie In-Memory-Speicher benötigen, sollten Sie sich entweder ETS oder Mnesia ansehen (letzteres für die Verteilung). In Erlang sind dies die schnellsten Lösungen, da Sie den Vorteil haben, niemals auf die Festplatte zu stoßen. Dies trifft insbesondere dann zu, wenn Sie Standard-Schlüssel/Wert-Lookups für Ihre Daten durchführen können, ohne innerhalb des Transaktionskontextes in Mnesien zu laufen (dreckiges Lesen). Die typische Suchgeschwindigkeit beträgt dann 5-10 Nanosekunden.

Answer 2

Es gibt keine eigenständige Bibliothek, die ich kenne. Die CouchDB source code ist jedoch sehr gut lesbar und gut implementiert.

Answer 3

nur eine Alternative, wenn Sie nicht in Open-Source-Datenbanksysteme hacken wollen:

Chris Okasaki der rein funktionale Datenstrukturen können Sie einen kleinen Einblick geben, es selbst zu implementieren. B + Baum selbst ist nicht so kompliziert aus meiner Erfahrung.

Ich würde empfehlen, gb_trees zu verwenden, wenn Sie sowohl In-Memory-Speicher und etwas mehr Low-Level (in gewissem Sinne) als Ets und Mnesia wollen.