prev.png
up.png next_g.png
Aufgabe 2.4 (10 Punkte)
Es seien 1.000.000 Records zu verwalten, die jeweils 400 Bytes umfassen; inklusive eines 16-Byte-Schlüssels. 1 Block habe 4.096 Bytes.
Wie viele Blockzugriffe verursachen die Methoden
- Heap-Organisation
- Hash-Organisation
zur Ausführung eines LOOKUP im schlimmsten Fall?
Musterlösung vom 04.05.2009:
Ein Block hat 4.096 Bytes, d.h. ein Block umfasst 10 Datenrecords.
- Heap-Organisation
1.000.000 Datenrecords benötigen 100.000 Datenblöcke, wenn lediglich eingefügt wurde ohne zu löschen.
Durch sehr ungünstiges Löschen kann es passieren, dass jeder Block nur ein Record enthält.
D.h., der Aufwand für Lookup im schlimmsten
Fall beträgt 1.000.000 Blockzugriffe.
Da im Skript keine Angaben darüber gemacht werden, was mit Datenblöcken
passiert, die nach einem DELETE ganz leer sind, könnte man annehmen, dass
diese nicht gelöscht werden. Unter dieser Annahme, sind unendliche viele
Blockzugriffe der worst case...
- Hash-Organisation
Im schlimmsten Fall sind alle Records im selben Bucket, d.h.,
wenn nie gelöscht wurde, werden 100.000 Blockzugriffe benötigt.
Durch sehr ungünstiges Löschen kann es passieren, dass jeder Block nur ein Record enthält.
Dann werden schlimmstenfalls 1.000.000 Blockzugriffe benötigt.
Dazu kommen die Zugriffe auf das Bucket-Directory, welches ggfs. über mehrere Blöcke verteilt sein kann.
prev.png
up.png next_g.png