Wykład 8

Fizyczna organizacja danych w bazie danych

 

Streszczenie

Tematem wykładu jest model fizyczny bazy danych - w odróżnieniu od modelu logicznego rozważanego do tej pory. Dla większości użytkowników baz danych znajomość szczegółów technicznych organizacji baz danych w komputerze może nie jest istotna, po to został zresztą wprowadzony poziom logiczny bazy danych, jednakże ogólna orientacja w tym temacie jest pożądana. Umożliwia ona zrozumienie działania baz danych i ich uwarunkowań a co za tym idzie daje możliwość dostrojenia bazy danych w celu efektywniejszego jej działania. Jest więc nieodzowna dla osób administrujących systemami baz danych a przed wszystkim dla osób planujących zbudowanie własnego SZBD.

Zostaną rozważone takie zagadnienia jak: zarządzanie miejscem na dysku, zarządzanie obszarem buforów danych (w RAM) oraz organizacja zapisu rekordów na dysku. Inaczej mówiąc, zostanie opisane działanie modułów SZBD najniższego poziomu jak i wymagane struktury danych.

Zagadnienia budowy indeksów i wykonywania instrukcji SQL zostaną przedstawione na kolejnych wykładach.

 


8.1 Model fizyczny bazy danych

Do tej pory zajmowaliśmy się głównie problemami modelu logicznego bazy danych. Teraz przyszła pora rozważyć szczegóły implementacji modelu logicznego w komputerze czyli szczegóły modelu fizycznego bazy danych. Model ten ściśle zależy od bieżącej architektury systemów komputerowych. Wraz ze zmianami w architekturze model ten ulega i także w przyszłości będzie ulegał zmianom. Zakładamy, że czytelnik zna podstawy budowy współczesnych systemów komputerów w tym nośników przechowywania danych takich jak magnetyczne dyski. Szczegółami technicznymi budowy dysków nie będziemy się zajmować na tym wykładzie.

Model fizyczny bazy danych jest oparty na pojęciach pliku i rekorduPlik obiektu bazy danych (nazywany też segmentem tego obiektu) składa się z rekordów posiadających ten sam formatFormat rekordu jest listą nazw pól z określeniem ich typów danychRekord składa się z wartości poszczególnych pól. Niektóre pola są wyróżnione jako klucz wyszukiwania rekordu Może być więcej niż jeden klucz wyszukiwania rekordu. Na poziomie fizycznym nie wymaga się aby był określony jednoznaczny identyfikator (klucz) rekordu w pliku.

Podstawowymi operacjami na pliku, inicjowanymi przez programy aplikacyjne, są:

  1. Wstawianie - wstaw rekord do pliku.
  2. Usuwanie - usuń rekord z pliku.
  3. Modyfikacja - zmodyfikuj zawartość pól w rekordzie w pliku.
  4. Wyszukiwanie - znajdź w pliku rekord(y) z podaną wartością  klucza wyszukiwania lub spełniające podane warunki.

Zatem duża różnorodność operacji na bazie danych dostępnych za pomocą instrukcji języka SQL, sprowadza się do tylko czterech na poziomie fizycznym. Oczywiście operacje na słowniku danych również są wykonywane w ten sposób.

Trzeba tu podkreślić, że plik modelu fizycznego bazy danych może być reprezentowany przez plik dostępny w systemie plików komputera ale nie musi. Tak więc pojęcia pliku rekordów z danymi i pliku dyskowego nie są tożsame.

W szczególności plik dyskowy może obejmować kilka plików obiektów bazy danych.

Również w specjalnych przypadkach jeden obiekt bazy danych jest zapisywany w więcej niż jednym pliku dyskowym np. gdy tabela jest dzielona na partycje, które mogą być przetwarzane równolegle przez osobne procesy. Wtedy jednemu plikowi modelu fizycznego bazy danych odpowiada kilka plików dyskowych.

Dyski i pliki

Współczesne systemy zarządzania bazą danych przechowują dane na twardych (magnetycznych) dyskach. Aby wykonać operacje na danych, trzeba je najpierw zapisać w pamięci wewnętrznej RAM, wykonać na nich operacje a następnie przepisać wyniki na dysk. Stąd nieodzowność stosowania operacji We/Wy:

  1. Odczyt (READ): przesłanie danych z dysku do pamięci RAM.
  2. Zapis (WRITE): przesłanie danych z pamięci RAM na dysk.

Obie operacje są o rząd wielkości wolniejsze niż operacje w pamięci RAM – muszą być stosowane przez SZBD umiejętnie! Koszt operacji na bazie danych jest przedstawiany jako liczba operacji We/Wy.

Naturalne wydaje się pytanie - dlaczego danych nie można przechowywać w pamięci RAM? 

Pierwszym argumentem jest fakt, że pamięć RAM jest chwilowa. Po wyłączeniu komputera z prądu tracimy wszystkie dane. Można tu jednak argumentować, że nie trzeba komputera wyłączać z prądu a wszelkie awarie zasilania rozwiązywać za pomocą urządzenia UPS, które w chwili awarii może przepisać dane na trwały nośnik.

Drugim argumentem jest istotnie wyższy koszt pamięci RAM niż dysku (rzędu sto razy wyższy).

Trzecim, decydującym argumentem było do tej pory to, że stosowane we współczesnych komputerach 32 bitowe adresowanie ogranicza ilość danych, które można zapisać w pamięci RAM. Jednakże znajdujemy się już w trakcie przechodzenia na adresowanie 64 bitowe.

Powyższa dyskusja pokazuje, że w niedalekiej przyszłości możemy mieć do czynienia z nowym, alternatywnym modelem fizycznym bazy danych, w którym 99% danych w bazie danych jest dostępne w pamięci RAM). Na razie jednak jest faktem, że podstawowym nośnikiem przechowywania danych w bazie danych jest dysk magnetyczny.

 

Oprócz dysków używa się też obszerniejszych ale za to wolniejszych w dostępie nośników danych takich jak taśmy magnetyczne, dyski optyczne, CD ROMy. Służą one do przechowywania: kopii zabezpieczających bieżącej bazy danych (backup), dzienników transakcyjnych off-line oraz kopii archiwalnych danych.

Charakterystyka używania danych przechowywanych na dysku

  1. Dostęp swobodny (ang. random access): w oparciu o adres rekordu na dysku możemy go przesłać do pamięci RAM w jednej operacji We-Wy.
  2. Dane są przechowywane i przekazywane w jednostkach nazywanych blokami dyskowymi lub stronami.
  3. Inaczej niż w przypadku pamięci RAM, czas dostępu do danych na dysku zależy od ich położenia na dysku. Dlatego wzajemne rozmieszczenie stron na dysku może mieć  zasadniczy wpływ na szybkość działania SZBD! Najlepsze wyniki uzyskujemy przy operowaniu ciągami sąsiadujących ze sobą stron.
  4. Dąży się do tego, aby dane, które są często wykorzystywane przez programy aplikacyjne, na stałe przebywały w buforach pamięci RAM (tzw. cachowanie). Wraz z obniżaniem się kosztu pamięci RAM coraz więcej danych bazy danych rezyduje w pamięci RAM. Dostęp do nich jest wtedy bardzo szybki.
  5. Operacje odczytu i zapisu bloków na dysku mogą być realizowane współbieżnie. Stąd opłaca się aby transakcje użytkowników były realizowane przez system współbieżnie a nie sekwencyjnie. Również w ramach jednej transakcji rozkładając dane do różnych dysków można istotnie przyśpieszyć jej wykonanie.

Natomiast w przypadku magnetycznych taśm mamy do czynienia z  dostępem sekwencyjnym - dane są odczytywane jedna po drugiej od początku taśmy do jej końca jako jedna, długa operacja We-Wy. Zaletami taśm są duża pojemność i niski koszt. Są używane do archiwizowania i tworzenia kopii zabezpieczających (backup-ów).

 


8.2 Dyskowy model fizyczny bazy danych

W przypadku dysku jako podstawowego nośnika danych w bazie danych nasz ogólny model fizyczny ulega uzupełnieniu o strony dyskowe. Oto jego podsumowanie.

Tabela (relacja) jest reprezentowana przez plik (dyskowy). Plik składa się ze stron. Strona składa się z rekordów. Rekord składa się z pól.

Rys. 8.1 Porównanie pojęć poziomu logicznego i fizycznego

Ponadto:

  1. Gdy rozmiar rekordu jest większy niż rozmiar strony, rekord jest dzielony na części przechowywane na osobnych stronach - najlepiej sąsiadujących na dysku. (Ta cecha nie jest implementowana w każdym systemie SZBD. Jeśli nie jest implementowana projektant bazy danych musi to uwzględnić, dzieląc długie wiersze na części przechowywane albo w tej samej tabeli albo w różnych - np. część atrybutów umieszczamy w jednej tabeli część w drugiej.)

  2. Duże obiekty LOB są trzymane w osobnych obszarach przeznaczonych do ich przechowywania w bazie danych, zwykle jako ciąg sąsiednich stron. W rekordach z danymi znajdują się tylko ich lokalizatory.

  3. Gdy schemat dostępu do danych polega na użyciu powiązanych danych z dwóch lub więcej tabel (np. departamenty i ich pracownicy; zamówienia i pozycje zamówień), w jednym pliku są zbierane dane z kilku tabel w oparciu o wspólny klucz (np. numer departamentu czy identyfikator klienta) - mamy wtedy do czynienia z klastrem tabel.

Hierarchia nośników przechowywania danych w bazie danych

  1. Pamięć RAM dla danych używanych w bieżącej chwili.
  2. Dysk dla głównej bazy danych.
  3. Taśma dla archiwalnych wersji danych i backupu.

Rys. 8.2 Hierarchia nośników przechowywania danych w bazie danych

Te same dane np. rekord pracownika mogą się w tej samej chwili znajdować w trzech różnych miejscach! Co więcej mogą się zmieniać w jednym z nich (w pamięci RAM) powodując brak (chwilowy) synchronizacji. Na ogół zmiany są propagowane z pamięci RAM do dysku i następnie na pomocnicze nośniki danych. Ale są sytuacje, np. operacja ROLLBACK albo awaria serwera, gdy rekord zapisany na dysku lub na taśmie zastępuje rekord zapisany w pamięci RAM.

Przejdziemy teraz do omówienia podstawowych modułów SZBD realizujących operacje na stronach (nie odwołując się do rekordów), z których korzystają inne moduły SZBD. Są to: moduł zarządzania miejscem na dysku oraz moduł zarządzania buforami w pamięci RAM.
 


8.3 Zarządzanie miejscem na dysku

W pliku mamy dwa rodzaje stron:

Zakładamy także, że system ma możliwość rozszerzania pliku rekordów i alokacji nowych, pustych stron oraz że system ma możliwość zwrotu (dealokacji) nieużywanych stron.

Moduł zarządzania miejscem na dysku (ang. disk space manager) realizuje następujące funkcje:

  1. Alokacja ciągu stron (położonych spójnie na dysku).
  2. Zwrot (dealokacja strony).
  3. Wyznaczenie strony do zapisu nowego rekordu.
  4. Aktualizacja struktur danych na dysku związanych z przechowywanymi stronami.

Rozmiarem strony jest zwykle rozmiar bloku dyskowego i strony są przechowywane jako bloki dyskowe, więc odczyt/zapis strony wykonuje się jako pojedyncza operacja We/Wy.

Moduł zarządzający miejscem na dysku ukrywa szczegóły sprzętu i systemu operacyjnego i umożliwia pozostałym modułom traktowanie danych na dysku jako zbioru stron.
 


8.4 Zarządzanie buforami danych (w RAM)

Moduł zarządzania buforami danych (ang. buffer manager) jest odpowiedzialny za sprowadzanie stron z dysku do puli buforów danych w pamięci RAM. Dane muszą być umieszczone w buforach danych aby procesy SZBD mogły na nich operować! Zapis strony odbywa się w ramce (ang. frame).

Rys. 8.3 Pula ramek

Oprócz puli ramek w pamięci RAM są przechowywane:

Ponadto wszystkie ramki, których licznik odwołań = 0, tworzą listę wolnych ramek (czasami lista ta jest tworzona z opóźnieniem).

Moduł zarządzania buforami danych jest wykorzystywany przez procesy SZBD - przede wszystkim przez procesy realizujące zlecenia użytkowników. Oto szkic jego działania.

Gdy procesowi jest potrzebna strona wykonywany jest algorytm:

  1. Gdy potrzebnej strony nie ma w puli ramek:
  2. Gdy potrzebna strona jest w puli ramek, zwiększ jej licznik odwołań o jeden.
  3. Przekaż procesowi wskaźnik do ramki ze stroną.
  4. Jeśli można z góry przewidzieć, że mają być sprowadzone sąsiadujące na dysku strony np. przy przeglądaniu sekwencyjnym pliku, sprowadź od razu kilka stron!

Gdy zmienia się zawartość ramki:

Strona w buforze danych może być potrzebna wielu procesom:

Z jednej ramki w pamięci RAM może korzystać współbieżnie wiele procesów. Sposób korzystania jest określony przez specjalne procedury, o których będzie mowa w wykładzie o transakcjach.

Strategie zastępowania stron w ramkach z listy wolnych ramek

Strona jest na liście wolnych ramek gdy jej licznik odwołań jest równy 0. Stosowane są następujące strategie wyboru ramki do zastąpienia:

  1. LRU – zastępuje się stronę, która najdłużej była nie używana,
  2. MRU – zastępuje się stronę, która ostatnio była używana,
  3. Clock - ustala się stałą, cykliczną kolejność pobierania wolnych ramek.

Wydawałoby się, że strategia LRU powinna być zawsze najlepsza. Okazuje się, jak pokazuje poniższy przykład, że nie jest tak zawsze.

Zjawisko sekwencyjnego zalewania puli ramek:

Stosując strategię LRU powtarzamy wielokrotnie sekwencyjne przeglądanie pliku. Gdy #ramek < #stron w pliku, wtedy każde żądanie strony powoduje operację We/Wy.

Strategia polegająca na wczytaniu najpierw #ramek stron do pamięci RAM, a następnie stosowaniu strategii MRU byłaby lepsza w tym przypadku. Część stron równa #ramek–1 pozostawałaby cały czas w puli buforów, natomiast pozostałe strony wczytywane byłyby kolejno do jednej z ramek.

Podobnie jeśli podejrzewamy, że wczytywane strony nie będą używane w najbliższym czasie, a tak możemy wnioskować w przypadku przeglądania wierszy dużej tabeli, nie opłaca się zastępować stron z rekordami, które są często używane przez strony pochodzące z pełnego przejrzenia wierszy dużej tabeli.

W praktyce proces wykonujący zlecenie użytkownika może posiadać informacje, że pewne strony będą często używane i w związku z tym należy je na stałe przechowywać w buforach w pamięci RAM. Komercyjne SZBD w większości realizują taką możliwość.

W stosowanych serwerach wzrastają rozmiary pamięci RAM i w związku z tym także rośnie liczba buforów danych. Wielokrotnie używane strony powinny więc być stale przechowywane w buforach. Gdy baza danych jest używana przez aplikację biznesową, przyjmuje się, że średnio co najmniej 90% potrzebnych do wykonania zapytania danych powinno znajdować się w buforach. Ponadto, jest potrzebny niezależny proces serwera bazy danych, który będzie regularnie synchronizował zawartości stron w buforach z tymi na dysku.

Obsługa wskaźników

W modelu obiektowo-relacyjnym jak i przy implementacji modelu relacyjnego (np. przy indeksach) występują wartości, które są wskaźnikami do rekordów (wierszy,  obiektów). Wskaźniki są reprezentowane przez adresy obiektów składowanych na dysku. Gdy obiekty zostają zapisane w buforach, jest możliwość przemiany adresów dyskowych na adresy pamięci RAM (ang. pointer swizzling). Przetwarzanie takich obiektów staje się szybsze. Przy zapisie obiektu na dysk jest konieczna transformacja odwrotna adresów pamięci RAM na adresy dyskowe. Potrzebna jest więc tabela odwzorowująca wzajemnie adresy obiektów na dysku i w pamięci.
 


8.5 Formaty rekordów i stron

Gdy użytkownik potrzebuje konkretnego rekordu z bazy danych, proces obsługujący zlecenie użytkownika:

  1. najpierw oblicza adres strony, na której znajduje się dany rekord,
  2. następnie sprowadza stronę z dysku i umieszcza ją w buforze pamięci RAM (przy tych operacjach są wywoływane moduły zarządzania miejscem na dysku i zarządzania buforami w pamięci RAM),
  3. po czym wydobywa z niej szukany rekord i przekazuje go użytkownikowi.

W punkcie 3 jest potrzebna znajomość struktur zapisu: pól w ramach rekordu i rekordów na stronie. Omówimy je w tej chwili.

Liczba i typy pól są zwykle takie same dla wszystkich rekordów w pliku; są zapisane w słowniku danych (katalogu systemowym). Jest kilka alternatywnych formatów zapisu pól w ramach rekordu.

Format rekordu: stała długość pól

Zapis rekordu składa się ze spójnego obszaru zawierającego ciąg pól P1,...,Pn o stałych rozmiarach D1,...,Dn. Mając adres bazowy (początek rekordu) B łatwo można obliczyć początek i-tego pola jako B+D1+...+Di-1.

Rys. 8.4 Zapis rekordu stałej długości

Format rekordu: zmienna długość pól

Istnieją dwa alternatywne formaty (przy założeniu, że liczba pól jest stała). W pierwszym przypadku, rozdzielamy pola za pomocą specjalnego separatora np. symbolu '$'. W drugim przypadku, na początku zapisu rekordu umieszczamy tablicę wskaźników (offsetów) do początków kolejnych pól.

Rys. 8.5 Zapis rekordu zmiennej długości

W drugim przypadku uzyskujemy:

Powyższą strukturę danych można rozszerzyć do przypadku, gdy liczba pól jest zmienna – ale ich typ jest określony statycznie w słowniku danych (katalogu systemowym). Mianowicie przed katalogiem wskaźników do pól umieszczamy liczbę pól w bieżącym rekordzie (czyli rozmiar tablicy offsetów). Nie trzeba wtedy reprezentować pól na końcu rekordu nie mających ustalonych wartości, czyli będących Null.

Z kolei rozpatrzymy formaty zapisu rekordów w ramach strony

Format strony dla rekordów stałej długości

Istnieją dwa alternatywne formaty. W obu przypadkach zapis strony składa się z ciągu miejsc, w każdym z nich albo jest zapisany rekord albo miejsce jest wolne. W pierwszym przypadku, najpierw są zgrupowane wszystkie miejsca zajęte, a następnie wolne. W drugim przypadku, miejsca wolne i zajęte są ze sobą przemieszane - to czy dane miejsce jest wolne czy zajęte wskazuje bit w dodatkowej tablicy Occupied:

    Occupied(i)=1 wtedy i tylko wtedy, gdy i-te miejsce na stronie jest zajęte.

Rys. 8.6 Zapis rekordów stałej długości

Przy operowaniu na danych pojawia się potrzeba sięgania do konkretnych rekordów, a nie do wszystkich za każdym razem np. sięgamy do rekordu w oparciu o jego wcześniej wyliczony adres bądź poprzez jego adres znaleziony w indeksie.

Adres rekordu czyli identyfikator rekordu rid, identyfikujący jego położenie na dysku, jest określany następująco:

rid = <id_strony, numer pozycji na stronie>

W przypadku pierwszej struktury przesuwanie rekordów na stronie  powoduje zmianę identyfikatora rekordu, co komplikuje odwołania do rekordu przez jego identyfikator rid. W przypadku drugiej struktury rekord nie jest przesuwany na stronie, nie zmienia się więc jego identyfikator.

Format strony dla rekordów zmiennej długości

W przypadku rekordów zmiennej długości adres zapisu rekordu na stronie jest określony przez wartość w tablicy pozycji Poz. Wartość Poz(i) wskazuje na początek zapisu i-tego rekordu, 1<= i <= N. Dodatkowo, wartość Poz(-1) wskazuje na początek obszaru wolnych miejsc a wartość Poz(0) jest równa N tj. maksymalnej liczbie rekordów na stronie.

Rys. 8.7 Zapis rekordów zmiennej długości

Adres rekordu czyli identyfikator rekordu rid, identyfikujący jego położenie na dysku, jest określany następująco:

rid = <id_strony, numer pozycji i w tablicy Poz>

Gdy przesuwamy i-ty rekord na stronie, jego nowy adres na stronie aktualizujemy w Poz(i). Nie zmienia to indeksu i a zatem nie zmienia także identyfikatora rekordu rid.

Natomiast przy przenoszeniu rekordu na inną stronę, identyfikator rekordu zmienia się. Gdy tego rodzaju operacje są przewidywane, trzeba to uwzględnić w strukturze danych:

Na stronie dyskowej są zapisywane także dodatkowe informacje jak informacje o transakcjach, które aktualnie wykonują operacje na rekordach przechowywanych na danej stronie oraz informacje o powiązaniach między stronami w ramach struktury danych pliku rekordów (o tym za chwilę).
 


8.6 Pliki rekordów

Plik stanowi kolekcję stron, z których każda zawiera zero, jeden lub więcej rekordów. Jak wiemy, na pliku są wykonywane następujące rodzaje operacji:

  1. wstawianie/usuwanie/modyfikowanie rekordu (o podanym rid),
  2. odczytywanie konkretnego rekordu (o podanym rid),
  3. wyszukiwanie wszystkich rekordów spełniających podane warunki.

Jest możliwe kilka organizacji pliku rekordów. Podstawowa różnica między nimi polega na tym, czy porządkują one rekordy według wartości pewnego klucza czy nie. Najpierw rozważymy dwie organizacje zapisu nieuporządkowanego (nazywanego potocznie stertą ang. heap).

Plik nieuporządkowany

  1. Rekordy są przechowywane na stronach pliku w dowolnym porządku.
  2. Nowy rekord jest wstawiany do pierwszej strony, na której jest wolne miejsce.
  3. Przy wyszukiwaniu w oparciu o pewien klucz przechodzimy po wszystkich stronach do chwili napotkania szukanego rekordu albo do końca pliku, gdy rekordu nie ma w pliku.

Organizacja nieuporządkowana jest wygodna przy wykonywaniu zapytań dotyczących wszystkich rekordów lub większości rekordów np.

    SELECT * FROM Emp;

lub

    SELECT * FROM Emp e WHERE e.Sal > 1000;

gdy wiemy, że większość pracowników zarabia powyżej 1000.

Plik nieuporządkowany w wersji dwie listy

Rys. 8.8 Zapis pliku w postaci dwóch list

Na jednej liście trzymane są strony z wolnymi miejscami do wstawienia nowych rekordów; na drugiej liście są trzymane strony bez wolnego miejsca do wstawienia nowych rekordów.

Plik nieuporządkowany w wersji katalogu stron

Rys. 8.9 Zapis pliku w postaci katalogu stron

Stan zajętości stron jest zapisywany w osobnym katalogu.

Przy wpisywaniu nowego rekordu, najpierw wybieramy w katalogu stronę z wolnym miejscem, ściągamy ją i wpisujemy rekord.

Alternatywne w stosunku do pliku nieuporządkowanego organizacje zapisu polegają na zachowaniu pewnego ustalonego porządku względem klucza rekordu. Przedstawimy dwa rozwiązania: plik posortowany i plik haszowany.

Plik posortowany

Rekordy są zapisywane na kolejnych stronach zgodnie z porządkiem względem pewnego ustalonego klucza rekordu. Taka reprezentacja jest wygodna gdy rekordy przetwarza się zawsze w pewnym, ustalonym porządku lub tylko pewien ich zakres względem tego porządku np.

    SELECT * FROM Emp e ORDER BY e.Sal;

lub

    SELECT * FROM Emp e WHERE e.Sal BETWEEN 1000 and 2000;

W pliku posortowanym wyszukanie rekordu mając dany jego klucz jest nieco szybsze niż dla pliku nieuporządkowanego, ale ze względu na to, że rekordy znajdują się na dysku, zastosowanie jednej z szybkich metod wyszukiwania jak wyszukiwanie binarne nie jest w pełni możliwe.

Są możliwe dwie implementacje:

1. Pełny ekstent – bloków sąsiadujących ze sobą na dysku – rekordy są uporządkowane według wartości klucza. Jest problem ze wstawieniem nowego rekordu lub usunięciem rekordu z pliku. Jest za to możliwość zastosowania wyszukiwania binarnego.

Rys. 8.10 Plik posortowany w postaci pełnego ekstentu

2. Lista bloków (lub ekstentów) – rekordy są uporządkowane według wartości klucza ale kolejne bloki na liście nie muszą być sąsiednie. Nie ma problemu ze wstawieniem nowego rekordu i usunięciem rekordu z pliku. Bezpośrednio nie ma możliwości zastosowania wyszukiwania binarnego - potrzebna jest więc dodatkowa struktura danych wykorzystująca posortowanie danych (struktura indeksowa - temat ten zostanie omówiony na kolejnym wykładzie).

Rys. 8.11 Plik posortowany w postaci listy

W obu powyższych metodach, rekordy o tej samej wartości klucza lub zbliżonej znajdują się na tej samej stronie lub tylko na kilku stronach dyskowych (w pierwszej metodzie nawet na sąsiednich). Jest to istotne przy wyszukiwaniu, gdyż wyznaczenie wszystkich rekordów o danej wartości klucza (lub o wartości zbliżonej) wymaga sprowadzenia jednej lub co najwyżej tylko kilku stron, a nie dla każdego rekordu osobnej strony.

Plik haszowany

Plik haszowany jest kolekcją segmentów (ang. bucket) rekordów. Segment jest to strona główna plus zero lub więcej stron nadmiarowych alokowanych do segmentu w razie potrzeby. Przydział rekordu do segmentu odbywa się w oparciu o wartość funkcji nazywanej funkcją haszującą (mieszającą) zastosowanej do klucza wyszukiwania rekordu, którym jest jedno lub więcej pól rekordu. Mianowicie:

Funkcja haszująca h: h(klucz wyszukiwania rekordu r) = adres segmentu do którego wpada rekord r.

 

Rys. 8.12 Plik haszowany

Przy tej metodzie, rekordy o tej samej wartości klucza znajdują się na tej samej stronie lub tylko na kilku stronach dyskowych. Jest to istotne przy wyszukiwaniu, gdyż wyznaczenie wszystkich rekordów o danej wartości klucza wymaga sprowadzenia tylko kilku stron, a nie dla każdego rekordu osobnej strony.

Organizacja pliku haszowanego jest użyteczna przy wyborze rekordu z pliku w oparciu o wartość lub wartości pewnych pól rekordu np. przy wykonywaniu zapytania:

SELECT * FROM Emp e WHERE e.Ename=:Nazwisko;

Natomiast organizacja rekordów w pliku haszowanym nie zachowuje kolejności względem wartości klucza wyszukiwania.

Zastosowanie jednej organizacji rekordów w pliku zazwyczaj nie wystarcza w aplikacjach baz danych, w których wyszukiwanie odbywa się względem wartości różnych kluczy wyszukiwania. Rozwiązanie tego problemu polega na skorzystaniu z osobnych struktur indeksowych. Ich studiowanie rozpoczniemy  na następnym wykładzie.
 


8.7 Podsumowanie

W wykładzie tym czytelnik poznał podstawy fizycznego modelu bazy danych opartego na pojęciach pliku, strony, rekordu i buforu danych. Treścią kolejnych wykładów będą zasady funkcjonowania SZBD na gruncie przedstawionego modelu.

Podstawowe dwa moduły niskiego poziomu zasłaniające moduły wysokiego poziomu od szczegółów implementacyjnych modelu fizycznego to moduł zarządzania miejscem na dysku (ang. Disk Space Manager) oraz moduł zarządzania buforami w pamięci RAM (ang. Buffer Manager).

 


8.8 Słownik pojęć

model fizyczny bazy danych - reprezentacja tabel w terminach struktur przechowywania danych w komputerze. Podstawowy dyskowy model fizyczny jest następujący: tabela jest reprezentowana przez plik (dyskowy);  plik składa się ze stron, strona składa się z rekordów, rekord składa się z pól.

plik - reprezentacja tabeli w modelu fizycznym bazy danych.

rekord - fizyczna reprezentacja wiersza.

pole - reprezentacja wartości w kolumnie (elementu wiersza) w modelu fizycznym bazy danych.

klucz rekordu - pole lub pola rekordu, których wartości jednoznacznie determinują cały rekord. Jeśli jest więcej niż jeden klucz rekordu, jeden z nich wybieramy jako główny.

strona (blok) - fizyczna jednostka przechowywania danych na dysku. Dane są przesyłane między pamięcią wewnętrzną i dyskiem stronami. Na jednej stronie mieści się pewna liczba rekordów.

bufor danych - miejsce w pamięci RAM, do którego sprowadza się stronę z dysku.

LRU - podstawowa strategia zastępowania stron w puli buforów danych; mianowicie zastępuje się stronę, która najdłużej pozostawała nie używana.

plik nieuporządkowany (heap) - plik, w którym rekordy są przechowywane na stronach w dowolnym porządku.

plik posortowany - plik, w którym rekordy są zapisywane na kolejnych stronach zgodnie z porządkiem względem klucza rekordu.

plik haszowany - plik, który jest kolekcją segmentów. Podział rekordów na segmenty odbywa się w oparciu o wartość funkcji, nazywanej funkcją haszującą, zastosowaną do klucza rekordu.

funkcja haszująca - funkcja, która wartościom klucza wyszukiwania,  przyporządkowuje adres segmentu w pliku haszowanym.
 


8.9 Sprawdzenie wiedzy

  1. Na jakich pojęciach jest oparty fizyczny model bazy danych?

    plik
    tabela
    rekord
    wiersz
    perspektywa

  2. Zawartości strony na dysku i w puli buforów:

    muszą zawsze być takie same
    mogą być różne
    mogą być takie same

  3. Przemiana adresów (ang. pointer swizzling) w rekordach dotyczy:

    zmiany adresów dyskowych na adresy pamięci RAM
    zmiany adresów dyskowych rekordów przy ich przepisaniu w inne miejsce na dysku

  4. Format strony dla rekordów zmiennej długości umożliwia:

    Przesuwanie rekordów na stronie bez zmiany ich identyfikatorów.
    Przesuwanie rekordów między stronami bez zmiany ich identyfikatorów.
    Umożliwia stosowanie wskaźników z zewnątrz do rekordu.

  5. Zarządzanie wolnym miejscem na stronach jest realizowane za pomocą:

    sortowania stron
    dwóch list stron
    katalogu stron

  6. Która strategia zastępowania stron w ramkach z listy wolnych ramek jest przyjmowana jako domyślna:

    zastępuje się stronę, która najdłużej była nie używana
    zastępuje się stronę, która ostatnio była używana
    ustala się stałą, cykliczną kolejność pobierania wolnych ramek
    następuje losowanie ramki z listy wolnych ramek

  7. W pliku haszowanym rekordy są zapisywane:

    w kolejności uporządkowanej względem klucza rekordów
    w podziale na segmenty względem wartości funkcji haszującej
    w dowolnym porządku
    w kolejności podanej przez użytkownika

  8. Co jest prawdą dla posortowanego pliku rekordów w wersji listowej:

    Rekordy o tej samej wartości klucza lub zbliżonej znajdują się na tej samej stronie lub tylko na kilku stronach dyskowych.
    Łatwo zastosować wyszukiwanie binarne.
    Łatwo wstawić nowy rekord znając miejsce w pliku rekordów.
    Łatwo usunąć rekord.

 


8.10 Zadania

1. Opracuj struktury danych dla modułu zarządzającego stronami i zaprogramuj go.

2. Opracuj struktury danych dla modułu zarządzającego buforami i zaprogramuj go.

3. Zaimplementuj strukturę danych pliku nieuporządkowanego w wersji dwie listy i zaprogramuj operacje wstawiania, usuwania, modyfikacji i wyszukiwania rekordu.

4. Zaimplementuj strukturę danych pliku nieuporządkowanego w wersji katalogu i zaprogramuj operacje wstawiania, usuwania, modyfikacji i wyszukiwania rekordu.

5. Zaimplementuj strukturę danych pliku posortowanego w wersji listy stron i zaprogramuj operacje wstawiania, usuwania, modyfikacji i wyszukiwania rekordu.

6. Zaimplementuj strukturę danych pliku haszowanego i zaprogramuj operacje wstawiania, usuwania, modyfikacji i wyszukiwania rekordu.

 



Strona przygotowana przez Lecha Banachowskiego - 07/24/06 .