BD-2st-1.2-w06.tresc-1.1-Slajd15

From Studia Informatyczne

Plik nieuporządkowany - operacje (1)

Plik nieuporządkowany - operacje (1)


Podstawową organizacją pliku nieuporządkowanego jest stóg (ang. heap).

W przypadku operacji wstawiania rekordu, rekord trafia do ostatniego bloku pliku. Przed wstawieniem, blok ten musi zostać odczytany z dysku do bufora pamięci operacyjnej. Tu rekord jest wstawiany i blok ten jest z powrotem zapisywany na dysk. W konsekwencji, koszt wstawienia rekordu wynosi 2D+C. Składnik 2D to odczyt ostatniego bloku z dysku i jego ponowny zapis. C to koszt przetworzenia rekordu w buforze.

W przypadku operacji wyszukania rekordu spełniającego wskazane kryterium, zachodzi konieczność liniowego przeszukiwania wszystkich bloków. Średni koszt liniowego przeszukania jest wyrażony wzorem nr 1 ze slajdu ( 0.5N(D+RC) ). Średnio, odszukanie rekordu wymaga odczytu połowy bloków - stąd składnik kosztu 0.5ND. Odczytane rekordy są następnie przetwarzane w buforze (sprawdzane jest czy rekordy spełniają kryterium poszukiwania), stąd składnik kosztu 0.5NRC.

W przypadku najgorszym, tj. albo jeżeli nie ma rekordów spełniających warunek selekcji albo poszukiwane rekordy znajdują się w ostatnim bloku, system musi przejrzeć cały plik. W tym przypadku koszt jest wyrażony wzorem nr 2 ( N(D+RC) ).


<< Poprzedni slajd | Spis treści | Następny slajd >>