ullman010 (2)

26 . DZIEDZINA SYSTEMÓW RAZ DANYCH

jące przy projektowaniu DBMS. przeznaczonych do obsługi wielkich zasobów danych i szybkiego przetwarzania zapytań. Jednak technologia implementowania DBMS nic jest tematem wiodącym w naszej książce, dlatego też skoncentrujemy uwagę na tym, w jaki sposób projektować bazy danych i korzystać z nich w efektywny sposób.

1.2.1. Przegląd składowych systemu DBMS

Na rysunku 1.1 przedstawiono najbardziej istotne fragmenty DBMS. Na samym dole widzimy element reprezentujący miejsce składowania danych. Zauważmy, że ten element służy nie tylko do zapisu danych, ale także meta-danych, które opisują strukturę danych. Na przykład, jeśli rozważany DBMS jest relacyjny, to metadane obejmują nazwy relacji, nazwy atrybutów relacji i typy poszczególnych atrybutów (np. całkowity lub znakowy o długości nie większej niż 20).

RYSUNKK 1.1

Główne elementy systemu DBMS

Często system DBMS obsługuje indeksy danych. Indeks jest taką strukturą danych, która pomaga w szybkim odnajdywaniu właściwych danych, a posługuje się przy tym ich wartościami; najbardziej popularny pr/.yklad indeksu umożliwia odnalezienie właściwej krotki relacji, mającej zadane wartości pewnych atrybutów. Na przykład relacja obejmująca numery kont i bilans może mieć indeks założony na numerach kont. wówczas odnalezienie bilansu koma o podanym numerze odbywa się błyskawicznie. Indeksy są przechowywane razem z danymi, a informacja o tym, który atry but ma założone indeksy, należy do metadanych.

Jak są zaimplementowane indeksy

Z wykładu dotyczącego struktur danych Czytelnicy zapewne dowiedzieli się, że bardzo skutecznym sposobem tworzenia indeksu są tablice haszo-wania. Były one szeroko stosowane we wczesnych systemach DBMS. Obecnie najbardziej rozpowszechnioną strukturą danych są B-drzewa, gdzie ,,B” oznacza „balanced - zrównoważony”. B-drzewo stanowi uogólnienie zrównoważonego binarnego drzewa przeszukiwań. Różnica polega na tym, że każdy wierzchołek drzewa binarnego ma co najwyżej dwóch potomków, a wierzchołki B-drzewa mogą mieć ich więcej. 7. założenia B--drzewo jest zapisywane na dysku, zamiast w pamięci operacyjnej, i jest tak projektowane, aby jeden wierzchołek zajmował cały jeden blok na dysku. Ponieważ w typowym systemie bloki dyskowe zajmują około 2^:" bajtów (4096 bajtów), więc daje to sposobność zapisania setek wskaźników do potomków w jednym bloku B-drzewa. Stąd też przeszukiwanie B-drzewa rzadko kiedy wymaga więcej niż trzech dostępów do dysku.

Rzeczywisty koszt przeszukiwania dysku w zasadzie jest proporcjonalny do liczby dostępów do dysku. Stąd też przeszukiwania B-drzewa, które zwykle polegają na sprawdzeniu trzech bloków na dysku, są znacznie bardziej wydajne niż przeszukiwania drzew binarnych, które wymagają zazwyczaj odszukania wierzchołków znajdujących się w wiciu rożnych blokach na dysku. Różnica między B-drzewami a drzewami binarnymi jest jednym z wiciu przykładów tego, żc struktur)' danych bardzo odpowiednie dla danych przechowywanych na dysku są zupełnie inne niż struktury danych używane w algorytmach operujących wyłącznie na danych, znajdujących się w pamięci operacyjnej.

Na rysunku 1.1 można także dostrzec moduł zarządzania pamięcią, który ma za zadanie wybierać właściwe dane z pamięci i w razie potrzeby dostosować je do wymagań modułów z wyższych poziomów systemu. Widać tam także składową, którą nazwaliśmy modułem przetwarzania zapytań, mimo żc taka nazwa może wprowadzać w błąd, bowiem obsługuje on nie tylko zapytania, ale również aktualizacje danych oraz metadanych. Jego zadanie polega na znalezieniu najlepszego sposobu wykonania zadanych operacji i na wydaniu poleceń do modułu zarządzania pamięcią, który jc wykona.

Moduł zarządzania transakcjami odpow-iada za spójność systemu. Musi on gwarantować, że kilka jednocześnie przetwarzanych zapytań nie będzie