☰

'cd'-Komplexität auf ext4

tag-icon • tag-icon performance ext4 file-search tree
'cd'-Komplexität auf ext4

Um Anhänge zu speichern, /path/to/atts/werden in einem Verzeichnis zahlreiche Unterverzeichnisse (Produkt-IDs) erstellt (von 1 bis ~10.000 oder zukünftig möglicherweise mehr), und in jedem dieser Unterverzeichnisse werden 1 bis ~10 Anhangsdateien erstellt.

In/path/to/atts/

  1
  ├── file1.1
  ├── file1.2
  └── file1.3
  2
  └── file2.1
  ...
10000
  ├── file10000.1
  ├── file10000.2
  ├── file10000.3
  ├── file10000.4
  └── file10000.5

(eigentlich wurde 1 .. 10000 gewählt, um die Erklärung zu vereinfachen – die IDs sind int32-Zahlen)

cdIch frage mich, wie hoch die Komplexität (der tatsächlichen Pfadauflösung) im ext4-Dateisystem ist , wenn /path/to/atts/54321/...beispielsweise Folgendes erreicht wird:

  • Überprüft die Pfadauflösung alle Inodes/Namen einzeln im attsVerzeichnis, bis 54321erreicht ist? Das bedeutet, dass im Durchschnitt n/2 Inodes überprüft werden (O(n))

  • Oder gibt es innerhalb eines Verzeichnisses eine Baumstruktur, die die Suche einschränkt (z. B. ein Trie-Baum, alphabetische Reihenfolge …), die die Anzahl der überprüften Inodes drastisch reduzieren würde, etwa log(n) statt n/2?

Wenn Ersteres zutrifft, werde ich die Art und Weise ändern, wie die Produktbaumstruktur implementiert wird.

Nur um das klarzustellen: Die Frage betrifft nicht die findSuche nach einer Datei in einem Dateisystembaum (das ist O(n)). Es handelt sich eigentlich um eine Pfadauflösung (durchgeführt vom FS), die ein Verzeichnis durchquert, in dem sich Tausende von Dateinamen befinden (die Produkt-IDs)..

Antwort1

Sie können über den Hash-Tree-Index lesen, der für Verzeichnisse verwendet wirdHier.

Eine lineare Anordnung von Verzeichniseinträgen ist nicht leistungsfördernd, daher wurde ext3 eine neue Funktion hinzugefügt, um einen schnelleren (aber besonderen) ausgeglichenen Baum bereitzustellen, der auf einem Hash des Verzeichniseintragsnamens basiert.

verwandte Informationen