Wstęp do baz danych


Struktury plików dla metod szeregowego dostępu



Pobieranie 8.37 Mb.
Strona35/97
Data29.10.2017
Rozmiar8.37 Mb.
1   ...   31   32   33   34   35   36   37   38   ...   97

Struktury plików dla metod szeregowego dostępu


Te metody opracowane były głównie dla plików przechowywanych na urządzeniach pamięci z dostępem szeregowym (sekwencyjnym) – np. taśmach magnetycznych.

W takich urządzeniach w celu otrzymania dostępu do fizycznego elementu rekordu trzeba „przewinąć” wszystkie umieszczone przed nim elementy.

Na urządzeniach z bezpośrednim dostępem (z dowolnym typem adresacji) istnieje możliwość umieszczenia głowic odczytu-zapisu w dowolne miejsce prawie natychmiast. Jednak czas ustawienia głowicy nie jest równy zero, a jest, po prostu, bardzo mały w porównaniu do czasu odczytania-zapisu.

W systemach plików z dostępem szeregowym (sekwencyjnym) cała pamięć fizyczna przedstawia się jako szereg elementów informacyjnych (stronic fizycznych lub rekordów plików). Pliki z szeregowym dostępem mają dwa typy rekordów: ze stałą długością i zmienną długością.

Dla plików ze stałą długością rekordów adres umieszczenia rekordu z numerem K może być obliczony według wzoru:

NK =BA + (K-1) * LZ +1,

Gdzie NK – wyszukiwany adres umieszczenia rekordu z numerem K,

BA - adres początku pliku,

LZ – długość rekordu.

W plikach ze zmienną długością rekordów każdy z nich może mieć dowolną długość z określonego przydziału. Żeby odnaleźć następny zapis w takich plikach korzystają z jednego ze sposobów:

1. Koniec każdego rekordu zaznaczany jest markerem – szeregiem specjalnych symboli, wykorzystywanych tylko dla tego celu.

2. Długość bieżącego rekordu jest znajduje się na początku każdego zapisu w określonym polu.

Pliki z różnymi długościami rekordów zawsze są plikami tylko z dostępem szeregowym.

Pliki ze stalą długością rekordów, umieszczone na urządzeniach pamięci bezpośredniego (dowolnego) dostępu, są plikami bezpośredniego dostępu.

Pliki ze stałą długością rekordów mogą się znajdować na urządzeniach pamięci tak z dostępem bezpośrednim (dowolnym), jak i z dostępem szeregowym (sekwencyjnym).

Pliki z różną długością rekordów zawsze są umieszczane na taśmach magnetycznych lub strimmerach.

Niech jest zadany schemat relacji R (Sno, FName, Lname, Address, Tel_No, Position, Sex, DOB, Salary, Bno), przy czym każda strona fizyczna pliku (rys.34) może zawierać kilka rekordów tablicy bazy danych. Liczba tych rekordów nie jest stała. Rekordy są posortowane według atrybutu kluczowego Sno. Spróbujemy opracować następujące zapytanie SQL:

SELECT *

FROM STAFF

WHERE Sno = ‘SG37’;

W celu poszukiwania rekordu w plikach z dostępem szeregowym stosuje się dwa rodzaje przeszukiwania: liniowe i binarne.

W przeszukiwaniu liniowym w celu odnalezienia niezbędnego rekordu trzeba wykonać sekwencyjne odczytanie kluczy kolejnych rekordów pliku, zaczynając od pierwszego, aż do odnalezienia rekordu z odpowiednim kluczem (‘SG37’ w naszym przypadku).

Dlatego zazwyczaj stosuje się przeszukiwanie binarne pozwalające zmniejszyć ilość operacji sprawdzenia (porównania) kluczy w rekordach z N do log2N (w najgorszym przypadku), gdzie N – ilość rekordów w pliku.



Algorytm przeszukiwania binarnego dla plików z dostępem szeregowym.

Algorytm zawiera następne iteracyjne kroki.

  1. Z początku włączamy do zbioru stron wszystkie strony fizyczne pliku, które zawierają rekordy logiczne i muszą być uporządkowane (posortowane) według wartości kluczy.

  2. Określamy i odczytujemy środkową stronę fizyczną wśród istniejących w zbiorze stron.

  3. Porównujemy klucz poszukiwanego rekordu logicznego ze wszystkimi kluczami rekordów logicznych znajdujących się na tej stronie. Jeśli rekord został odnaleziony - kończymy algorytm. Inaczej przechodzimy do p.4.

  4. Jeśli wartość klucza pierwszego rekordu strony fizycznej jest większą od wartości klucza poszukiwanego, to znaczy, że ten rekord logiczny znajduje się na poprzednich stronach fizycznych zbioru. W tym przypadku do zbioru stron włączamy tylko poprzednie strony fizyczne. Jeśli wartość klucza ostatniego na stronie rekordu jest mniejsza od wartości klucza poszukiwanego, to oznacza, że ten rekord logiczny jest umieszczony na następnych stronach fizycznych zbioru. W tym przypadku do zbioru stron włączamy tylko następne strony fizyczne. Przejście do p.2.

Przykład przeszukiwania binarnego w pliku z dostępem szeregowym i przedstawionym wcześniej zapytaniu SQL pokazany jest na rys.43. Tu umownie pokazano 6 stronic pamięci fizycznej, każda z których zawiera jeden rekord.



Najpierw odczytana jest zawartość stronicy 3 (ona jest środkową). Wartość pola kluczowego rekordu znajdującego na tej stronicy jest mniejsza od wzorca ‘SG37’. Dlatego na następnej iteracji przeszukiwanie wzorca odbywa się tylko na stronicach 4,5 i 6. Następnie odczytywana jest zawartość stronicy 5 (ona jest środkową wśród pozostałych). Potrzebny rekord odnaleziony zostanie na iteracji trzeciej.




Wady metod dostępu szeregowego:

  1. Wstawienie nowych rekordów wymaga reorganizacji całego pliku - zapis starych rekordów na inne miejsca, a nawet na inne stronice, ponieważ na odpowiedniej stronicy może nie okazać się miejsca na nowy rekord.

  2. Usunięcie rekordów powoduje powstanie „dziur”, co też wymaga reorganizacji całego pliku.

W celu usunięcia pierwszej wady stosuje się tymczasowy nieposortowany plik przepełnienia (overlflow file) nazywany również plikiem tranzakcji (transaction file). W tym przypadku wszystkie operacje wstawienia nowych rekordów wykonują się w tym pliku, zawartość którego okresowo zostaje przekopiowana do pliku głównego. Wtedy operacje dodania nowych rekordów wykonuje się bardziej efektywnie, jednak więcej czasu potrzebuje operacja przeszukiwania. Jeśli rekord nie zostaje odnaleziony podczas przeszukiwania binarnego w posortowanym pliku, trzeba kontynuować przeszukiwanie (już tylko liniowe!) w pliku transakcji. Również po usunięciu rekordu trzeba reorganizować cały plik transakcji.

Pliki z dostępem szeregowym rzadko stosują się dla przechowania tablic bazy danych, wyłączając pliki z indeksem pierwotnym ( o tym będzie powiedziano niżej). One mogą być wykorzystane dla tworzenia plików indeksowanych zawierających klucze pierwotne tablic. Pliki te przechowywane zazwyczaj są w buforach pamięci operacyjnej.





Pobieranie 8.37 Mb.

Share with your friends:
1   ...   31   32   33   34   35   36   37   38   ...   97




©operacji.org 2020
wyślij wiadomość

    Strona główna
warunków zamówienia
istotnych warunków
przedmiotu zamówienia
wyboru operacji
Specyfikacja istotnych
produktu leczniczego
oceny operacji
rozwoju lokalnego
strategii rozwoju
kierowanego przez
specyfikacja istotnych
Nazwa przedmiotu
Karta oceny
ramach działania
przez społeczno
obszary wiejskie
dofinansowanie projektu
lokalnego kierowanego
Europa inwestująca
Regulamin organizacyjny
przetargu nieograniczonego
kryteria wyboru
Kryteria wyboru
Lokalne kryteria
Zapytanie ofertowe
Informacja prasowa
nazwa produktu
Program nauczania
Instrukcja obsługi
zamówienia publicznego
Komunikat prasowy
programu operacyjnego
udzielenie zamówienia
realizacji operacji
opieki zdrowotnej
przyznanie pomocy
ramach strategii
Karta kwalifikacyjna
oceny zgodno
Specyfikacja techniczna
Instrukcja wypełniania
Wymagania edukacyjne
Regulamin konkursu
lokalnych kryteriów
strategia rozwoju
sprawozdania finansowego
ramach programu
ramach poddziałania
kryteriów wyboru
operacji przez
trybie przetargu