Modul B-PRG Grundlagen der Programmierung 1 · Grundlagen der Programmierung 1 R.Brause: Dateiverwaltung Folie 31 Indexsequentielle Dateien Definition B-Baum (Bayer, McCreight1972)

1

Modul B-PRG

Grundlagen der Programmierung 1

Teil 3:Teil 3: Betriebssysteme, Dateisysteme, SicherheitBetriebssysteme, Dateisysteme, SicherheitV22+V23: V22+V23: DateiverwaltungDateiverwaltung

Prof. Dr. R. BrauseAdaptive SystemarchitekturInstitut für Informatik Fachbereich Informatik und Mathematik (12)

Grundlagen der Programmierung 1 R.Brause: Dateiverwaltung Folie 2

Dateisysteme

Liste von Dateien auf Massenspeicher

= relationale Datenbank!Objektorientierte Datenbank: mit Methoden+AttributenMulti-Media-Datenbank: mit Bild+Tonobjekten+Synchron.

Organisation von DatenbankenPersistent Storage Manager PSM (kleineObjekte)Object-Oriented Database Management System OODBMS

Nummer Name Position Länge Datum ...0 Datei1.dat 264 1024 11.12.871 MyProgram 234504 550624 23.4.962 Datei1.dat 530 2048 25.1.97... ... ... ... ... ...

2


Dateinamen

Hierarchische Dateiorganisation in BaumformKnoten = „Ordner“ = directory

Alle Dateien

Gruppe 1 ... Gruppe m Datei f

Datei 1 Datei 2 ... Datei n Datei k ... Datei s

Zusätzliche Vernetzung (azykl.Graph)

Firma Abteilung 5

Formulare Rudi Hans

BriefVorlage.dot Brief1.doc .. BriefN.doc Brief1.doc BriefM.doc


Dateinamen

NamensbildungNamensbildung Name.ext (üblich)Extension = Dateityp, Dateizweck

Beispiele:.dat Daten; Format hängt vom Erzeugerprogramm ab.doc Textdokument in dem speziellen Format des Texteditors.pas PASCAL-Programm Quellcode.c C-Programm Quellcode.h Deklarations (header)-Dateien für C-Programme.ps Postscript Dateien zum Ausdrucken.Z, .zip, .gz Komprimierte Dateien.tar ein gesamtes Dateisystem, in einer Datei abgespeichert.html ASCII-Textdatei für das world wide web-Hypertextsystem.jpg, .gif, Bilddateien.tif, .bmp3 Extensionsbuchstaben: MS-DOS! Sonst: 215 Char ohne \ / : * ? " < >

3


Geschachtelte Typen

Beispiel: Skript.ps.gz= Textdatei → Postscript-Format→Komprimiert

Dateinamen: Externe Typangabe

Typaktionen Typ verknüpft mit Aktion

Benutzeroberfläche (Desktopmanager HP -VUE, MS-Explorer) behandelt DateinamenListe von Aktionen pro Typ definiert (Kontextmenü)Doppelklick = erste Aktion ausführen


Dateinamen: UNIX Interne Typangabe

class File Header {a_magic: LONG CARDINAL (*Magische Zahl*)a_txt: CARDINAL (* Code-Segmentgröße *)a_data: CARDINAL (* Segmentgröße der init. Daten*)a_bss: CARDINAL (* Segmentgröße der nicht init.Daten*)a_syms : CARDINAL (* Größe der Symboltabelle*)a_entry: CARDINAL (* Start des Programms*)

... }a_magic =

407B (* altes Format: Code („text“) und Daten werden nicht schreibgeschützt und sollen deshalb nicht von anderen Prozessen genutzt werden *)

410B (* Text -Segment wird schreibgeschützt, und das Datensegment wird an die nächsten Seitengrenzen (4 KB) im Speicher gelegt *)

413B (* Text -Segment fängt an der nächsten Seitengrenze der Datei an; text und Datensegmente sind Multiple der Seitenlänge *)

4


Dateinamen: Eindeutigkeit

Problem: eineindeutige Abbildung langer Namen auf kurzez.B. NTFS → MS-DOS (8 Zeichen..3Zeichen)

Lösung Windows NT:üAlle illegale MS-DOS Buchstaben löschen sowie alle Punkte

innerhalb des Namens bis auf den letzten, falls er nicht abschließt. Kleinbuchstaben → Großbuchstaben.üNur die ersten 6 Buchstaben beibehalten, Zeichen „∼1“ vor

dem Punkt einfügen.ü3 Zeichen hinter dem Punkt beibehalten, alle anderen löschen.üEx. Datei gleichen Namens, so wird „∼1“ zu „∼2“ bzw. zu

„∼3“, falls schon existiert.

Beispiel: „Ganz langer Dateiname.text.ps“ → GANZLA~1.ps


Dateinamen: Pfadnamen

absolute PfadnamenDateiname = Kette aus Knotennamen von der Wurzel zum BlattBeispiel: /Abteilung5/Rudi/Brief1.doc Unix

\Abteilung5\Rudi\Brief1.doc NT

relative PfadnamenVorgänger: ..Dieses Verzeichnis .Beispiel: Rudi/Brief1.doc ist bei Hans: ../Rudi/Brief1.doc

Abteilung 5

Rudi Hans

BriefN.doc Brief1.doc BriefM.docBrief1.doc

5


Dateinamen: Pfadnamen

Vorteil relativer Pfadnamen: PortabilitPortabilitäättBeispiel Programmsystem

/

toolsX toolsY

Daten Programme

Dat1.a liba libb Prog

Absolute Pfadnamen müssen nach Verschiebung des Programmsystems geändert werden, relative nicht !


Dateinamen: UNIX Namensraum

Querverbindungen durch hard links (gleiches Laufwerk) oder symbolic links (anderes Laufwerk)

Beispiel: hard link löschen zu Datei2: Datei bleibt erhalten (Zähler).zu rück-referiertem Verzeichnis: stand-alone Verzeichnis?

Abteilung5

Gruppe 1 Gruppe2

Rudi Hans

Datei1 Datei2 Datei3

symbolic linkhard links

×

Baumorientiertes Dateisystem

6


Zugriff mit /users/Rudi/Brief1.doc

user file system

Rudi Hans Ute Festplatte 2Brief1.doc

/

Dateinamen: UNIX Pfaderweiterung

Einhängen eines Dateisystems (mounten)

root file system

etc bin usr

users

/Festplatte 1


Dateinamen: Windows NT Namensraum

Namen für alle Objekte wie pipes, shared memory, Prozesse, Semaphoren, events, ...

Logische Querverbindungen (symbolic links)

Löschen von Dateien: 2 Referenzzähler (user und kernelhandles)

„Durchsuchen“-Methode bei jedem Objekt: neue, unbekannte Dateisysteme!

7


Dateinamen: Windows NT Namensraum

Symbolic link parsing-Methode:\

Device DosDevices

Floppy0 HardDisk0 A: B: C:

Texte Email Partition0

bs_mem.doc bs_files.docObjekt Manager Namensraum

Dateimanager Namensraum

Beispiel A:\Texte\bs_files.doc

Objekt manager: A:\Texte\bs_files.doc à \Device\Floppy0\Texte\bs_files.doc

Datei manager: Find Texte\bs_files.doc


Dateiattribute und Sicherheit

Dateiattribute§ Dateilänge§ Datum für Erzeugung, letzte Änderung,..§ Log. Attribute hidden, system, Archiv, § Erzeuger, Besitzer, Benutzer und ihre Rechte

Rechte & Sicherheit in POSIX-6:

§ geringstmöglichste Rechte für eine Aufgabe (least privilege)

§ Diskrete Angaben für Zugangskontrolle: Wer darf, wer nicht (ACL)

§ Zugangskontrolle nur von Prozessen größerer Rechte (mandatorycontrol)

§ Aufzeichnung des Zugangs (audit trail)

8


drwx r-x r-x brause 512 Apr23 15:55 .

off 512 May17 17:53 ..

-rw- r-- r-- brause 44181 Apr23 15:56 data1.txt

drwx r-x r-x

Dateiattribute und Sicherheit: UNIX

Zugriffsrechte: Lesen R, Schreiben W, Ausführen XVerzeichnisse: R=Liste lesen, W=neue Datei aufnehmen, X=Liste durchsuchen nach DateiGetrennt für Besitzer, Gruppe, Alle

Rechte bei Programmausführung = user RechteAber: set userId, set group Id

ACL ex. in neuerem Unix (Wer, was, wie)


Dateiattribute und Sicherheit: Windows NT

Standardrechte: Read, Write, ExecuteOnly, Vollzugriff, ...ACL ex., neue Gruppen möglichAuditing möglichSpeziell für Dateien:ü Attribute

• Dateiname, Gerätetyp, Position in Datei, share-Status(r,w,del)

• Mode: sync/async, mit/ohne Cache, seq/random Access, ...• File disposition: temp oder persistent

ü Methoden• CreateFile(), OpenFile(), ReadFile(), WriteFile(), CloseFile()• Lesen/setzen von Dateiinfo, Attributen, Geräteinfo, Verzeichnissen

• Sichern/freigeben der Dateilänge

Attribute implementiert durch Datenströme, neu erzeugbar„MeineDatei.dat : MeinKommentar“ (nichtlöschbare Viren!)

9


Verbind.Verbind.--orientierteorientierteKommunikationKommunikation

Dateifunktionen

StandardfunktionenStandardfunktionen

Create File Name, Zugriffsart: Tabelleneintrag

Open File Apprüfen der Zugriffsrechte, Puffereinrichtung,

Close FilePuffer + Tabellen deallozieren,

Read/Write File Puffer schreiben/lesen: DMA!

Seek FileIndex setzen der aktuellen Position → random access


Dateifunktionen: UNIX

fd = creat(Name, mode)file descriptor = Index in Tabellefd = open (Name, mode)read (fd, buffer, nbytes)write(fd, buffer, nbytes)close(fd)

fd=1 fd=0 fd=1 fd=0Programm1 Programm2 Programm N

fd=2 fd=2 fd=2

Fehlerausgabe Fehlerausgabe Fehlerausgabe

Beispiel: pipesfd=0: Standard Input, fd=1 Standard Output, fd=2 standard error

Programm1 | Programm2 | .. | ProgrammN

10


Dateifunktionen: Windows NT

Übliche Dateizugriffsfunktionen wie Unix

Bei Veränderung der Dateistruktur: Atomare Transaktionendurch log file service LFS (write-ahead logging)

Ergänzung der Operationen nach Absturz:= Fehlertolerantes Dateisystem

Wirksam bei fail save-System, nicht aber bei aktivem Fehler

DateistrukturenDateistrukturen

11


Strukturierte Zugriffsfunktionen

Sequentielle Dateien sequential filesMagnetbänder, LochstreifenProblem: unbekannte Zugriffsreihenfolge

Wahlfreie Dateien random access filesFestplatten, CD-ROM: Positionsangabe (offset) möglichProblem: ineffizient bei bekannter Datenorganisation

Indexsequentielle Dateien index-sequential filesÜbersicht (Index) am Dateianfang,Ordnung nach einem Kriterium (Schlüssel),

z.B. Name, Geburtsdatum, ...

Fehlen der DB-Unterstützung: Problem bei UNIX!


Indexsequentielle Dateien

Einwohnerdatei, Schlüssel = Alter

Auffüllen von Containern der Größe m mit Schlüsseln

Baumstruktur für indizierten Zugriff:Index n-1. Stufe= {max (container Index n-ter Stufe) }Index-sequentielle Speicherung (Zylinder, Spur, Sektor)

Beispiel 12 Record-Schlüssel: 5, 15, 26, 42, 48, 56, 80, 82, 97, 37, 50

48 97 Index 1. StufeZylinder

x≤48 48<x≤97

26 48 80 97 Index 2. StufeSpur

x≤26 26<x≤48 x≤80 80<x≤97

5 15 26 37 42 48 50 56 80 82 97 Index 3. StufeSektorDatensätze

Problem: Eingliedern/Ausgliedern von Datensätzen in die Container (Datenblöcke) fester Größe, z.B. „41“

12



NeuordnungSchnellerer Zugriff: Jeder Schlüssel wird nur einmal notiert und enthält bereits das Info für den Dateizugriff

Pro Intervall ein Ast (oder Blatt), max. m Intervalle pro Knoten, m-1 Schlüssel

Ist ein Schlüssel nicht vorhanden, wird er im Intervall auf unterster Stufe eingefügt und ein neues Blatt (Platzhalter) wird daneben erzeugt ⇒ Alle Blätter sind auf der selben Ebene

Ist ein Behälter zu voll, so wird er in zwei Behälter aufgeteilt und der Schlüssel in der Mitte eine Ebene höher verschoben

Beispiel: m=5 (max. 4 Schlüssel pro Knoten bzw. Schlüsselbehälter)Die 12 Record-Schlüssel 5, 15, 26, 42, 48, 56, 80, 82, 97, 37, 50 werden abgespeichert



Beispiel: m = 5 Schlüssel 5, 15, 26, 42, 48, 56, 80, 82, 97, 37, 50

(a)

26 Index 1. Stufe

48

5 15 26 42 5 15 42 48 Index 2. Stufe

13




Eingliedern

Index 1. Stufe

Index 2. Stufe485 15 26 42




Schlüsselbehälter aufspalten

Index 1. Stufe

Index 2. Stufe

26

5 15 42 4826

14




Schlüsselbehälter auffüllen

Index 1. Stufe

Index 2. Stufe

26

5 15 42 48 56 80 82




Schlüsselbehälter teilen

Index 1. Stufe

Index 2. Stufe56

26

5 15 42 48 80 82

56

15




Schlüsselbehälter auffüllen

Index 1. Stufe

Index 2. Stufe97

26

5 15 42 48 80 82

56

5037


B-Baum

Allgemein: Einfacheres Einfügen neuer SchlüsselIntervall (Ast oder Blatt) suchen für neuen SchlüsselEinfügen auf unterster StufeÜberfließen bei max. m Schlüsseln pro Behälter (m ungerade):

Aufteilen in zwei H älften [S1...St-1], St, [St+1 ...Sn], t = (n-1)/2 +1 = n/2

§ Nachbarbehälter hat Platz (n = m+k < 2m) : Umverteilen§ Nachbarbehälter bereits voll (n = 2m) : Beide fusionieren +

Schlüsselbehälter wird aufgeteiltMittleren Schlüssel St nach oben verschieben in h öhere Stufe

Bei Überlauf im Behälter der h öheren Stufe wie oben verfahren

Eigenschaften

§ Gleiche Anzahl von Verzweigungen pro Ebene§ Schlüsselbehälter sind mind. zur Hälfe m/2 voll

⇒ „B-Baum“

16



Definition BB--Baum Baum (Bayer, McCreight 1972)

Ein B-Baum der Ordnung m ist ein Baum, bei dem

(1) die Wurzel (wenn sie nicht Blatt ist) mind. 2 Äste hat

(2) jeder Knoten mit k Verzweigungen k–1 Schlüssel (Indizes) enthält,

(3) jeder Ast bzw. Knoten (bis auf die Wurzel und Blätter) in minimal k=m/2 und maximal k = m Äste verzweigt,(minimal zur Hälfte gefüllte Behälter)

(4) alle Blätter auf derselben Ebene sind. Die Blätter selbst tragen keine Information; sie stellen nur mögliche Einfügepunkte für Indizes dar.

Satz: Bei N Schlüsseln gibt es N+1 Blätter


B-Baum

Anzahl der nötigen Stufen (Baumtiefe) (ungerades m)

1.Stufe: mind. 2 Verzweigungen der Wurzel nötig2.Stufe: mind. 2 mal m/2 Verzweigungen auf der Stufe3.Stufe: mind. 2 mal m/2 mal m/2 Verzweigungenn-te Stufe: mind. 2⋅m/2⋅m/2⋅.. = 2⋅m/2n–1 Verzweigungen

= N+1 Blattverzweigungen

Wir erreichen spätestens in der n-ten Stufe 2⋅m/2n–1 = N+1 Verzweigungen.Also: 2⋅m/2n–1 = N+1

n–1 = logm/2 (N+1)/2 Log. Suchzeit! BeispielBei m=200, N=2 Mill.: max. n-1 = log100(1⋅106)=log100(1003) = 3 Stufen, also nur max. n=4 Stufen!

B-Bäume sind flach !

17


B-Baum

Problem: Häufiges Teilen der BehälterVerbesserungen

Ausgleich zwischen vollen und leeren BehälternVerschiebe vom Schlüsselbehälter mit m–1 Schlüsselnzu einem Nachbarbehälter mit k < m-1 Schlüsseln so, daßjeweils die halbe Gesamtschlüsselzahl verbleibt und der mittlere Schlüssel mit Index i= (k+m)/2 nach oben wandert.

Aufteilen von zwei vollen BehälternTeile vollen (m-1) und übervollen (m) Behälter + dazugehörenden Schlüssel der nächsthöheren Stufe (=2m) in drei Behälter auf zu je (2m-2)/3 + 2 Schlüssel für die nächste Stufe.

Also jeweils (2m–2)/3, (2m–1)/3 und (2m)/3 Schlüssel, wobei die beiden Schlüssel SA und SB mit den Indizes A=(2m+1)/3, B= (m–2)/3 nach oben in die höhere Indexstufe wandern.

⇒ Jede Partition ist nicht mind. ½, sondern 2/3 voll


B*-Baum

Definition B*B*--Baum Baum Ein B*-Baum der Ordnung m ist ein Baum, bei dem

(1) die Wurzel mindestens 2 und maximal 2 (2m–2)/3 +1Verzweigungen hat. Damit kann die Wurzel beim Überfließen in 2 Behälter zu je(2m–2)/3 Schlüssel (plus ein Schlüssel als neue Wurzel) geteilt werden.

(2) jeder Ast bzw. Knoten (bis auf die Wurzel und Blätter) in minimal k= (2m–1)/3 und maximal m Äste verzweigt.

(3) jeder Knoten k–1 Schlüssel (Indizes) enthält.

(4) alle Blätter auf derselben Ebene sind.

18


B*-Baum: Beispiel


B*-Baum: Eingliedern in Wurzel mit max 2 (2m–2)/3 = 4 Schlüsseln

Index 1. Stufe

Index 2. Stufe485 15 26 42


B*-Baum: Beispiel


B*-Baum: Wurzel-Schlüsselbehälter aufspalten

Index 1. Stufe

Index 2. Stufe

26

5 15 42 4826

Resultiert in 2 Behälter je (2m–2)/3 = 2 Schlüssel wie beim B-Baum

19


26

155 42 48

B*-Baum: Beispiel


B*-Baum: Überfließen

Index 1. Stufe

Index 2. Stufe829756 805

42

2615 48 56 80 825 15

48

4226 56 80 82 97


26 80

B*-Baum: Beispiel

Beispiel: m = 5 Schlüssel 5, 15, 26, 42, 48, 56, 80, 82, 87, 97, 37, 50

B*-Baum: Behälter dreiteilen

Index 1. Stufe

Index 2. Stufe48

48

8026 975 15 42 56 82 87

20


B*-Baum vs. B-Baum: Beispiel

Vergleich B-Baum vs. B*-Baum

Beispiel: Aufbau + Einfügen von „41“

m=5

(a) (b)

26 42 56 37 56 Index 1.Stufe

5 15 37 41 48 50 80 82 97 5 15 26 41 42 48 50 80 82 97 Index 2.Stufe

Fazit: B*-Baum hat besseren Füllgrad ⇒ weniger Behälter nötig


Mehrfachlisten und Invertierte Dateien

Die Indexfolge jeden Schlüssels ist als Liste implementiertBeispiel: Mehrfachliste

Indexfolge 1,3,2,6,5,8

Problem: Sequ. Schlüsselsuche

Lösung : Alle Zeiger im Dateianfang: invertierte Datei

(Schlüssel→Record statt umgekehrt)

Schlüssel 1

Schlüssel 2

...

Schlüssel m

Satz 1 Satz 2 Satz 3 Satz 4 Satz 5 Satz 6 Satz 7 Satz 8

21

DateiDatei--implementierungimplementierung


Dateiimplementierung

Kontinuierliche SpeicherzuweisungDatei „in einem Stück“: Schnell, aber nicht änderbar.

Listenartige SpeicherzuweisungVerzeigerte Liste von Speicherblöcken (Strategien!)

Vorteil Rekonstruktion möglich bei Anker-Löschung Nachteil ineffizienter wahlfreier Zugriff

Datei A

Datei B Nil

BBlock 0

ABlock 1

BBlock 1

BBlock 2

ABlock 0

ABlock 2

BBlock 3

0 1 2 3 4 5 6

22



Zentrale indexbezogene Speicherzuweisungzentraler Block von Zeigern (Indizes) in einer Liste

Anfang Datei B

Anfang Datei A

Ende Datei B

Phys.BlockNr = ListenIndex

nächsterDaten-block

0 21 52 33 64 15 76 NIL


Dateiimplementierung: Zentraler Index

Beispiel File Allocation Table FAT von MS-DOS

Blockgröße: 512 Byte (= 1 Sektor), Block 0: Bootstrap,

Blöcke 1-5: FAT mit je Eintrag 12 Bit = 3Hexzahlen = 1.5 Byte

Pro cluster 1024 Byte = 2Blöcke

Block 18/19

Cluster 0

Cluster 1

Cluster 2

Index 3

12 Bit

1024 Byte

Index 2

Index 4

Index 5

Index 6

Block 20/21

Block 22/23

Maximale Diskettengröße

max. FATgröße 5⋅512=2560Byte

Max. Zahl der Einträge = 2560/1.5 = 1706 Einträge (cluster), also max 1706 ⋅1024Byte

= 1,7 MB pro Diskette

23


Dateiimplementierung: Zentraler Index

FAT-ProblemeIndexgröße Floppy 12 Bit → Platten 16 Bit

212 Einträge → 216 Einträge = 216 Cluster

Problem1 : zu wenige Cluster

Bei 2 GB Platte und 216 Cluster istClustergröße = 2 GB/Clusterzahl

= 231/216 = 215 = 32kB groß: großer Verschnitt von 16kB!

Problem2: zu kleine Cluster

Bei 2 GB Platte und 1kB Clustergröße→ 231/210 = 221 = 2 Mill. Einträge. Da jeder Eintrag 2 Mill andereEinträge referieren kann, muß er mind. 21 Bit (3 Bytes) breit sein. Dies bedeutet 2 Mill.× 3 Bytes = 6 MB Platz für die FAT-Tabelleim Hauptspeicher, ohne daß alle Einträge benutzt werden.

⇒ Bei kleinen Clustern gibt es lange Listen im RAM sowie lange Suchdauer.



Verteilte indexbezogene SpeicherzuweisungStatt zentraler Index aller Dateien eigene Indexliste pro Datei:

Datei A4157...

Datei B0236

NIL

Problem: Bei einigen Dateien ex. sehr viele Blöcke, lineare Blocksuche wird langsam.

24



Verteilte indexbezogene SpeicherzuweisungBaumstruktur zur schnellen BlocksucheTabellengröße vs. Suchzeit: 1-,2-,3-stufige Tabellen

phys.

Blöcke

(a) einstufige (b) zweistufige (c) dreistufige Übersetzung (einfach-indirekt) (zweifach-indirekt)

... ... ...


Dateiimplementierung: UNIX

Zentrale Tabelle pro Datei: i-node (Indexknoten)Verwaltungsdaten (Referenzen, Zeiger für free-Liste + mount()-Tabelle), erste Adressen von Datenblöcken + Zeiger für weitere

modelink countowner uidowner gid

file size3 time ref.Adressender ersten10 Blöcke

1-indirekt2-indirekt3-indirekt

Max 256 Einträge (Blockindizes)

Max 256 Einträge (Zeiger)

16,8 GB

67 MB266 kB

Verzeichnis = Datei = Tabelle aus Dateinamen + i-node-Nummer

Zentrale Tabelle aller i-nodes = super node

25


Dateiimplementierung: Windows NT

KonzeptKonzeptVolumes (log. Massenspeicher) als DatenspeichereinheitAlle Untereinheiten eines volumes sind nur Dateien (files), gekennzeichnet durch eine 48 Bit-Zahl &16Bit-Sequenznummer

Vorteile Vorteile Dateien vs. dedizierte Blöcke (Plattenbereiche)

einfacher, konsistenter Dateizugriffsmechanismus, sogar auf die boot-Information.Die Sicherheitsinformationen sind getrennt pro Objekt (Verwaltungsinformation) → besser anpaßbar an die inhaltlichen Notwendigkeiten des Objekts bzw. der Funktion.Werden Plattenteile unbrauchbar, so können die Verwaltungs-informationen unsichtbar für den Benutzer auch auf andere Plattenteile verlagert werden.


Chkdsk-Programm

Dateiimplementierung : Windows NT

~ ~

Datei 0 Master File Table

Datei 1 Sicherheitskopie der MFT ( Plattenmitte)

Datei 2 log file : Alle Operationen, die die NTFS-Struktur ändern, werden hier verzeichnet und garantieren so atomare Dateitransaktionen.

Datei 3 volume file : Statusinformationen Name, NTFS Version, ...corrupted Bit=1:

Datei 4 attribute definition table:Attributstypen + ihr Status

Datei 5 Root directory: Name des Wurzelverzeichnisses, z. B. \

Datei 6 bitmap file: Belegungstabelle der volume-Speichereinheiten (Cluster)

Datei 7 boot file: bootstrap Code von Windows NT und die physikalische Geräteadresse der MFT -Datei.

Datei 8 bad cluster file: Verzeichnis der unbrauchbaren volume-Cluster

. . .

Datei 16 Normale Benutzerdateien undVerzeichnisse

26


Dateiimplementierung : Windows NT

Struktur des Wurzelverzeichnisses root directory

root file Indexpuffer

Standardinformation

file name „ \ “

B*-Baum indexroot

file 4file 10file 15

indexallocation VCN→LCN

bitmap XXX0XX0XXXXX

...

VCN0 file 0, …1 file 1, …2 file 3, …3

VCN4 file 6, …5 file 8, …67 file 9, …

VCN8 file 11, …9 file 12, …10 file 13, …11 file 14, …

Max. 15 Dateien (Schlüssel)

pro container(4 Cluster)

Wurzelcontainerdes B*-Baums

Documents

Modul B-PRG Grundlagen der Programmierung 1 · Grundlagen der Programmierung 1 R.Brause: Dateiverwaltung Folie 31 Indexsequentielle Dateien Definition B-Baum (Bayer, McCreight1972)