Dateiorganisation Flashcards
(48 cards)
Primärspeicher
- Cache, Ram
- teuerer (als Sek.)
- schneller (als sek)
- flüchtig (nicht-persistent)
- Zugriffsgranularität: fein, Zugriff auf Byteebene
Sekundärspeicher
- Festplatte, Magnetbänder
- günstig ((er) als Prim.)
- langsam ((er) als Prim)
- persistent
- Zugriff auf Blockebene (oft 512 Byte pro Block)
Mittlere Zugriffszeit
- Seek time => Zugriffsarm (Schreib-Lese-Kopf) positionieren
- Latenzzeit (latency) => Warten bis richtiger Sektor Kopf passiert (Umdrehungszeit)
- Transferzeit => Übertragungszeit von Platte in Hauptspeicher
Record Defintion
Sammlung von Feldern die in einer Beziehung zueinander stehen (logischer Datensatz)
Record Speicherverfahren
Fixlängenspeicherung => für jedes Feld fixe Anzahl Bytes
Speicherung variabler Längen (Trennzeichen) ==> Zwischen var Feldern spezielles Trennzeichen - weniger Speicherplatz verbraucht, langsamerer Zugriff als Fixlänge
Speicherung var Längen (Key-Value-Paare) ==> Key = Value, Nicht gesetzte Felder nicht gepeichert (Sparsam)
Bsp Name=Smith, John/usw.
Auslesen schwieriger, nicht angegegebene Felder werden nicht mehr explizit gespeichert
Hash-Kollision
Bei einer Hash Kollision ergibt die Hash Funktion für 2 Schlüsselwerte den gleichen Wert, womit beide Schlüsselwerte am selben Speicherplatz gespeichert werden müssten.
Hash Kollisionen lassen sich nicht vermeiden, da die Schlüsselmenge in den meisten Fällen größer ist als die Menge an Speicherplätzen (Wertemenge).
Warum wird sequentieller Zugriff im Vergleich zu Wahlfreiem Zugriff immer Schneller verhältnismäßig immer schneller?
Transferraten wachsen verhältnismäßig schneller als Rotations und Positionierungszeiten.
Was ist Heap, Sequenziele, und Hash-Organisation?
Heap Organisation -unsortierte Speicherung von internen Tuplen
Sequenzielle Organisation - sortierte Speicherung von internen Tupeln
Hash Organisation - gestreute Speicherung von internen Tupeln
In einer unspanned Heap-Datei wird der i-te fixe Record in den Festplattenblock (i/bfr) an der Position (i mod bfr) gespeichert. Erläutern Sie, warum dieses Wissen im operativen Datenbankbetrieb
faktisch nicht vorteilhaft ausgenutzt werden kann
Der Zugriff auf den i-ten Record in einer unsortierten Datei beschleunigt lediglich das Suchen nach dem i-ten Eintrag der Datei, nicht aber die Suche anhand
konkreter Felder in den Records
Heap vs. sotierte Datei? Kategorien (Suchoperationen, Einfügen löschen, sotierte Ausgabe)
Suche: Aufwändig da alle Records gelesen werden müssen Durschnitt n/2. Binäre Suche effizienter
Einfügen: Einfach weil einfach am ende eingefügt werden kann. Aufwändig da Dateien ggf. umorganisiert werden müssen
Löschen: Aufwändig da gesucht werden muss und Reorganisation zur Lücke gemacht werden muss. Nur günstiger wenn Sotierfeld ansonsten genauso aufwendig
Sotierte Ausgabe: Sehr schwer, einfach weil bereits sotiert vorliegen
REihenfolge der Blockspeicherung 3. Varianten Contiguous Allocation Linked Allocation Clustered Allocation
1.Contiguous Allocation
Alle Blöcke werden konsekutiv hintereinander geschrieben
-Hohe Lesegeschwindigkeit
-Teure Einfügeoperationen
2.Linked Allocation
Am Ende jedes Blocks befindet sich ein Pointer auf den nächsten Block
-Teure Leseoperationen
-Einfügeoperationen problemlos realisierbar
3.Clustered Allocation
Konsekutive Block-Cluster werden untereinander verlinkt Kompromisslösung
Unterschied B und B+ Baum
Daten sind nur in Blätter daher auch als hohler Baum bezeichnet (B+).
Was sollte bei einem B baum nicht getan werden und warum?
Sotierte Zahlen sollten nicht in ein B-Baum eingefügt werden da dies zu einer schlechten Auslastung des Baums führt.
Ordnung p=5 wie viele paare können nach unten abgehen
5 Paare können abgehen, nur 4 Kästchen.
Was ist ein Index?
Ein Index ist ein sekundärer Zugriffspfad auf eine Datei, der parallel zur primäaren Dateiorganisation existiert. Er erlaubt einen direkten Zugriff auf die Daten innerhalb der Datei
Vorteile eines Indexes
Effiziente Suchverfahren können angewandt werden. Sequenzielle Suche entfällt. (Weniger Blockzugriff um Record zu finden)
Sparse und Dense Index Unterschied
Sparse Index zeigt nur auf den ersten Eintrag im Block d. h es können WErte lücken entstehen. Daher ist eine Sotierung inerhalb des Blocks entscheidend. (Primary Index)
Wie ist ein Primary Index aufgebaut?
Wird über einem eindeutigen Attribut gebildet, nach dem die Datendatei physisch organisiert ist.
Jeder Record besteht aus zwei Feldern:
Das erste Feld ist vom selben Datentyp wie das Sortierfeld der Datendatei. (Bsp. Hans Mueller)
Das zweite Feld ist ein Pointer auf einen Disk Block, in dem der Record physisch liegt.
Was für Aussagen können über den Secondary Index getroffen werden ?
Existieren für den jeweiligen Indexeintrag nur ein WErt in der Datentabelle handelt es sich um einen Dense Index.
Ist sotiert. Jeder Index ist einem Record zu gewisssen. Index kann eindeutig sein muss aber nicht zwangsläufig.
Was ist ein sogenannter clustered Index und was unterscheidet diesen?
Der Clustered Index besitzt somit die gleiche Struktur wie der Primary Index Aber: An Stelle eines Eintrages pro Disk Block enthäalt der Clustered Index nun einen Eintrag für jeden unterschiedlichen Wert des Sortierfeldes! Auch der Clustered Index ist ein sparse Index.
Wie können Hash-Kollisionen vermieden werden?
1.Lineares Sondieren
Wert rechts neben in Tabelle in freies Feld schreiben
2.Anhängen einer verketteten Liste an die Hash-Position (Overflow-Listen)
Werte unter den bereits belegten Wertschreiben -> Lücken im Wertebereich
-3.Mehrfaches Hashing, d.h. Anwendung weiterer Hash-Funktionen
Was ist mit gobaler Tiefe gemeint ? Binär System Tiefe 1: 0 und 1 Tiefe 2 01, 10
Man schaut sich die 1,2 oder 3 stellen des Hashwerts an und ordnet die Namen dann in die jeweiligen Blätter ein.
Warum sollte bei der Hash-Map nicht die binäre Schreibweise gewählt werden.
Da die Nummern sequentiell vergeben werden und erst ab 2125 beginnen, unterscheiden sie sich in der Bmardarstellung nur in den letzten Bits wesentlich. Es würde also ein unnötig großes Verzeichnis
angelegt, wenn man die Binardarstellung als Hashwert verwendet hätte
Um dies zu verhindern, nimmt man die inverse Darstellung. In der Praxis sollte man die Schlüsselwerte noch starker - z B durch Faltung -
„durcheinander wirbeln“
was macht ein Equijoin
ER übernimmt nur die Zeilen wo es in beiden Tabellen einen Match gibt
