ZSBD-2st-1.2-w6.tresc-1.1-Slajd17

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Indeksowanie hierarchii rozszerzeń klas(1)

Indeksowanie hierarchii rozszerzeń klas(1)


Na slajdzie przedstawiono dwie dedykowane metody wydajnego wyszukiwania obiektów w hierarchiach rozszerzeń klas. Obydwie polegają na modyfikacjach struktury indeksu typu B-drzewo.

Pierwsze rozwiązanie polega na rozszerzeniu struktury liści indeksu w celu przechowywania dodatkowej informacji o typie każdego indeksowanego obiektu. Ogólna struktura informacji przechowywanej w liściach indeksu jest następująca. Z każdym kluczem jest związana lista zbiorów wskaźników na obiekty o danej wartości klucza. Elementy listy odpowiadają poszczególnym podzbiorom danych. Na slajdzie pokazano kawałek liścia takiego indeksu założonego na atrybucie „wiek ”. Z kluczem o wartości równej 25 lat jest związana lista zbiorów wskaźników „p ”. Wskaźniki są pogrupowane w zależności od klasy obiektów których dotyczą. Dwie pierwsze grupy to wskaźniki na pracowników i studentów.

Drugim rozwiązaniem są tak zwiane h-drzewa. H-drzewo jest hierarchią B-drzew odpowiadającą hierarchii podzbiorów. Korzeniem tej hierarchii jest indeks odpowiadający klasie bazowej całej hierarchii klas, z którego są osiągalne wszystkie obiekty. Z indeksów ulokowanych niżej w hierarchii osiągalne są tylko obiekty należące do odpowiedniej pod-hierarchii klas. Indeksy ulokowane liściach hierarchii adresują obiekty będące wystąpieniami pojedynczych klas. Wynika stąd, że zakresy zasięgów indeksów z różnych poziomów hierarchii pokrywają się. Natomiast zakresy zasięgów indeksów znajdujących się na tym poziomie hierarchii są rozłączne. W pośrednich węzłach indeksów występują dwa rodzaje wskaźników: wskaźniki na węzły niższego poziomu w tym samym indeksie i wskaźniki na węzły w innym indeksie znajdującym się na niższym poziomie hierarchii indeksów.

Przykładowe H-drzewo zostało pokazane na slajdzie. Korzeniem hierarchii indeksów jest indeks odpowiadający klasie „Osoba ”. Z tego indeksu są osiągalne zarówno wystąpienia klasy „Osoba ”, jak i wystąpienia klasy „Student ”. Indeksem niższego poziomu jest indeks odpowiadający klasie „Student ”, która jest podklasą klasy „Osoba ”. Z tego indeksu są osiągalne jedynie obiekty, które są wystąpieniami klasy „Student ”. W indeksie odpowiadającym klasie „Osoba znajduje się węzeł oznaczony przez „N ”, który zawiera wskaźniki na inne węzły tego indeksu i dodatkowo zawiera wskaźnik na węzeł oznaczony przez „n ”, który znajduje się wewnątrz indeksu odpowiadającego klasie „Student ”. Na rysunku pokazano przykładowe ścieżki wyszukiwania. Dwie z nich zamykają się wewnątrz indeksów składowych H-drzewa. Środkowa ścieżka pokazuje nawigację między różnymi indeksami hierarchii.


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