Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!
5
Gegeben sei eine sequentielle Datei mit n = 100.000 Datensätzen, die auf einer Festplatte mit Blockgröße s=1024 Bytes gespeichert sind. Es darf angenommen werden, dass alle Datensätze fester Läge l=100 Bytes sind und Seitengrenzen nicht überschreiten.
Angenommen, dass das Suchschlüsselfeld (Sortierfeld) die Länge k=9 Bytes besitzt und dass ein Zeiger vom Index auf einen Block der Datei z=6 Bytes benötigt.
Wie viele Blockzugriffe benötigt eine binäre Suche auf diese Datei?
Wie viele Blockzugriffe werden zum Auffinden eines Datensatzes benötigt, wenn für die Datei ein dichter bzw. dünner Primärindex erzeugt wird?
Angenommen, dass das Suchschlüsselfeld (Sortierfeld) die Länge k=9 Bytes besitzt und dass ein Zeiger vom Index auf einen Block der Datei z=6 Bytes benötigt.
Wie viele Blockzugriffe benötigt eine binäre Suche auf diese Datei?
Wie viele Blockzugriffe werden zum Auffinden eines Datensatzes benötigt, wenn für die Datei ein dichter bzw. dünner Primärindex erzeugt wird?
Binär:
r=s/l (abgerundet) = 10 Datensätze pro Block
Anzahl der benötigten Blöcke ist b = n/r (aufgerundet) = 100.000/10 = 10.000
Eine binäre Suche benötigt log2(b) (aufgerundet) Zugriffe
log2(10.000) 14 Zugriffe
Dichter Index:
Größe eines Indexeintrages: 9+6 = 15
Indexeinträge 1024/15 = 68 Indexeinträge pro Block
Benötigte Blöcke = 100.000/68 (aufgerundet) = 1.471
log2(1.471) = 11 Zugriffe (aufgerundet)
Dünner Index:
100.000 Blöcke durch 68 Einträge (aufgerundet)
100.000/68 = 148
log2(148) = 8 Zugriffe (aufgerundet)
r=s/l (abgerundet) = 10 Datensätze pro Block
Anzahl der benötigten Blöcke ist b = n/r (aufgerundet) = 100.000/10 = 10.000
Eine binäre Suche benötigt log2(b) (aufgerundet) Zugriffe
log2(10.000) 14 Zugriffe
Dichter Index:
Größe eines Indexeintrages: 9+6 = 15
Indexeinträge 1024/15 = 68 Indexeinträge pro Block
Benötigte Blöcke = 100.000/68 (aufgerundet) = 1.471
log2(1.471) = 11 Zugriffe (aufgerundet)
Dünner Index:
100.000 Blöcke durch 68 Einträge (aufgerundet)
100.000/68 = 148
log2(148) = 8 Zugriffe (aufgerundet)
Karteninfo:
Autor: Der Kurssprecher
Oberthema: Datenbanken
Thema: Datenbanktechnik
Veröffentlicht: 14.04.2016