Wie lagern Sie einen trie in eine relationale Datenbank?

Habe ich ein prefix-trie. Was ist die empfohlene schema für die Darstellung dieser Struktur in einer relationalen Datenbank? Ich brauche substring matching effizient bleiben.

  • Ja, versuche nicht-Baum. Siehe en.wikipedia.org/wiki/Trie
  • Sind Sie der Speicherung und dem abrufen der trie zu/von DB, die im code verwendet werden ? Denn für DB-lookup gibt es integrierte tools wie full-text indexing (basierend auf ähnlichen Prinzipien)
InformationsquelleAutor |
  1. 11

    Wie über die Materialized Path design?

    CREATE TABLE trie (
  path VARCHAR(<maxdepth>) PRIMARY KEY,
  ...other attributes of a tree node...
);

    Speichern ein Wort wie "stackoverflow":

    INSERT INTO trie (path) VALUES
  ('s'), ('st'), ('sta'), ('stac'), ('stack'),
  ('stacko'), ('stackov'), ('stackove'), ('stackover'),
  ('stackover'), ('stackoverf'), ('stackoverflo'),
  ('stackoverflow');

    Die materialisierte Pfad in dem Baum ist das Präfix der Sequenz der Zeichen selbst. Dies bildet auch den Primärschlüssel. Die Größe des varchar-Spalte ist die maximale Tiefe des trie, die Sie speichern möchten.

    Ich kann nicht an nichts denken, das mehr einfach und unkompliziert, und es bewahrt effiziente string-Speicherung und-Suche.

    • Der link leitet auf nichts von Interesse. Hier ist eine archivierte version: web.archive.org/web/20071019044908/http://www.dbazine.com/...
    • danke, ich beantwortete diese 5.5 Jahren, so ist es nicht verwunderlich, dass einige links, die veraltete gehen.
    • Können Sie ein Beispiel geben, wie wird die Abfrage von dieser Tabelle sagen, "st", und es gibt mehr Wörter wie "stackoverflowone"
    • SELECT path FROM trie WHERE path='st'. Wenn dies gibt eine nicht-leere Menge, dann "st" ist in der Trie. Ich weiß nicht, was du redest, auf den zweiten Punkt.
    InformationsquelleAutor
  2. 0

    Nicht alle Ihre Einheiten haben eine Beziehung mit einer anderen? Wenn nicht, das ist nicht relational ist, eine hash-Tabelle mit einer Serialisierung würde es tun.

    • Das ist nicht wirklich ein trie... ich Stimme zu, dass es wohl Sinn macht, um es aus der db, aber verwandelte Sie in eine hashtable?
    • O(1) algorithmen sind nicht gut auf die Einsparung von Ressourcen. 😉
    • Aber Sie sind gut für die Geschwindigkeit: es ist immer ein Kompromiss.
    InformationsquelleAutor
Schreibe einen Kommentar