Warum können wir ohne die zusätzlichen Schreibvorgänge nicht in Dateien einfügen? (Ich meine weder anhängen noch überschreiben)

8

Dies tritt für mich als programmiersprachenunabhängiges Problem auf.

Ich habe eine Datei mit dem Inhalt

aaabddd

Wenn ich einfügen wollen Chinter bdann meinen Code Bedürfnisse neu zu schreiben dddzu bekommen

aaabCddd

Warum kann ich nicht einfach Can dieser Stelle einfügen ?

Ich kann das nicht in Java, Python, .... Ich kann das nicht unter Linux, Windows, .... Habe ich recht?

Ich verstehe nicht, warum Cnicht einfach ohne die zusätzlichen Schreibvorgänge eingefügt werden kann. Würde jemand bitte erklären, warum das so ist?

Benutzer
quelle
2
Überlegen Sie, was mit den Bits auf der Festplatte passiert, wenn Sie etwas in Byte 128 einer 2-Gigabyte-Datei einfügen möchten.
Du meinst ohne Betriebssystem und ohne Dateisystem dazwischen? Dann wird es nicht funktionieren. Mit den anderen beiden habe ich keine Ahnung, warum es nicht funktionieren kann.
Benutzer
12
Nimm 500 Dominosteine ​​und lege sie Ende an Ende in eine Reihe. Versuchen Sie nun, eine in diese Zeile einzufügen, ohne die anderen zu verschieben.
Großmeister
2
@MichaelT In meiner Traumwelt sollten Sie nur einen weiteren Block in die Blockfolge einfügen müssen, aus der die Datei besteht, und den Inhalt des aktuellen ersten Blocks auf die ersten beiden Blöcke verteilen. Zugegeben, würde dies die Dateisystem - Implementierer erfordern ungerade große Blöcke zu handhaben - aber in den Situationen , in denen Sie haben diese Operation benötigen, würde es die Effizienz verbessern , so viel ist es auch nicht lustig.
Kilian Foth
1
@Benutzen Sie die Fragen der Dateisystemfragmentierung und der Funktionsweise von Ext4 und rücken Sie fest in den Bereich von SuperUser. Bitte denken Sie daran, vollständig Ihr Problem geben oder sie werden wieder zu Bytes fragen. Sie fragen nach Blöcken und Dateisystemen und logischen Volume-Managern und dergleichen.

Antworten:

8

Angesichts der Tatsache, dass die meisten Dateisysteme den Inhalt von Dateien in einzelnen Blöcken speichern, die nicht unbedingt auf der physischen Festplatte zusammenhängend sind, sondern über Zeigerstrukturen verknüpft sind, sollte ein solcher Modus - "Einfügen" statt "Anhängen" oder "Überschreiben" - verwendet werden möglich zu sein und sicherlich effizienter zu machen als das, was wir jetzt tun müssen: den gesamten Inhalt lesen, den Bytestrom bearbeiten und den gesamten Inhalt neu schreiben.

Ob gut oder schlecht, die UNIX-Semantik von Dateisystemen wurde in den 1970er Jahren nach dem "groben und einfachen" Paradigma entwickelt: Sie ermöglicht es Ihnen, alles zu tun, aber nicht unbedingt auf die effizienteste Art und Weise. Heutzutage ist es fast undenkbar, einen neuen Modus zum Öffnen von Dateien in die Ebene des virtuellen Dateisystems einzuführen, und hoffen, dass die wichtigsten Dateisysteme diese unterstützen. Dies ist ein kleiner Ärger von mir, aber leider ist es unwahrscheinlich, dass er bald behoben wird.

Kilian Foth
quelle
2
Gebäude, das für eine Weile ein interessantes Nebenprojekt sein könnte ...
FrustratedWithFormsDesigner
1
Die Speicherung auf Blockebene erschwert die Frage noch einen Schritt weiter. In Anlehnung an das ursprüngliche Beispiel des OP sollten die beiden Versionen der Zeichenfolge in einen einzelnen Block passen. Die Bytes müssen nacheinander ausgeschrieben werden, und dies erfordert, dass der Schwanz des Strings um den jeweils eingefügten Betrag nach unten verschoben wird.
Es wäre nur effizient, wenn Sie genau die Datenmenge einfügen müssten, die in einem Block gespeichert werden kann, genau an der Grenze zwischen zwei vorhandenen Blöcken.
Idan Arye
Kilian Forth scheint richtig zu sein. Ich habe einen Professor danach gefragt und er hat mir dasselbe erzählt: Das "grobe und einfache" Design ermöglicht Portabilität und wird daher häufiger verwendet. Nicht viele Dateisysteme erlauben das Einfügen, und noch weniger Betriebssysteme machen es verfügbar, um es auf eine tragbare Schnittstelle anzuwenden. @ GlenH7 Zwei Leute, die meine Frage bearbeitet haben, haben es so aussehen lassen, als würde ich nach Bytes fragen und meine Klarstellung rückgängig machen. Die eigentliche Frage betrifft die von uns verwendete Schnittstelle.
Benutzer
Ja, die Blöcke sind über Zeiger verknüpft, sodass der Dateiinhalt nicht zusammenhängend gespeichert werden muss. Wenn sie jedoch zusammenhängend gespeichert werden, kann die Hardware Block für Block lesen, ohne dass sie langsamer werden muss. Wenn es Zeiger für Zeiger folgen müsste, würde sich der Lesekopf ständig bewegen. Aus diesem Grund beschleunigt die Defragmentierung Ihren Computer. Es setzt die Blockzeiger für Dateien in zusammenhängende Blöcke. Dann lautet der Befehl nicht Block 1 lesen, Block 3 lesen, Block 9 lesen, Block n lesen ... er wird zu Leseblöcken 1 bis n. Die Hardware kann das viel, viel effizienter.
Dunk
12

Theoretisch könnten Sie eine Datei implementieren, die dies zulässt. Für maximale Flexibilität müssen Sie jedoch zusammen mit jedem Byte in der Datei einen Zeiger auf das nächste Byte speichern. Unter der Annahme eines 64-Bit-Zeigers würde dies bedeuten, dass 8 von 9 Bytes Ihrer Datei aus internen Zeigern bestehen. Das Speichern von 1000 Byte tatsächlicher Daten würde also 9000 Byte Speicherplatz erfordern. Das Lesen der Datei wäre auch langsam, da Sie jedes Byte lesen, den Zeiger lesen, dem Zeiger folgen müssen, um das nächste Byte zu lesen usw., anstatt große, zusammenhängende Datenblöcke von der Festplatte zu lesen.

Offensichtlich ist diese Art von Ansatz nicht praktikabel. Sie können die Datei jedoch in 32-KB-Blöcke aufteilen. Dies würde es relativ einfach machen, 32 KB Daten an einer beliebigen 32 KB-Grenze in der Datei hinzuzufügen. Es würde es nicht einfacher machen, ein einzelnes Byte als 5. Byte der Datei hinzuzufügen. Wenn Sie jedoch in jedem Block freien Speicherplatz reservieren, können Sie kleine Datenzusätze zulassen, die sich nur auf die Daten in diesem einzelnen Block auswirken. Sie hätten natürlich eine Strafe in Bezug auf die Dateigröße, aber möglicherweise eine vernünftige. Das Herausfinden, wie viel Speicherplatz reserviert und wie Blöcke aufgeteilt werden müssen, ist für eine bestimmte Anwendung in der Regel viel einfacher als für ein Allzwecksystem. Was in einem Kontext funktioniert, kann in einem anderen Kontext je nach Dateizugriff und sehr schlecht sein Modifikationseigenschaften.

Tatsächlich implementieren viele Systeme, die viel Zeit mit der Interaktion mit Dateien verbringen, etwas wie das, was ich oben beschrieben habe, wenn sie ihre bestimmte Dateiabstraktion implementieren. Beispielsweise implementieren Datenbanken im Allgemeinen ein Konzept eines "Blocks" als kleinste E / A-Einheit, mit der sie arbeiten können, und reservieren im Allgemeinen etwas Speicherplatz für zukünftiges Wachstum, sodass die Aktualisierung einer Zeile in einer Tabelle nur die Ein Block, in dem diese Daten gespeichert werden, anstatt die gesamte Datei neu zu schreiben. Unterschiedliche Datenbanken haben natürlich unterschiedliche Implementierungen mit unterschiedlichen Kompromissen.

Justin Cave
quelle
3
Ich würde auch erwähnen, dass die Herausforderung "Suche nach dem Block, der sich auf 1 Gigabyte einer 2-Gigabyte-Datei befindet" mit der verknüpften Liste der Byte-Implementierung etwas Zeit in Anspruch nehmen könnte.
Das Problem, was während des Einfügens passiert, ist eine Sache, die bei Menschen, die die Deduplizierung für Speichersysteme entwerfen, große Bestürzung hervorruft.
Blrfl
Vielen Dank für Ihr Verständnis, dass ich nicht über Bytes sprechen wollte, sondern über das Gesamtbild.
Benutzer
8

Das "Problem" besteht darin, wie Dateien byteweise auf das Speichermedium geschrieben werden.

In der einfachsten Darstellung ist eine Datei nichts anderes als eine Reihe von Bytes, die auf die Festplatte (auch als Speichermedium bezeichnet) geschrieben werden. Ihre ursprüngliche Zeichenfolge sieht also so aus:

Address  Value
0x00     `a`
0x01     `a`
0x02     `a`
0x03     `b`
0x04     `d`
0x05     `d`
0x06     `d`

Und Sie möchten Can Position 0x04 einfügen . Dazu müssen die Bytes 4 - 6 um ein Byte nach unten verschoben werden, damit Sie den neuen Wert einfügen können. Wenn Sie dies nicht tun, überschreiben Sie den Wert, der derzeit bei 0x04 liegt und nicht Ihren Wünschen entspricht.

Address  Value
0x00     `a`
0x01     `a`
0x02     `a`
0x03     `b`
0x04     `C`
0x05     `d`
0x06     `d`
0x07     `d`

Der Grund, warum Sie das Ende der Datei nach dem Einfügen eines neuen Werts neu schreiben müssen, liegt darin, dass in der Datei kein Platz vorhanden ist, um den eingefügten Wert zu akzeptieren. Andernfalls würden Sie überschreiben, was dort war.


Anhang 1 : Wenn Sie den Wert von durch ersetzen möchten, müssen Sie den Schwanz der Zeichenfolge nicht neu schreiben. Das Ersetzen eines Werts durch einen Wert gleicher Größe erfordert kein Umschreiben.bC

Anhang 2 : Wenn Sie die Zeichenfolge abdurch ersetzen möchten, müssen CSie den Rest der Datei neu schreiben, da Sie eine Lücke in der Datei erstellt haben.

Nachtrag 3 : Block Level - Konstrukte wurden erstellt , um große Dateien zu erleichtern Handhabung zu behandeln. Anstatt zusammenhängenden Speicherplatz für Ihre Datei im Wert von 1 Million zu finden, müssen Sie jetzt nur noch verfügbare Blöcke im Wert von 1 Million finden, in die Sie schreiben können.

Theoretisch könnten Sie ein Dateisystem erstellen, das Byte für Byte verknüpft, ähnlich wie Blöcke. Dann können Sie ein neues Byte einfügen, indem Sie das auf | aktualisieren von Zeigern an der entsprechenden Stelle. Ich würde eine Vermutung wagen, dass die Leistung darauf ziemlich schlecht wäre.


Verwenden Sie, wie Großmeister B vorgeschlagen hat , ein Bild gestapelter Dominosteine, um visuell zu verstehen, wie die Datei dargestellt wird.

Domino

Sie können keinen weiteren Domino in die Domino-Linie einfügen, ohne dass alles umkippt. Sie müssen den Raum für das neue Domino schaffen, indem Sie die anderen entlang der Linie bewegen. Das Verschieben von Dominosteinen entlang der Linie entspricht dem erneuten Schreiben des Endes der Datei nach der Einfügemarke.

Gemeinschaft
quelle
Angenommen, ab C und d sind keine Zeichen, sondern Gigabyte Zeichen. Könnten Sie dies in Ihrer Antwort ansprechen? Ich mag das Bild, aber ich denke auch, dass die Leute versuchen würden, 1000 Dominosteine ​​in 2000 Dominosteine ​​anders einzufügen als 1 Dominostein in 6 Dominosteine.
Benutzer
@User - GB Zeichen anstelle von Bytes ändern die Art Ihrer Frage grundlegend, und jetzt müssen Speicherblöcke berücksichtigt werden. Auf einer einfachen Ebene ist die Antwort dieselbe. Sie können nichts in eine zusammenhängende Reihe von "whatevers" einfügen, ohne Platz zu schaffen.
0

Das Einfügen in eine Datei ist in den meisten Dateisystemen nicht implementiert, da es als "teurer" Vorgang (zeit- und raumfressender Vorgang) mit potenziell langfristigen "teuren" Auswirkungen und zusätzlichen Fehlermodi angesehen wird.

Ein Dateisystem mit Einfügesemantik würde wahrscheinlich entweder Shift & Insert verwenden (möglicherweise sehr teuer, wenn Sie am Anfang einer großen Datei einfügen, aber keine / wenige langfristige Nebenwirkungen) oder eine Art verallgemeinerte Heap-Zuordnung mit Zuordnungsgrößen variabler Länge ( In einigen Fällen sehr schlecht benommen [Stellen Sie sich die Gesichter der interaktiven Benutzer vor, wenn sie versuchen, eine Datei während eines Stop-the-World-GC zu speichern!]).

Wenn Sie experimentieren möchten, können Sie einfach eine Datei-E / A-Abstraktion in Java oder Python erstellen, die das Einfügen implementiert. Wenn Sie erfolgreich sind und sich gut verhaltene Leistungsmerkmale aufweisen, haben Sie die Grundlage für ein hervorragendes Forschungspapier. Viel Glück.

Scott Leadley
quelle
Dies scheint nichts Wesentliches über die vorherigen 6 Antworten zu bieten
Mücke
Sie können die gesamte gewünschte Software schreiben, dies ändert jedoch nichts an der Funktionsweise der Hardware. Hardware funktioniert durch Lesen / Schreiben in Blöcken / Seiten. Wenn diese Daten auf einer Festplatte nicht zusammenhängend sind, muss sich der Lesekopf bewegen, was die Dateizugriffszeit erheblich verlangsamt. Jede Einfügeoperation müsste "aufgrund der Tatsache, dass es sich um eine Einfügung handelt" an anderer Stelle und nicht zusammenhängend gespeichert werden. Das Einfügen ist also möglicherweise schneller (bei sehr großen Dateien), aber das Lesen ist viel langsamer.
Dunk
0

Der effizienteste Weg, einen Byteblock in die Mitte einer Datei einzufügen, wäre:

  1. Ordnen Sie die Datei dem Speicher zu
  2. Fügen Sie die Bytes am Ende des Speicherabbilds der Datei hinzu
  3. Drehen Sie diese Dateien an ihren Platz (z. B. mit einem Standardalgorithmus, der in der C ++ - Standardbibliothek verfügbar ist).
  4. Lassen Sie das Betriebssystem schmutzige Blöcke auf die Festplatte schreiben
Laurent LA RIZZA
quelle
-1

Zuerst müssen Sie alles nach dem Einfügepunkt lesen und dann um so viel Platz zurückschreiben, wie Sie einfügen möchten. Dann können Sie Ihre "Einfügen" -Daten an die richtige Stelle schreiben. Extrem schlechter Leistungsbetrieb, daher nicht nativ unterstützt.

Brian Knoblauch
quelle
1
Was ist mit einer SSD mit wahlfreiem Zugriff? Auch Dateien werden vom Dateisystem in Teile geteilt. Wie hängt das damit zusammen, alles wieder zu schreiben?
Benutzer
@Benutzer sicher, dass Sie zufällig darauf zugreifen können (obwohl Sie keinen Zugriff auf Bitebene ausführen, führen Sie dennoch Blockebenen aus) ... aber wie sagen Sie, welches Byte als Nächstes kommt?
1
SSD liest und schreibt immer noch jeweils eine Seite. Um Ihr 1-Byte zu schreiben, das Sie einfügen möchten, müssen Sie eine ganze Datenseite schreiben und alle entsprechenden Dateisystemtabellen / -zeiger aktualisieren. Es würde mich nicht wundern, wenn die anfänglichen Dateisysteme eine einfügeähnliche Operation hätten, aber sie stellten fest, dass dies weitaus mehr Overhead hinzufügte als es sparte.
Dunk
-1

Wenn Sie direkten Zugriff auf eine Datei haben, verwenden Sie eine niedrige Ebene, mit der komplexere Strukturen erstellt werden können. Erwägen Sie, eine Datenbank mit Ihren Daten zu erstellen, die die von Ihnen benötigten Zugriffstypen einschließlich des Einfügens ermöglicht.

Es wäre kostengünstiger, wenn Sie nur die Datei durchlaufen müssen und keine zufälligen Zugriffe auf einen bestimmten Offset ausführen müssen. Wenn Sie einen zufälligen Zugriff durch Versatz in der Datei benötigen, müssen Sie den Index für alle Bytes jenseits der Einfügemarke aktualisieren.

Im Allgemeinen zahlen Sie für die Indizierung von Datenstrukturen, den Speicher zum Speichern des Index und zusätzliche Festplattenzugriffe zum Aktualisieren.

Patricia Shanahan
quelle