Spaß mit Nested-Sets

In den letzten Tagen habe ich ein wenig an einer neuen Anwendung programmiert. Teil davon ist ein Baum in dem eine Hierarchie von Tags abgebildet ist und eine Liste mit Dateien, denen man n Tags zuweisen kann. Nach Dateien soll man über diese Tag-Hierarchie suchen können. Da sich nach einer anfänglichen Konfiguration die Tag-Hierarchie nicht mehr großartig ändert, habe ich mich für das Nested-Set Datenmodell zum Speichern in der Datenbank entschieden.

Die Tabellenstruktur des Baums, der Dateien und der Zuordnungstabelle sieht in etwa so aus:

Nodes { id, lft, rgt, parentId }
FileNodes { id, nodeId, fileId }
Files { id, name }

Im Tag-Baum will ich neben dem Namen des Tags auch die Anzahl der Dateien anzeigen, denen dieser Tag zugeordnet ist. Dabei dürfen natürlich Dateien in der Hierarchie nicht doppelt gezählt werden. Mit diesem Beispiel hier würde ich also für die Knoten folgendes Ergebnis bekommen ([Knoten]: Anzahl):
[1]: 5, [2]: 4, [3]: 3, [4]: 1, [5]: 2, [6]: 2

Erster Gedanke: Eine kleine SQL-Abfrage zusammenbasteln, dann geht das schon. Mein Ergebnis:

Kann man bestimmt noch verbessern aber ich bin kein SQL-Profi *g*. Falls jemand einen Vorschlag hat, immer her damit.
Auf jeden Fall habe ich die Abfrage auf dem SQLServer 2008 Express getestet und mit einer Testdatenmenge von 2000 Tags, 10000 Dateien und 75000 Zuordnungen lieferte mir der Server innerhalb von 60ms ein Ergebnis. Nicht schlecht für den ersten Versuch. Eine Anforderung an mein Programm ist aber, dass es auch mit SQLServer Compact Edition oder SQLite funktioniert. Die Compact Edition streikt bei der Abfrage direkt, da sie keine Nested Selects unterstützt. Mit SQLite funktioniert es, allerdings benötigt er für einen Tag schon ca. 600ms. Den User mehrere Minuten auf das Ergebnis warten lassen ist natürlich nicht akzeptabel. 🙂

Im letzten Semester habe ich an der Uni die Vorlesung “Grundlagen Algorithmen und Datenstrukturen” besucht und dabei kam auch die Tiefensuche dran. Die hat mich dann auf die Idee gebracht, wie ich die Anzahl der Beziehungen auch einfach selbst ermitteln kann, wenn die Datenbank zu lange brauche:

Erst mal alle Knoten und Beziehungen aus der Datenbank abrufen, aus den Daten dann eine Objekt-Hierarchie erstellen, die ich sowieso für die Darstellung des Baums brauche und zusätzlich jedem Knoten noch eine Liste mit allen File-IDs zuweisen, die ihm direkt zugeordnet sind (im Beispiel bekommt [2] also B, [5] C,D, etc.). Danach wende ich die Tiefensuche an. Beim Wurzelknoten beginnend besuche ich alle Kinder, für jedes Kind wieder rekursiv alle Kinder, etc. bis ich am untersten Knoten angelangt bin (=> der Knoten hat keine Kinder mehr). Mit dem Knoten fange ich dann an und erstelle eine Liste mit allen seinen File-IDs, die ich in einer HashMap/Dictionary ablege. Als Key dient die ID des Knoten, der Value ist die File-ID-Liste. Anschließend erstelle ich eine Kopie der Liste und speichere sie unter der ID des Elternknoten in der HashMap. Falls unter der jeweiligen Knoten-ID bereits eine Liste existiert, wird diese mit der Vereinigungsmenge von sich selbst und der neuen Liste ersetzt.

Am Beispiel:

  1. Knoten 4: { A }, Knoten 2: {A}
  2. Knoten 5: { C, D }, Knoten 2: { A, C, D }
  3. Knoten 2: { A, C, D, B }
  4. etc.

Ich hatte zuerst Bedenken, dass der Algorithmus zu lange brauchen würde und ich trotzdem mit mehreren Sekunden Wartezeit leben muss, die konnte mein Rechner aber glücklicherweise zerstreuen 🙂 . Mit der oben angegebenen Datenmenge braucht der Algorithmus ca. 55ms 😀

Ergebnis: Ein glücklicher Programmierer mit einem flott durchgezählten Tag-Baum 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.