1. Foren
  2. Kommentare
  3. OpenSource
  4. Alle Kommentare zum Artikel
  5. › Meego: Mobiles Linux verwendet…

Warum ist Verzeichnisstruktur so lahm?

Expertentalk zu DDR5-Arbeitsspeicher am 7.7.2020 Am 7. Juli 2020 von 15:30 bis 17:00 Uhr wird Hardware-Redakteur Marc Sauter eure Fragen zu DDR5 beantworten.
  1. Thema

Neues Thema Ansicht wechseln


  1. Warum ist Verzeichnisstruktur so lahm?

    Autor: Datenbank 13.05.10 - 18:58

    Warum ist bei allen (mir bekannten) Dateisystemen das Suchen nach Dateien so langsam?

    z.B. Suche nach *.doc auf dem gesamten Datenträger dauert immer ewig.

    Warum geht das nicht in unter 1 Sekunde, kann doch nicht so schwer sein, das Dateiverzeichnis wie eine DB aufzubauen und Abfragen wären flott möglich, z.B.

    SELECT filename, filedate FROM C: WHERE filename LIKE "*.doc" AND filesize>1000

    Sollte in unter 1 Sekunde ALLE TREFFER auflisten...

    Das meine ich NATIV ohne irgendwelche Indizierungsdienste...

  2. Re: Warum ist Verzeichnisstruktur so lahm?

    Autor: Wahrheitssager 13.05.10 - 19:18

    Siehe BFS (BeOS Filesystem , gerade auch in der neuen Fassung von Haiku als OpenBFS) .
    Das hat die Funktionalität die du willst.

  3. Re: Warum ist Verzeichnisstruktur so lahm?

    Autor: Ferrum 13.05.10 - 21:07

    Datenbank schrieb:
    --------------------------------------------------------------------------------
    > Warum ist bei allen (mir bekannten) Dateisystemen das Suchen nach Dateien
    > so langsam?
    >
    > z.B. Suche nach *.doc auf dem gesamten Datenträger dauert immer ewig.

    Ich verstehe nicht viel von Dateisystemen, aber die Antwort auf diese Frage würde mich auch interessieren. Immerhin sind selbst bei FAT-Dateisystemen alle Verzeichniseinträge innerhalb einer kompakten Tabelle des Stammverzeichnisses gespeichert. Eine einfache Suche innerhalb dieser Tabelle kann bei mehreren hunderttausend Einträgen schon einmal mehrere Minuten dauern, was ein normaler Texteditor innerhalb weniger Sekunden oder sogar Sekundenbruchteilen erledigt.

    Vielleicht kann es jemand erläutern, der mehr Ahnung von der Materie hat. Wäre interessant.



    2 mal bearbeitet, zuletzt am 13.05.10 21:11 durch Ferrum.

  4. Re: Warum ist Verzeichnisstruktur so lahm?

    Autor: tsu 13.05.10 - 21:30

    1. Sind Plattenzugriffe viel viel teurer als Speicherzugriffe
    2. ist das eine Frage der Aufbereitung, z.B. lassen sich sortierte Datensätze schneller finden als unsortierte
    3. ist im Dateisystem mehr "Bewegung" innerhalb des Datenbestandes möglich

  5. Re: Warum ist Verzeichnisstruktur so lahm?

    Autor: Ferrum 13.05.10 - 23:21

    tsu schrieb:
    --------------------------------------------------------------------------------
    > 1. Sind Plattenzugriffe viel viel teurer als Speicherzugriffe
    Schon klar. Aber wenn die Tabelle mit den Verzeichniseinträgen am Stück eingelesen und durchsucht wird, hätte man dann im Prinzip nicht nur einen einzigen Festplattenzugriff darauf? Inwiefern soll sich das dann auf die Suchdauer niederschlagen?

    > 2. ist das eine Frage der Aufbereitung, z.B. lassen sich sortierte
    > Datensätze schneller finden als unsortierte

    Das gilt vielleicht für Menschen. Aber ein Rechner durchsucht doch ohnehin alle zur Verfügung stehenden Einträge auf einen Treffer der Suchmaske. Also inwiefern würde eine Sortierung die Suche dann beschleunigen?

    > 3. ist im Dateisystem mehr "Bewegung" innerhalb des Datenbestandes möglich

    Inwiefern soll eine Bestandsänderung die Suchdauer beeinflussen? Wenn der Bestand geändert wird, aktualisiert sich die Dateizuordnungstabelle und gut ist. Letztlich muss doch nur diese Tabelle durchsucht werden und nicht die ganze Platte nach einzelnen Dateien.



    1 mal bearbeitet, zuletzt am 13.05.10 23:24 durch Ferrum.

  6. Re: Warum ist Verzeichnisstruktur so lahm?

    Autor: schmofarz 13.05.10 - 23:58

    Ferrum schrieb:
    --------------------------------------------------------------------------------
    > tsu schrieb:

    > > 2. ist das eine Frage der Aufbereitung, z.B. lassen sich sortierte
    > > Datensätze schneller finden als unsortierte
    >
    > Das gilt vielleicht für Menschen. Aber ein Rechner durchsucht doch ohnehin
    > alle zur Verfügung stehenden Einträge auf einen Treffer der Suchmaske. Also
    > inwiefern würde eine Sortierung die Suche dann beschleunigen?

    Die Sortierung ist bei sämtlichen Datenbanken die grundlegende Eigenschaft für effizientes Suchen (völlig unabhängig von der verwendeten Hardware, im Vergleich natuerlich immer auf derselben, d.h. entweder Ram oder Platte). Hast Du N Datensätze, findest Du einen Datensatz bei Nichtsortierung sequentiell in maximal N schritten, bei Sortierung in log( N ) / log ( 2) (also ld(N)) Schritten, ein Beispiel: 1*10 hoch 6 Datensäze

    ohne Sortierung: 1*10 hoch 6 Verarbeitungsschritte
    mit Sortierung: ld( 1*10 hoch 6)= 20 Verarbeitungsschritte
    d.h. 50000 mal schneller

    umso mehr Datensätze Du hast, desto mehr wirkt sich die Sortierung aus


    > > 3. ist im Dateisystem mehr "Bewegung" innerhalb des Datenbestandes
    > möglich
    >
    > Inwiefern soll eine Bestandsänderung die Suchdauer beeinflussen? Wenn der
    > Bestand geändert wird, aktualisiert sich die Dateizuordnungstabelle und gut
    > ist. Letztlich muss doch nur diese Tabelle durchsucht werden und nicht die
    > ganze Platte nach einzelnen Dateien.

    Daß mehr Bewegung möglich ist, stimmt so nicht, wenn der Datenbestand auf bestimmte Suchanfragen hin indexiert ist, müssen bei jeder Bewegung die Indexe mitgeführt werden.

    Gruß

  7. Re: Warum ist Verzeichnisstruktur so lahm?

    Autor: schmofarzkiller 14.05.10 - 09:18

    Auf ein neues:

    schmofarz schrieb:
    --------------------------------------------------------------------------------
    > Die Sortierung ist bei sämtlichen Datenbanken die grundlegende Eigenschaft

    Hier geht es um ein Dateisystem und nicht um eine Datenbank!

    > Daß mehr Bewegung möglich ist, stimmt so nicht, wenn der Datenbestand auf
    > bestimmte Suchanfragen hin indexiert ist, müssen bei jeder Bewegung die
    > Indexe mitgeführt werden.

    In der Ausgangsfrage ging es explizit um eine Suche ohne Indexierung!

  8. Re: Warum ist Verzeichnisstruktur so lahm?

    Autor: Der braune Lurch 14.05.10 - 12:54

    > Hier geht es um ein Dateisystem und nicht um eine Datenbank!

    Ach. Und wo sollen die Datei- und Verzeichniseinträge mit all ihren Informationen gespeichert werden? Eventuell in einer Datenbank?

    ------------------------------
    Der Molch macht's.
    ------------------------------

  9. Re: Warum ist Verzeichnisstruktur so lahm?

    Autor: Der braune... 14.05.10 - 14:05

    Der braune Lurch schrieb:
    --------------------------------------------------------------------------------
    > > Hier geht es um ein Dateisystem und nicht um eine Datenbank!
    >
    > Ach. Und wo sollen die Datei- und Verzeichniseinträge mit all ihren
    > Informationen gespeichert werden? Eventuell in einer Datenbank?

    Ach. Und was hat das mit der Ausgangsfrage zu tun? Eventuell gar nichts?

  10. nicht am Anfang der Platte und nicht...

    Autor: 7bit 14.05.10 - 11:26

    Ferrum schrieb:
    > Immerhin sind selbst bei FAT-Dateisystemen
    > alle Verzeichniseinträge innerhalb einer kompakten Tabelle des
    > Stammverzeichnisses gespeichert.

    Du verwechselst da was: Diese Tabelle die Du da meinst (und die dem FAT auch seinen Namen gibt) ist die File Allocation Table, die verwaltet aber nur (quasi eine Schicht tiefer) welche Cluster frei oder belegt sind und für belegte Cluster welcher Cluster jeweils der nächste in einer Datei ist (die Reihenfolge in der sie zusammengefügt eine Datei ergeben). Diese Tabelle hat eine feste Größe weil es ja nur eine fixe Anzahl an Clustern gibt, sie ändert nie ihre Größe, daher kann man sie an einem Stück irgendwo am Anfang der Partition ablegen.

    Die Verzeichnisse jedoch mit den Dateinamen und den zugehörigen Angaben wie Attribute, Größe, Nummer des ersten Clusters sind kreuz und quer über die ganze Platte verteilt. Jeder "Ordner" hat sein eigenes Verzeichnis, manchmal ist selbst für einen Ordner das Verzeichnis in mehrere Teile aufgeteilt wenn die Platte übel fragmentiert ist.

    Ich kann mich erinnern zu FAT Zeiten noch eins dieser Defragmentierprogramme (von norton) benutzt zu haben und da gabs eine Option die Verzeichnisse aufzuräumen und jeweils wieder in einem Stück an den Anfang zu verlegen und das hat bewirkt dass Dateisuchen nicht mehr ganz so übel auf der Platte gerödelt hat (damals waren die Platten noch *laut*) und auch beim booten gings dann etwas ruhiger zu.



    2 mal bearbeitet, zuletzt am 14.05.10 11:29 durch 7bit.

  11. Re: nicht am Anfang der Platte und...

    Autor: Ferrum 14.05.10 - 11:39

    7bit schrieb:
    --------------------------------------------------------------------------------
    > Die Verzeichnisse jedoch mit den Dateinamen und den zugehörigen Angaben wie
    > Attribute, Größe, Nummer des ersten Clusters sind kreuz und quer über die
    > ganze Platte verteilt.

    Ach herrje. Was für ein Chaos. Wenn für eine banale Suche erstmal die komplette Festplatte nach allen Dateieinträgen durchsucht wird und dafür alle Ordner einzeln angesprungen werden müssen, erklärt das natürlich einiges. Danke dir.

  12. Re: Warum ist Verzeichnisstruktur so lahm?

    Autor: Everything 13.05.10 - 22:57

    Dafür benutze ich unter Windows "Everything search engine": http://www.voidtools.com/

    Datenbank schrieb:
    --------------------------------------------------------------------------------
    > Warum ist bei allen (mir bekannten) Dateisystemen das Suchen nach Dateien
    > so langsam?
    >
    > z.B. Suche nach *.doc auf dem gesamten Datenträger dauert immer ewig.
    >
    > Warum geht das nicht in unter 1 Sekunde, kann doch nicht so schwer sein,
    > das Dateiverzeichnis wie eine DB aufzubauen und Abfragen wären flott
    > möglich, z.B.
    >
    > SELECT filename, filedate FROM C: WHERE filename LIKE "*.doc" AND
    > filesize>1000
    >
    > Sollte in unter 1 Sekunde ALLE TREFFER auflisten...
    >
    > Das meine ich NATIV ohne irgendwelche Indizierungsdienste...

  13. Re: Warum ist Verzeichnisstruktur so lahm?

    Autor: Auch Everything 14.05.10 - 10:12

    Everything schrieb:
    --------------------------------------------------------------------------------
    > Dafür benutze ich unter Windows "Everything search engine":
    > www.voidtools.com

    Genau das nutze ich auch, superschnell und erfüllt genau die
    Ansprüche, die der Thread-Starter fordert !

    Also, einfach mal ausprobieren statt hier rum zu diskutieren !

  14. Re: Warum ist Verzeichnisstruktur so lahm?

    Autor: Auch... 14.05.10 - 10:39

    Der heilige Troll-Freitag ist scheinbar schon voll im Gange.

    Auch Everything schrieb:
    --------------------------------------------------------------------------------
    > Genau das nutze ich auch, superschnell und erfüllt genau die
    > Ansprüche, die der Thread-Starter fordert !

    Der Thread-Starter fordert keine Ansprüche, sondern eine Erklärung auf eine Frage, zu der du offenbar genauso wenig in der Lage bist.

    > Also, einfach mal ausprobieren statt hier rum zu diskutieren !

    Als ob sich davon die Frage beantworten würde.

    Auch für dich daher: Wenn du keine Ahnung hast, dann troll dich!

  15. Re: Warum ist Verzeichnisstruktur so lahm?

    Autor: dbadmin 14.05.10 - 07:59

    es ist nur dann langsam, wenn deine Platte nicht indiziert ist. indexe zu erstellen kostet aber zeit und speicher. stichwort "Laufwerk für schnelle Dateisuche indizieren" ich hatte irgendwo mal nen artikel zur hand, der auf die indizierung unter xp im detail eingegangen ist, ich glaub es war in der ct.
    schau mal nach bei systemsteuerung - verwaltung - computerverwaltung - dienste und anwendungen - indexdenst

  16. Re: Warum ist Verzeichnisstruktur so lahm?

    Autor: dbadminkiller 14.05.10 - 08:26

    *********************************

    1. ging es in der Frage explizit um eine Suche ohne Indexierung.
    2. ist eine Indexierung vor allem für eine Suche von Inhalten innerhalb von Dateien sinnvoll.
    3. ist deine Begründung, dass die Suche nur aufgrund einer fehlenden Indexierung langsam ist, absoluter Schwachsinn. Die Gründe liegen woanders und dass es auch ohne Indexierung schneller gehen kann sieht man an anderen Dateisystemen.
    4. Heißt es Indexierung. Eine Indizierung ist was vollkommen anderes.

    Lies Wikipedia wenn du keine Ahnung hast und troll dich!



    1 mal bearbeitet, zuletzt am 14.05.10 09:11 durch ap (Golem.de).

  17. Re: Warum ist Verzeichnisstruktur so lahm?

    Autor: Der braune Lurch 14.05.10 - 12:59

    > 4. Heißt es Indexierung. Eine Indizierung ist was vollkommen anderes.

    Nein. Wenn man von Indizierung spricht (womit meist ein Verbot der Bewerbung von Medien gemeint ist), sagt man das so, weil dieses Medien auf den Index kommt. Genauso kommen bei einer Indizierung bei einer Partition bestimmte Informationen über Dateien/Ordner in einen Index. Indizierung ist korrekt.

    ------------------------------
    Der Molch macht's.
    ------------------------------

  18. Re: Warum ist Verzeichnisstruktur so lahm?

    Autor: Der braune... 14.05.10 - 14:13

    Der braune Lurch schrieb:
    --------------------------------------------------------------------------------
    > > 4. Heißt es Indexierung. Eine Indizierung ist was vollkommen anderes.
    >
    > Nein. Wenn man von Indizierung spricht (womit meist ein Verbot der
    > Bewerbung von Medien gemeint ist), sagt man das so, weil dieses Medien auf
    > den Index kommt. Genauso kommen bei einer Indizierung bei einer Partition
    > bestimmte Informationen über Dateien/Ordner in einen Index. Indizierung ist
    > korrekt.

    Irrtum. Zitat aus dem Wikipedia-Artikel zur Indizierung:

    „... Indizierung bezeichnet im Allgemeinen die Aufnahme in einen Index. Speziell wird darunter vor allem die Aufnahme in ein Verzeichnis verbotener Werke verstanden.
    ...
    Bei der Erstellung eines Registers und beim Information Retrieval wird neuerdings in Anlehnung an das englische indexing die Bezeichnung Indexierung statt Indizierung verwendet.
    ...“

  19. Re: Warum ist Verzeichnisstruktur so lahm?

    Autor: Der grüne Frosch 14.05.10 - 15:58

    Das hättest du dir auch leicht selber herleiten können.
    Ein Index ist ein lexi. sortiertes Stichwortverzeichnis.

    Etwas kommt nicht auf dem Index sondern in den Index.
    Und diese Artikel sind nicht verboten, sondern nur beschränkt im Handel. Der Import kann legal sein, muss aber nicht. Bei einigen Artikel reicht der Besitz schon aus um ein Verfahren am Hals zu haben.

  20. Re: Warum ist Verzeichnisstruktur so lahm?

    Autor: Der grüne Frosch 14.05.10 - 16:07

    Wobei wir noch zwischen Bückware(keine Werbung) und ein Stufe höher(srafrechtlich relevant, beschlagnahmt, kein Verkauf) unterscheiden.

  21. Re: Warum ist Verzeichnisstruktur so lahm?

    Autor: Indexpopper 14.05.10 - 16:11

    Der grüne Frosch schrieb:
    --------------------------------------------------------------------------------
    > Etwas kommt nicht auf dem Index sondern in den Index.

    Wer sagt dir dass man auf dem Index nicht kommen kann? hrhrhr

  22. Lahm ist nur Windows

    Autor: egal0815 14.05.10 - 09:17

    > Warum ist bei allen (mir bekannten) Dateisystemen das Suchen
    > nach Dateien so langsam?

    Das hängt davon ab, wie das Dateiverzeichnis verwaltet wird. Ich benutze in Linux updatedb, um das Dateiverzeichnis aktuell zu halten. Mit locate finde ich dann jede Datei innerhalb von 3 Sekunden, auch bei 1 Mio Dateien. Ohne updatedb würde es Minuten dauern, um eine Datei zu finden.

    Bei Windows ist die Suche mit dem Explorer ein Relikt aus der Steinzeit. Kennt Windows überhaupt sowas wie updatedb?

  23. Re: Lahm ist nur Windows

    Autor: egal0815killer 14.05.10 - 09:29

    Sagt mal, könnt ihr eigentlich alle nicht Lesen?

    egal0815 schrieb:
    --------------------------------------------------------------------------------
    > > Warum ist bei allen (mir bekannten) Dateisystemen das Suchen
    > > nach Dateien so langsam?
    >
    > Das hängt davon ab, wie das Dateiverzeichnis verwaltet wird.

    Erstklassige Antwort. Sehr ausführlich und informativ. Echt super!

    > Ich benutze [blablabla]...

    Es interessiert hier keinen, was du benutzt. Zumindest beantwortet das nicht die Frage.

    > ... in Linux updatedb, um das Dateiverzeichnis aktuell zu halten.

    In der Frage ging es explizit um eine Suche ohne Indexierungsdienst.

    > Ohne updatedb würde es Minuten dauern, um eine Datei zu finden.

    Erstklassige Feststellung. Hat sogar der Fragesteller schon herausgefunden. Doch die Frage nach dem „Warum“ hast du natürlich nicht beantwortet.

    Auch für dich daher: Wenn du keine Ahnung hast, dann lies Wikipedia und troll dich!

  24. Re: Warum ist Verzeichnisstruktur so lahm?

    Autor: no way, jose 14.05.10 - 13:34

    Die Verzeichnisstruktur ist bei den meisten Dateisystemen nicht zusammenhängend in einem großen Block, sondern über die Platte verteilt. Bei einer Suche schubbert der Schreib-Lesekopf also ziemlich wild über die Scheibe(n) hin und her, und liest die Verzeichnisblöcke ein. Diese Seek-Zeiten dürften die meiste Zeit ausmachen.

  25. Re: Warum ist Verzeichnisstruktur so lahm?

    Autor: Robert Bauer 15.05.10 - 11:17

    Datenbank schrieb:
    --------------------------------------------------------------------------------
    > Warum ist bei allen (mir bekannten) Dateisystemen das Suchen nach Dateien
    > so langsam?
    >
    > z.B. Suche nach *.doc auf dem gesamten Datenträger dauert immer ewig.

    Das kann ich genau erklären da ich selber schon mal ein natives Dateisystem für Linux programmiert habe.
    Ein Dateisystem unter Linux sowie auch unter Windows wird an einem virtuellen Dateisystem angehängt. Unter UNIX Systemen nennt sich das VFS. Alle Programme wie z.B. find oder unter Windows Explorer verwenden eine vorgegebene API vom Betriebssystem um Dateien zu finden. In dieser API gibt es keine Möglichkeit mal einfach einen Sonderbefehl auszuführen wie z.B. in SQL ein SELECT. Die API ist vom Betriebssystemhersteller vorgegeben. In UNIX ist es der POSIX Standard.
    Der Standard gibt vor das man nur Verzeichnisse öffnen kann und sich eine Liste vom Verzeichnis ausgeben kann (Systemaufruf opendir und readdir unter Unix).

    Wenn man jetzt ein Datenbankdateisystem bauen würde und man wolle ein SELECT einfach mal so ausführen wie du es beschrieben hast, dann müsste man im Dateisystem eine Sonderschnittstelle einbauen über die Programme solche Abfragen machen könnten. Dafür müsste man unter Linux die GNU Software Foundation bitten Ihr "find" Programm zu patchen nur damit es mit diesem einzigen Dateisystem anders nach Dateien sucht als mit dem Rest. Besser wäre es dann den POSIX Standard für so etwas zu erweitern. Das ist aber sehr aufwendig und kompliziert weil dieser schon seit 30 Jahren ausgereift ist. Die einfachere Variante wäre also die Programme wie "find" und Frontendtools in KDE und Gnome für das Dateisystem zu patchen.

  1. Thema

Neues Thema Ansicht wechseln


Um zu kommentieren, loggen Sie sich bitte ein oder registrieren Sie sich. Sie müssen ausserdem in Ihrem Account-Profil unter Forum einen Nutzernamen vergeben haben. Zum Login

Stellenmarkt
  1. hl-studios GmbH, Erlangen
  2. AKKA, Ingolstadt
  3. Präsidium der Bay. Bereitschaftspolizei, München
  4. Technische Universität Berlin, Berlin

Golem pur
  • Golem.de ohne Werbung nutzen

Anzeige
Spiele-Angebote
  1. (-91%) 2,20€
  2. (u. a. Warhammer 40,00€0: Gladius - Relics of War für 23,79€, Aggressors: Ancient Rome für 17...
  3. 58,48€ (PC), 68,23€ (PS4) 69,99€ (Xbox One)


Haben wir etwas übersehen?

E-Mail an news@golem.de


Echo Auto im Test: Tolle Sprachsteuerung und neue Alexa-Funktionen
Echo Auto im Test
Tolle Sprachsteuerung und neue Alexa-Funktionen

Im Auto ist die Alexa-Sprachsteuerung noch praktischer als daheim. Amazon hat bei Echo Auto die wichtigsten Einsatzzwecke im Fahrzeug bedacht.
Ein Test von Ingo Pakalski

  1. Echo Auto Amazon bringt Alexa für 60 Euro ins Auto
  2. Echo Flex mit zwei Modulen im Test Gut gedacht, mäßig gemacht
  3. Amazon Zahlreiche Echo-Modelle nicht mehr bis Weihnachten lieferbar

Kotlin, Docker, Kubernetes: Weitere Online-Workshops für ITler
Kotlin, Docker, Kubernetes
Weitere Online-Workshops für ITler

Wer sich praktisch weiterbilden will, sollte erneut einen Blick auf das Angebot der Golem Akademie werfen. Online-Workshops zu den Themen Kotlin und Docker sind hinzugekommen, Kubernetes und Python werden wiederholt.

  1. React, Data Science, Agilität Neue Workshops der Golem Akademie online
  2. In eigener Sache Golem Akademie hilft beim Einstieg in Kubernetes
  3. Golem Akademie Data Science mit Python für Entwickler und Analysten

Außerirdische Intelligenz: Warum haben wir noch keine Aliens gefunden?
Außerirdische Intelligenz
Warum haben wir noch keine Aliens gefunden?

Seit Jahrzehnten gucken wir mit Teleskopen tief ins All. Außerirdische haben wir zwar bisher nicht entdeckt, das ist aber kein Grund, an ihrer Existenz zu zweifeln.
Von Miroslav Stimac