Relation Tabelle Datenstruktur in Clojure

Question

Ich bin auf der Suche nach Clojure Datenstruktur, die funktioniert wie Relationstabelle (wie in relationalen Datenbanken).

Karte (auch bidirektionale) ID -> (val1, val2, val3, ...) macht nicht die Arbeit. Wenn ich zum Beispiel alle Zeilen mit val2 = "etwas" finden möchte, braucht es O (n).

Aber ich möchte Suche in einer Spalte in O (log n) durchführen!

Answer 1

Die Suche nach Zeilen in einer Datenbank mit einem Spaltenprädikat ohne Index ist O (n), da jede Zeile geprüft werden muss, wenn sie mit dem Prädikat übereinstimmt. Wenn ein Index für eine Spalte vorhanden ist, die von Ihrem Vergleichselement verwendet wird, kann der Index verwendet werden, um alle Zeilen für einen bestimmten Wert zu finden, indem dieser Wert als Schlüssel im Index gesucht wird, um alle übereinstimmenden Zeilen abzurufen. Dann ist es normalerweise log (n) Operation (es hängt von der internen Implementierung des Index ab, beispielsweise für B-Baum ist es log (n)).

Ich bin nicht bewusst von Out-of-the-Box-Implementierung einer Clojure-Datenstruktur mit Eigenschaften, wie sie normalerweise single-purpose (zB Karte ist eine assoziative Datenstruktur für die Suche nach einem einzigen Schlüssel, nicht mehrere Schlüssel als in DB mit mehreren Indizes). Sie würden eher eine Bibliothek benötigen, die eine Art In-Memory-Datenbank bereitstellt (zB wie in Thumbnail in seinem Kommentar erwähnt) DataScript, oder sogar In-Memory SQL DB mit JDBC-Schnittstelle (zB H2SQL, HSQLDB oder Speicher speichert).

Ich bin mir Ihrer spezifischen Anforderungen nicht sicher, aber Sie könnten einige der Funktionen auch selbst implementieren, indem Sie die grundlegende API von Clojure verwenden. Zum Beispiel könnten Sie eine Clojure Set als „Tabelle“ verwenden und verbessern es mit einigen Funktionen von clojure.set:

Ihr Tisch:

(def my-table #{{:id 1 :name "John" :age 30 :gender :male} 
       {:id 2 :name "Jane" :age 25 :gender :female} 
       {:id 3 :name "Joe" :age 40 :gender :male}}) 

Und Ihre Indizes angeben:

(def by-id (clojure.set/index my-table [:id])) 
(def by-age (clojure.set/index my-table [:age])) 
(def by-gender (clojure.set/index my-table [:gender])) 

Und Verwenden Sie dann Ihre Indizes beim Abfragen/Filtern Ihrer Tabelle:

(clojure.set/intersection 
    (by-age {:age 30}) 
    (by-gender {:gender :male})) 

;; => #{{:id 1, :name "John", :age 30, :gender :male}}