Hallo Forum

Sodeli, hier bin ich mal wieder mit einer Frage :-)
Vielleicht ist der Titel ein bisschen zu "grob" geschrieben ... ich will nicht einen eigenen MySQL-Server schreiben ;-)

Vieleicht vorneweg: Testsetup ist wie folgt:
HP ML330 (1x 1GHz CPU, 2.5 GB RAM) - Debian 5, Perl 5.10.0, MySQL 5.0.51a
VM auf ESXi (1x 3GHz CPU, 1GB RAM) - Debian 6, Perl 5.10.1, MySQL 5.1.49

Für ein kleines (bis jetzt Hobby-) Projekt will ich eine (hierarchische) Ordnerstruktur in einer Datenbank abbilden. Ich habe bereits Stunden mit Googeln und probieren verbracht, sonst würde ich hier nicht fragen!

Im Moment will ich eigentlich nur, dass das Script folgendes macht:
- Einen bestimmten Order nach allen Unterordner (und diese wieder nach Unterordner etc. -> rekusriv) absuchen
- Für jeden gefundenen Ordner prüfen, ob er in der Datenbank ist, wenn nicht, füge ihn hinzu

Schlussendlich will ich eigentlich sehen, welche Ordner in der Datenbank existieren, aber auf dem Dateisystem nicht und welche Ordner auf dem Dateisystem existieren aber in der Datenbank nicht.

Mittlerweile bin ich (mit Hilfe) auf die Idee gekommen, dass man zuerst die gesamte Datenbank auslesen und die Struktur in einem "Hash-Tree" (Hash of Hashes) abbilden könnte.

Danach kann man ja recht einfach prüfen, ob z.B. der Pfad /data/test1/ha1/blubb1 in der Datenbank resp. im Hash-Tree vorhanden ist:


Ausserdem könnte man "gefundene" Einträge (also solche die sowohl auf dem Dateisystem wie auch im Hash-Tree existieren) aus dem Hash-Tree entfernen, was den Ressourcen-Verbrauch verrinngern würde, da der Hash-Tree immer kleiner würde. Dies hätte auch noch der Vorteil, dass man schlussendlich im Hash-Tree nur noch die Einträge hat, die auf dem Dateisystem nicht existieren (diese Einträge wurden aus dem Hash-Tree nicht entfernt, weil sie nicht überprüft wurden).

Nun, was ist überhaupt mein Problem?
Mein Problem ist, dass ich hier nicht nur von 100 oder 1'000 Ordnern rede, die ich in der Datenbank habe, sondern von 10'000, 100'000 oder sogar 1'000'000 ... auch wenn das letzte wohl in der Praxis weniger vorkommen wird. Bis jetzt habe ich immer versucht, die Daten in einer MySQL-DB (also relational) zu speichern, und dort die Hierarchie abzubilden.
Woran ich jetzt scheitere, ist die Performance wenn ich schon nur 80'000 Ordner in der DB habe.

Folgende "Modelle" habe ich probiert:
### Parent-Modell ###
- Ein Datensatz besteht aus ID, ParentID und name.
- Die Hierarchie wird über die ParentID "gebaut".

# Vorteil #
- Relativ einfache und leicht verständliche Struktur
- Es wird Platz gespart, da nur der Name (nicht den ganzen Pfad) gespeichert wird

# Nachteil #
- Seeeeehr langsam beim aufbauen des Baumes ...

### Pfad-Modell ###
- Jeder Datensatz besteht aus ID und pfad.

# Vorteil #
- Es kann einfach einen ganzen Pfad abgefragt werden
- Es kann einfach überprüft werden, ob ein Pfad bereits in der DB ist

# Nachteil #
- Der Aufbau des Baumes gestaltet sich eher schwierig, da in der Datenbank keine Hierarchie abgebildet ist
- Es wird viel Platz gebraucht, da immer der komplette Pfad gespeichert wird

### Nested Sets ###
- Jeder Datensatz besteht aus ID, name, lft und rgt
- Relation wird über lft und rgt hergestellt

# Vorteil #
- Schnelle und "einfache" Abfragen (meistens nur ein SQL-Statement)
- Platzsparend, da nicht der ganze Pfad gespeichert wird

# Nachteile #
- Relativ komplizierte Struktur
- Änderungen sind ressourcen-fressend, da sehr viele Datensätze angepasst werden müssen

Für die Nested-Sets habe ich dies hier gebraucht: http://www.klempert.de/nested_sets/#kap1
Dort hat es auch einen schönen Performance-Vergleich zwischen den 3 Modellen.

Nun habe ich testweise mit einem Script auf den beiden Servern Ordnerstrukturen mit bis zu 110'000 Ordner angelegt (ca. 3 - 4 Ebenen in der Breite und ca. 10 Ebenen in der Tiefe), wobei jeder Ordnernamen 9 - 10 Zeichen lang ist (also 10 Bytes).

Danach habe ich mit Scripts die Ordnerstruktur in die DB (MySQL) importiert. Dies ging auf beiden Servern für jedes der 3 Modelle recht fix.
Aber jetzt:
Auf dem zweiten Server (3GHz CPU) hat das Erstellen der Ordnerstruktur (resp. nur die Abfrage der Datenbank mit dem entsprechenen Statement, siehe unten) aus dem Nested Sets ganze 10 Minuten gebraucht für 80'000 Ordner.
Auf dem alten Server (1GHz CPU) hat es für 110'000 Ordner ganze 70 Minuten gedauert.
Über die beiden anderen Modelle (Parent- und Pfad-Modell) fange ich lieber gar nicht erst an ... das Parent-Modell war etwa um den Faktor 40 langsamer als das Nested Sets-Modell ... also hätte ich für die Berechnung mit 80'000 Ordner auf dem besseren Server ganze 400 Minuten (= 6.5 Stunden) gebraucht ...

Mittlerweile frage ich mich, ob eine relationale Datenbank wie MySQL der richtige Weg ist ...
In der Datenbank sollte eigentlich neben den Ordner auch noch die Files (also ich meine eigentlich auch nur "Verweise" darauf mit den Namen) sowie Config-Optionen und weitere Dinge gespeichert werden.

Nun, wäre evt. die Speicherung der Daten in einer hierarchischen Form in einer Datei vieleicht einfacher? Z.B. indem man den Hash-Tree via Data::Dumper in eine Datei schreibt, und diese dann wieder einliest? Eine relationale Datenbank wäre mir allerdings trotzdem irgendwie sympathischer ...

Eine weitere Idee, die mir gerade eingefallen ist, wäre folgende:
Anstatt dass ich aus der Datenbank heraus einen Hash-Tree generiere und diesen dann mit den Pfaden von der Ordnerstruktur vergleiche, könnte ich z.B. auch für jeden gefundenen Ordner ein SQL-Statement wie "Update z.B. den Zeitstempel in der DB, wenn der Ordner schon eingetragen ist, ansonsten füge ihn zusätzlich ein" (mit REPLACE oder INSERT IF NOT EXISTS???) durchführen. Vielleicht gibt es ja auch für UPDATE- oder REPLACE-Statements eine ähnliche Möglichkeit wie "$dbh->last_insert_id", also welche ID jetzt genau geupdated wurde, diese könnte man dann für die Child-Objekte weierverwenden: "Wenn ein Eintrag mit diesem Namen UND derselben ParentID existiert, update ihn, ansonsten füge ihn hinzu" ...

Wäre das vielleicht eine elegante Lösung?

Ich hoffe auf eure Hilfe und Danke jetzt schon für jeden investierten Schweisstropfen :-)
Lousek