Hunderttausende Dateinamen mit Pfaden effizient in Datenbank speichern

[Benmik]

Ich muss mehrere Hunderttausend Dateinamen mit den zugehörigen Pfaden in einer Datenbank speichern. Die Verzeichnisnamen blähen die Datenbank natürlich gewaltig auf. Ich habe mir schon selbst ein System gebastelt, in dem jeder einzelne Verzeichnisname eine ID bekommt und die Pfade zusammengesetzt werden. Das funktioniert auch, aber leider lassen sich nun die Dateien inklusive Pfade nur noch umständlich vergleichen.

Für sowas muss es doch schon eine Lösung geben.

[Hansa]

Wo liegt denn das Problem ? An 2 Byte oder was ? :lol: Sagen wir 1 Mio. Dateinamen mit Pfadlängen von 200 Zeichen (geht nicht nur max. 128 ? :gruebel:), das wären 200 MB. Nicht viel mehr als Peanuts für DB. Und das geht sogar noch locker auf CD. Oder zig-fach auf USB-Stick für 5 EUR.

[Puke]

Zahlen sind doch dreimal besser zu vergleichen als Strings?
Nur den Dateinamen würde ich als String zu jedem Record speichern. Für ordnerstrukturen relationen mit schlüsseln!

[Puke]

@Hansa: Hilfe nein! Stell dir vor du willst einen Ordnernamen umbenennen... Bei deiner Lösung musst du 100000 mal überprüfen und ändern. Bei mir brauchst du nur einmal die Relations-Tabelle durchgehen und einmal ändern....

[Benmik]

Danke für die schnellen Antworten.

Hansa: Jeder Verzeichnisname darf - wenn ich mich nicht irre - unter NTFS 256 Byte umfassen. Und wenn jemand will, kann er 20 Unterverzeichnisse verschachteln. Da ist man schnell bei ziemlichen Größen.

Puke: Ja, auf sowas bin ich auch gekommen. Hast du da vielleicht mal ein Codebeispiel? Und wie macht man das mit Dateivergleichen? Da muss man dann für jede einzelne Datei den Pfad zusammensetzen?

Benmik

[Perlsau]

Zitat:

Zitat von Benmik (Beitrag 1251160)

Jeder Verzeichnisname darf - wenn ich mich nicht irre - unter NTFS 256 Byte umfassen. Und wenn jemand will, kann er 20 Unterverzeichnisse verschachteln. Da ist man schnell bei ziemlichen Größen.

Offenbar hast du da was falsch verstanden. Wenn du selbst einmal Hand anlegen und versuchen würdest, einen Pfad zu erstellen, der größer ist als 232 Zeichen, würdest du ganz einfach feststellen: Es geht nicht.

Zitat:

Zitat von Benmik (Beitrag 1251160)

Und wie macht man das mit Dateivergleichen? Da muss man dann für jede einzelne Datei den Pfad zusammensetzen?

Nein, du kannst dir z.B. ein View erstellen, das einen Concat von Pfad und Dateiname beinhaltet. Ich erstelle Views gewöhnlich für alle Tabellen, in denen Spalten auf Detailtabellen verweisen.

[Puke]

Bin eher Theoretiker ...
Da ich nicht weiß wie du deine datenbankzugriffe organisierst, mach ich dir mal diesen Vorschlag:

Pfade zusammensetzen ( muss auf Datenbanken umgestellt werden! sry):

Delphi-Quellcode:

// Im loc_Datensatz stehen die Dateipfad-Nummern
Result  := loc_Datensatz.device; // Festplatte oder sonstwas
For loc_i_counter := 0 to loc_Datensatz.AnzahlOrdnerTeile do
  // FTabellePfade sind die Dateipfade
  Result := Result + FTabellePfade.gebepfadNummer(loc_datensatz.Pafdnummer(loc_i_counter));
End;
Result := Result + loc_Datensatz.Dateiname;

Bei Vergleich fehlt mir jetzt das Wissen wofür?
Im Prinzip kannst du zwei Datensätze nehmen und dann Nummer für Nummer miteinandervergleichen. hurra wir lieben Schleifen ...
Vorteil es bleibt linear! ( bei Strings nicht ganz so gegeben )

Gruß
Puke

[michaelthuma]

Schwierige Übung. Versuche die Bitmuster der Pfade zu komprimieren und in einem Index abzulegen ohne DB.

Warum willst du den Pfad vergleichen? Sucht du Duplikate?

Zitat:

Zitat von Benmik (Beitrag 1251153)

Ich muss mehrere Hunderttausend Dateinamen mit den zugehörigen Pfaden in einer Datenbank speichern. Die Verzeichnisnamen blähen die Datenbank natürlich gewaltig auf. Ich habe mir schon selbst ein System gebastelt, in dem jeder einzelne Verzeichnisname eine ID bekommt und die Pfade zusammengesetzt werden. Das funktioniert auch, aber leider lassen sich nun die Dateien inklusive Pfade nur noch umständlich vergleichen.

Für sowas muss es doch schon eine Lösung geben.

[mjustin]

Zur Beschleunigung der Vergleiche bietet sich der Einsatz eines Hashwertes an...

[Benmik]

Wozu das Ganze?

Die Dateien in der DB sollen mit neuen Dateien verglichen werden, ob sie - also Pfad und Dateiname - schon vorhanden sind. Über TWin32FindData erfolgt dann die weitere Prüfung auf Identität.

Hashwert: Genau! Sind für alle Dateien in der DB vorhanden. Durch den Vergleich soll aber gerade die Berechnung von neuen Hashwerten eingespart werden.

Perlsau: Genau das habe ich auch schon realisiert (wenn ich mal davon ausgehe, dass ein View praktisch eine Abfrage ist). Ich hatte nur 2 Probleme:

1. Zum einen wird sehr viel Speicher verbraucht (unter XP sind oft nur 2 GB im Einsatz, mehr als 3,5 bei 32 Bit nicht drin)

2. Ich muss dann eventuell sehr lange Pfade vergleichen. Ein Index wird da sehr groß, oder? Ich würde gerne eine eindeutige ID für jede Datei vergeben (Cardinal) und die vergleichen. Ist für bestehende Dateien in der DB natürlich kein Problem, aber es gibt wohl keinen Weg, für eine neue Datei inklusive Pfad auf schnelle Weise zu der identischen ID zu kommen (wenn Name und Pfad gleich sind), oder?

[himitsu]

Einige Dateisysteme bieten auch die Möglichkeit Dateien/Verzeichnisse via ID anzusprechen.
Man braucht da also keinen Dateinamen.

Oder man sieht jeden vollständigen Dateipfad als einzelnen String an, welcher in einer Pfadtabelle gespeichert wird.
> nur eine ID auflösen (hilft nur, bei wenigen Verzeichnissen und vielen Dateien)
Und wer unbedingt will, kann noch weiter sparen, indem er nur einzelne Verzeichnisnamen und die Rootverzeichnisse speichert und diese dann als Baum untereinander verlinkt.
> hier muß man halt erst wieder die Pfade rekursiv zusammensetzen

[Benmik]

Vielleicht kann ich die Frage etwas kondensieren.

Ich habe in einem Pfad zu einer Datei z.B. 10 Verzeichnisse, die alle eine ID (Word) haben, also 10 maximal fünfstellige Zahlen.
Gibt es einen Algorithmus, der aus einer solchen Zahlenkombination - bei der auch die Reihenfolge stimmen müsste - eine eindeutige ID errechnen kann?

Wie wäre es, wenn ich die Zahlen hintereinander schriebe und daraus einen Hashwert (z.B. MD4) errechnen würde. Wäre das nicht eindeutig?
Wie machen die Profis sowas?

[Perlsau]

Zitat:

Zitat von Benmik (Beitrag 1251166)

Die Dateien in der DB sollen mit neuen Dateien verglichen werden, ob sie - also Pfad und Dateiname - schon vorhanden sind. Über TWin32FindData erfolgt dann die weitere Prüfung auf Identität.

Wenn du, wie du schreibst, auf Vorhandensein einer Datei in einem bestimmten Verzeichnis prüfen willst, wozu benötigst du dann eine Datenbank?

Delphi-Quellcode:

If FileExists then

liefert dir doch bereits diese Information.

Zitat:

Zitat von Benmik (Beitrag 1251166)

Hashwert: Genau! Sind für alle Dateien in der DB vorhanden. Durch den Vergleich soll aber gerade die Berechnung von neuen Hashwerten eingespart werden.

Das verstehe ich jetzt nicht: Wie willst du einen Hashwert finden, wenn du gar nicht weißt, welchen Hashwert du suchst? Das erfährst du doch erst, wenn du aus einem Dateinamen (incl. Pfad) einen Hashwert berechnest. Gibt's den berechnete Hash bereits in der Datenbank, ist die Datei vorhanden, da aus derselben Pfad-Datei-Angabe immer auch derselbe Hashwert berechnet wird, wenn du stets dieselbe Berechnungsmethode anwendest.

Zitat:

Zitat von Benmik (Beitrag 1251166)

Perlsau: Genau das habe ich auch schon realisiert (wenn ich mal davon ausgehe, dass ein View praktisch eine Abfrage ist).

Ein View ist eine virtuelle Tabelle, die in der DB sozusagen ein fest verdrahtetes Select-Ergebnis darstellt. Du kannst ein View wie eine normale Tabelle auslesen. Darin steht dann nicht mehr nur die Id 15, sondern z.B: "C:\Temp\Test\". Wie du mit deinem DBMS ein View erstellst, sollte in der Dokumentation stehen.

Zitat:

Zitat von Benmik (Beitrag 1251166)

1. Zum einen wird sehr viel Speicher verbraucht (unter XP sind oft nur 2 GB im Einsatz, mehr als 3,5 bei 32 Bit nicht drin)

Wofür wird sehr viel Speicher verbraucht?

Zitat:

Zitat von Benmik (Beitrag 1251166)

2. Ich muss dann eventuell sehr lange Pfade vergleichen. Ein Index wird da sehr groß, oder? Ich würde gerne eine eindeutige ID für jede Datei vergeben (Cardinal) und die vergleichen. Ist für bestehende Dateien in der DB natürlich kein Problem, aber es gibt wohl keinen Weg, für eine neue Datei inklusive Pfad auf schnelle Weise zu der identischen ID zu kommen (wenn Name und Pfad gleich sind), oder?

Was heißt "sehr lange Pfade"? Ich hatte vorhin mal getestet und konnte in einem Ordner mit Namen "0123456789" 31 Verschachtelungen mit demselben Namen erstellen, dann war Schluß. Mehr als 256 Byte stehen da wohl nicht zur Verfügung. Doch wie bereits empfohlen: Teste es selbst aus, dann weißt du, was du hast.

Inwieweit soll dir eine eindeutige ID dabei helfen, zu überprüfen, ob eine gegebene Datei incl. Pfad bereits eingetragen ist? Es sei denn, du verwendest keine automatisch erstellten Id, sondern einen Hash, den du aus Datei und Pfad erzeugst und als Primary Key festlegst. Aber hier mußt du natürlich aus dem gesuchten Dateinamen erstmal einen Hashwert erzeugen, um danach suchen zu lassen.

Zitat:

Zitat von Benmik (Beitrag 1251170)

Ich habe in einem Pfad zu einer Datei z.B. 10 Verzeichnisse, die alle eine ID (Word) haben, also 10 maximal fünfstellige Zahlen.
Gibt es einen Algorithmus, der aus einer solchen Zahlenkombination - bei der auch die Reihenfolge stimmen müsste - eine eindeutige ID errechnen kann?

Glaubst du, diese Id wäre nicht eindeutig? Hast du bereits überprüft, ob bei verschiedenen Dateien in verschiedenen Ordnern dieselben Ids vergeben werden? Was sind das für Ids? Woher stammen diese Werte?

Zitat:

Zitat von Benmik (Beitrag 1251170)

Wie wäre es, wenn ich die Zahlen hintereinander schriebe und daraus einen Hashwert (z.B. MD4) errechnen würde. Wäre das nicht eindeutig?

Wenn du aus einem vollständigen Dateinamen einen Hashwert erzeugst, ist der eindeutig, weil in einem Ordner niemals zwei Dateien mit demselben Namen stehen können.

Zitat:

Zitat von Benmik (Beitrag 1251170)

Wie machen die Profis sowas?

Keine Ahnung. Was ist ein Profi? Jemand, der das beruflich macht? Oder jemand, der eine ähnliche Aufgabe bereits gelöst hat?

[Sir Rufo]

Ein vergleichbares Konzept wird bei der Backup-Software Retrospect verwendet. Bis zur Version 7.x wurde vor dem Backup von allen Dateien Hash-Werte gebildet und anhand derer wurde überprüft, ob sich die Datei geändert hatte. Als Option können auch gleiche Dateien (gleiche Hash-Werte/Datei-Größe) nur einmal im Backup gespeichert werden.

Die Pfade werden logischerweise auch gespeichert (ich vermute mal auch als Tree, obwohl die Katalog-Dateien auch sehr groß werden).

Ab der Version 8.x läuft ein Dienst mit, der bei Dateiänderungen direkt den Hash-Wert neu berechnet um die Zeit bis zum wirklichen Anlaufen des Backups zu verkürzen.

[Benmik]

Ich bitte um Entschuldigung, ich dachte, es würde reichen, mich auf ein Detailproblem zu konzentrieren. Wie aus diesem Beitrag hervorgeht, geht es um ein selbst gestricktes Backup-Programm, insofern hat Sir Rufo ins Schwarze getroffen. Ich hätte Perlsau einige Mühe ersparen können. Es geht also natürlich darum, bereits gesicherte Dateien in einer DB zu speichern und bei neuen Dateien nachzuschauen, ob man sich die erneute Erstellung einer Prüfsumme sparen kann (in vielen Fällen über 99%). Trotzdem - der Hinweis von Perlsau, ein MD4 von Pfad und Dateinamen zu erstellen, ist schonmal gut!

[Perlsau]

Wenn es auch um die Überprüfung von Dateiänderungen geht (Dateiname bleibt gleich, Änderungsdatum und ggf. Größe jedoch unterschiedlich), mußt du zur Berechnung eines eindeutigen Hashwerts natürlich auch Größe und Datum mit einbeziehen.

[Benmik]

Natürlich. Von jeder Datei wird aber ohnehin ein MD4 erstellt. In der DB werden Dateiname, MD4, Größe, Erstellungs- und letztes Änderungsdatum vermerkt. Wenn nun Dateiname, Pfad, Größe, Erstellungs- und letztes Änderungsdatum übereinstimmen, dann spare ich mir die erneute MD4-Berechnung und gehe von Identität aus. Da bei sehr großem Dateibestand der Prozentsatz der geänderten Dateien sehr klein ist, kann man sich so meist >99% der Arbeit sparen.

Retrospect ist natürlich toll, ich weiß aber nicht, ob ich so einen Dienst mitlaufen haben möchte. Insbesondere nicht, wenn ich Videobearbeitung mache.

Ich glaube, ich verfolge jetzt erstmal den Ansatz, die Verzeichnisse mit ID zu versehen und für den Gesamtnamen ein MD4 zu speichern, was mich einheitlich 32 Byte kosten würde.
Vielen Dank für eure Anregungen, und wenn jemand noch eine zündende Idee hat, immer her damit!

[Sir Rufo]

Zitat:

Zitat von Benmik (Beitrag 1251176)

Retrospect ist natürlich toll, ich weiß aber nicht, ob ich so einen Dienst mitlaufen haben möchte. Insbesondere nicht, wenn ich Videobearbeitung mache.

Und warum sollte das stören? :gruebel:

Klar kann man das so implementieren, dass es fürchterlich stört, aber auch so, dass es eben nicht störend wirkt.
Wenn die CPU sich langweilt, dann alles berechnen, was da ansteht, ansonsten vornehm zurückhalten und nicht bei jeder Änderung sofort die Berechnung anwerfen.

[Benmik]

Ist natürlich richtig, wenn die Jungs das so geschickt machen. Womit auch Persaus Frage beantwortet wäre, was ein Profi ist :wink: Mir jedenfalls stehen solche Möglichkeiten wie die Implementierung eines solchen Dienstes nicht zur Verfügung. Was auch für die blockweise Datensicherung gilt.

[Sir Rufo]

Zitat:

Zitat von Benmik (Beitrag 1251181)

Ist natürlich richtig, wenn die Jungs das so geschickt machen. Womit auch Persaus Frage beantwortet wäre, was ein Profi ist :wink: Mir jedenfalls stehen solche Möglichkeiten wie die Implementierung eines solchen Dienstes nicht zur Verfügung. Was auch für die blockweise Datensicherung gilt.

Nun ja, einer Eigenschaft einen Wert zuweisen, wirst du wohl schon schaffen TThread.Priority.

[hoika]

Hallo,

bei einer richtigen DB (z.B. Firebird) gibt es kein RAM-Problem.
Die Dateinamen / Indizes sind eh schon komprimiert.

Was willst du denn verwenden ?

Heiko

[Furtbichler]

Ich verstehe die ganze Problematik nicht. Ich habe eine Liste von eindeutigen Dateinamen. Wie die im Detail aussehen, ist doch zunächst vollkommen egal.

Nun möchte ich wissen, ob sich die Datei verändert hat, um sie ggf. neu zu sichern. Da bietet sich zunächst das Archivbit an (Größe und Änderungsdatum vielleicht noch). Ein Hash... ich weiß nicht, ob es sinnvoll ist, Bestrebungen des Anwenders zu umgehen, eine Datei zu ändern, ohne das Archivbit zu setzen. Soweit ich weiß, wird das bei jeder Änderung gesetzt. Weiterhin ist das eine sehr einfache Möglichkeit, Dateien vom Archivieren auszuschließen (einfach nicht setzen bzw. zurücksetzen).

Aber gut, auch zweitrangig, wie man Änderungen feststellt. Es geht ja hier um die Frage, wie man so eine Dateiliste in einer Datenbank ablegt. Natürlich ist hier auch entscheidend, was mit der Liste angestellt werden soll, d.h. die Speicherstrategie richtet sich nach den Retrievalanforderungen.
In den meisten Fällen wird eine einfache Liste, d.h. Tabelle, am schnellsten umzusetzen und für die meisten Use Cases geeignet sein.
Allerdings kann ich mir bei einem richtig guten Backupprogramm auch vorstellen, das es Umbenennungen von Verzeichnissen und Dateien mitbekommt und seine eigene Liste entsprechend überarbeitet. Wenn man das umsetzen will und (!) wirklich sehr viele Dateien hat(> 1Mio), dann wäre ein anderes Speichermodel vielleicht sinnvoll(naheliegend: Baum). Ansonsten ist die banale Liste wirklich keine Hürde. Die Suche (auch nach Verzeichnissen) kann immer einen Index verwenden, denn man vergleicht ja den Anfang (also ein "LIKE 'FOO%'"). Mal eben 1000 Dateien umzubenennen ist nun auch keine Hürde.
Um ehrlich zu sein, würde ich noch nicht einmal eine Datenbank nehmen. Die Rechnung sieht so aus:
Maximale Anzahl der Dateien, die supported werden: 1 Mio (Beispiel)
Maximale Länge eines Dateinamens : 255 Bytes.
Benötigter Speicher dafür: 256 MB.
Wo war jetzt gleich das Problem?

Benötigst Du allerdings 100 Mio Dateien, dann solltest Du dir eine DB anschaffen, das ist logisch.

Zitat:

Zitat von hoika (Beitrag 1251186)

Die Dateinamen / Indizes sind eh schon komprimiert.

Aber nur RLE, was hier überhaupt nichts bringt.

[Union]

Man kann auch problemlos einen Prozess sich selbst überwachen lassen, so dass er z.B. nie mehr als x Prozent der Systemleistung benutzt. So eine Speicherung von sehr vielen Dateinamen hatte ich vor 20 Jahren mal gemacht, als es wirklich noch auf jedes Byte ankam.
Damals wurden damit im Fidonet Dateibestaende verwaltet. Die Struktur war VolumeID, PathID, FileName. Das ging ziemlich gut.

[Benmik]

Zitat:

Zitat von Furtbichler (Beitrag 1251190)

Allerdings kann ich mir bei einem richtig guten Backupprogramm auch vorstellen, das es Umbenennungen von Verzeichnissen und Dateien mitbekommt und seine eigene Liste entsprechend überarbeitet.

Genau darum geht es mir! Ich möchte, dass in allen gesicherten Dateien jede einzelne Datei nur ein Mal vorkommt und Doubletten durch Hardlinks ersetzt werden.
Ich habe beide Varianten ausprobiert, Verzeichnisse mit ID in einer getrennten Tabelle und Speicherung des vollen Namens. Schon bei mir reichen da 256 Byte nicht aus, ein Echt-Beispiel aus der Praxis lautet "D:\Daten\Gemeinsam\Projekte\Video\Edius\Projektda teien\Tropenhaus\Echoes of Nature - Jungle Talk\Sounds Of Nature - Fresh Country Rain\Sounds Of Nature - Fresh Country Rain\Sounds Of Nature-Fresh Country Rain\Sounds Of Nature - 01 - Fresh Country Rain - (with music).mp32". Ich bn mir sicher, dass es da noch ganz andere Kaliber gibt. Man kann sich fragen, warum das eine Verzeichnis drei Mal auftaucht, aber es war eben so (da hatte ich wegen Resampeln rasch mal das Verzeichnis kopiert), und dann muss man auch bei anderen damit rechnen. Leider benötigte ich mehrere Indizes, nicht nur den Dateinamen, sondern auch noch für Größe und MD4, mit der Folge, dass Dateioperationen unglaublich langsam wurden.

Nochmal zum Entwurf: Alle Dateien sollen durch MD4 eindeutig identifizierbar sein, unabhängig von Name und Pfad. Diese Erstellung von MD4 ist das Zeitaufwendigste, daher wüsste ich nicht, wie das Speichern der vorhandenen Dateien mit MD4 ohne Datenbank gehen sollte. Bei bereits vorhandenen MD4-Prüfsummen kann die erneute Erstellung entfallen, dazu prüfe ich Pfad, Dateiname, Größe, Erstellungs- und Änderungsdatum und übernehmen dann die MD4 aus der DB.

Gehört jetzt vielleicht nicht mehr zum Thema, aber die 32 Byte von MD4 oder MD5 sind mir für läppische Dateinamen ein bisschen viel. Welche Prüfsumme hat denn 16 Byte? Oder kann ich einfach die ersten 16 von MD4 nehmen, wie hoch ist da die Wahrscheinlichkeit von Kollisionen? Ich würde ja gern CRC64 von Wolfgang Ehrhardt nehmen, aber leider weiß ich nicht, wie ich den Datentyp

Delphi-Quellcode:

type
  TCRC64 = packed record
    lo32, hi32: longint;
  end;

in einen HexString umwandeln kann. In den mem_utils finde ich nichts, das passt.

[hstreicher]

also ,
du wandelst lo32 und hi32 jeweils separat in eine Hexstring und haengst dann die 2 Strings aneinander

lo32hx:=hexstring(lo32);
hi32hx:=hexstring(hi32);
crc64hx:=hi32hx+lo32hx;

oder verstehe ich das jetzt vollkommen falsch ?

[Benmik]

Klappt! Danke.

[jfheins]

Du könntest die ganze Geschichte auch in den Alternate Data Streams unterbringen.

Also jeder Datei einen dolchen verpassen, in dem dann der Hash drinsteht, zusammen mit dem Erzeugungsdatum des Hashs. Wenn du dann das Verzeichnis mit dem Backup vergleichst, greifst du wieder darauf zu und vergleichst für jede Datei 1. Ob der Hash noch aktuell ist, ggf. neu erzeugen und 2. Ob er überein stimmt.

Das geht natürlich nur für NTFS. Sicherungen auf ein Netzlaufwerk werden damit schwierig. Aber da du eh schon von Hardlinks sprachst, erfolgt das Backup ja eh von NTFS nach NTFS, oder?

[Benmik]

Völlig richtig, da Hardlinks eine große Rolle spielen sollen, ist NTSF Voraussetzung. ADS ist natürlich ein ganz neuer, interessanter Gedanke, umso mehr, da sich in meiner Sammlung von Delphi-Routinen auch die zum Auslesen und Schreiben von ADS finden. Ich müsste mal grübeln, ob das sicher genug ist. Eine Datenbank ist ein gesicherter Raum, während die Dateien mit den ADS ja "in freier Wildbahn" verbleiben und dort alle möglichen Programm alles Mögliche mit ihnen anstellen können. Ich habe auch noch nie gehört, dass ADS für Sicherungszwecke verwendet werden, das wird doch wohl seinen Grund haben? Aber bestechend ist der Gedanke schon!

PS: Da hast du mir einen Floh ins Ohr gesetzt! Das Setzen und Wiederauslesen der ADS ist kinderleicht! Ein gewisser Nachteil: Anscheinend sind (jedenfalls unter Windows 7) Administratorrechte erforderlich.