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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Indeks RD-drzewo

Indeks RD-drzewo


Dla wydajnej realizacji zapytań odwołujących się do atrybutów wielowartościowych lub związków wielokrotnych stosuje się dodatkowe struktury danych bazujące na sygnaturach zbiorów. Jedną z takich struktur jest indeks nazywany RD-drzewem od angielskiego Russian Doll. Indeks ten jest zakładany na sygnaturach atrybutów wielowartościowych lub związków wielokrotnych. Indeks ten ma strukturę hierarchiczną i jest wzorowany na B-drzewie. Wartościami kluczy przechowywanymi w węzłach wewnętrznych są sygnatury utworzone przez operację sumy logicznej wszystkich sygnatur przechowywanych w węźle niższego poziomu wskazywanym przez wskaźnik skojarzony z daną zbiorczą sygnaturą.

Na rysunku pokazano fragment dwupoziomowego RD-drzewa założonego na atrybucie Wierzchołki obiektów z kolekcji Wielokąty. W liściach indeksu znajdują się sygnatury utworzone dla zbiorów wierzchołków poszczególnych wielokątów. Na przykład sygnatura sig(w2) reprezentuje zbiór pięciu wierzchołków: p4, p5, p6, p7 i p8 wielokąta o nazwie Wielokąt2. Sygnatury w korzeniu drzewa są utworzone z sygnatur przechowywanych w liściach drzewa. Na przykład pierwsza sygnatura składowana w korzeniu jest sumą logiczną sygnatur dwóch zbiorów wierzchołków w1 i w2.


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