Dateiorganisationsform: Wie viele blöcke müssen gelesen werden?
-
Hallo, ich hab gerade hier eine Aufgabe aber ich komme nicht weiter.
Gegeben ist:
- eine Tabelle mit 600.000 Datensätzen
- Für die sortierte Datei liegt ein mehrstufiger Primärindex für den Titel vor.
- Für die unsortierte Datei liegt ein mehrstufiger Sekundärindex für den Titel vor.
- Für beide liegt ein mehrstufiger Sekundärindex für das Jahr vor.
- Der Blockungsfaktor der Hauptdatei ist 200
- Der Blockungsfaktor eines Index für den Titel ist 300
- Der Blockungsfaktor eines Index für das Jahr ist 500
- Es gibt 5.000 Einträge für das Jahr 1980
- Es gibt 86 Einträge deren Titel mit ‚Star Wars‘ anfängtWie viele Blöcke müssen gelesen werden, um folgende Anfrage durchzuführen:
- Alle Filme, deren Titel mit „Star Wars“ anfängt.Lösung ist 3-4 Blöcke aber ich kann das nicht nachvollziehen
Ich habe schon berechnet, dass die Hauptdatei 3000 Blöcke enthält und
Indexdatei 10 Blöcke auf der ersten Ebene und 1 Block auf der zweiten Ebene.
-
Meine Vermutung ist, dass zwei Blöcke für die erste und zweite Ebene gelesen werden müssen und dann der Block in dem die 86 Datensätze enthalten sind plus eventuell ein weiterer Block falls die 86 Datensätze über Zwei Blöcke verteilt sind. richtig?
-
Mir ist klar dass das fast 3 Monate zu spät kommt, aber egal.
Ich kann die Lösung nicht nachvollziehen.
Ein Index ist normalerweise ein B-Baum (bzw. ein B-Baum Derivat).
Ein B-Baum hat üblicherweise genau einen Root-Block, d.h. der B-Baum für den Index müsste 3 Ebenen haben. Der Root-Block ist nötig, woher soll man sonst wissen mit welchem Key die Blöcke der "1. Ebene" (die eben in Wirklichkeit die 2. Ebene ist) anfangen.
D.h. wir müssen im Best-Case 3 Blöcke im Index lesen (einen pro Ebene, da sich 86 Index-Einträge ja noch in einem Leaf-Block ausgehen). Im Worst-Case müssten es mMn. 5 Blöcke sein, der Root-Block und je zwei Level-2 und Level-3 Blöcke (die 86 Index-Einträge könnten ja über zwei Level-2 Blöcke verteilt liegen).
D.h. alleine für den Index-Lookup kommen wir auf 3-5.Dann kommt noch der Table-Lookup dazu. Wenn wir davon ausgehen dass der Table sortiert ist, können das wieder 1-2 Pages sein. Wenn der Table nicht sortiert ist können es natürlich bis zu 86 sein.
Also kommen wir insgesamt auf 4-7. Bzw. 4-91 im nicht sortierten Table.
Die einzige Variante wie man mMn. auf 3-4 kommen kann, ist, wenn man nur wissen will wie viele Titel es sind (dann spart man sich nämlich den Table-Lookup, die Anzahl kann man ja aus dem Index alleine ermitteln), und man den Worst-Case Fall falsch berechnet. Nämlich den Fall wo man zwei Level 2 Blöcke braucht vernachlässigt, und nur den Fall betrachtet wo man auf Level 3 zwei Blöcke braucht.
ps:
Eine Variante wäre noch, dass der B-Tree keine Duplikate enthält, sondern pro eindeutigem Key nur einen Zeiger in den Table wo der erste Datensatz mit diesem Key steht. Dann lässt sich die Frage nicht so einfach bzw. nicht so genau beantworten, da wir dann die nötige Grösse des B-Baumes nicht mehr berechnen können. Je nachdem wie viel Duplikate es gibt könnte der ja kleiner bzw. grösser ausfallen.In dem Fall kommt deine Berechnung inetwa hin. Der einzige Fehler ist dann dass der Baum - vorausgesetzt es gibt wenig Duplikate - eben 3 Ebenen tief sein muss.
Die Antwort wäre dann fix 3 Blöcke im Index und 1-2 Blöcke im Table. Also in Summe 4-5 Blöcke.Auf 3-4 kann man nur kommen wenn man einen 2 Ebenen tiefen B-Baum ohne Duplikate annimmt. Was sich aus der Aufgabenstellung für mich aber nicht ableiten lässt.
ps2:
Hah. Vielleicht ist mit "mehrstufigem Primärindex" ein Clustered Index gemeint. Also dass die Tabelle selbst als B-Baum vorliegt.
In dem Fall kommen wir dann wieder auf 3 Ebenen. Die Antwort ist dann aber die selbe wie beim Index mit 3 Ebenen, nur ohne den Table-Zugriff. Also 3-5.
