[ Pobierz całość w formacie PDF ]
.Nie gwarantują one jednakże, że tworzone i modyfikowane dynamicznie S-drzewo jest zrównoważone.Innym problemem jest problem niewykorzystanej pamięci.B-drzewoB-drzewo jest S-drzewem z dodatkowymi ograniczeniami.Ograniczenia te mają na celu zagwarantowanie, że drzewo jest zrównoważone i że wolna przestrzeń (na skutek usuwania rekordów) nie będzie zbyt duża.B-drzewo rzędu p definiujemy następująco:lKażdy wierzchołek wewnętrzny posiada następującą strukturęl<P1, <K1, Pr1>, P2, <K2, Pr2>, …, <Pq-1, Krq-1>, Pq>gdzie q p.Pi jest wskaźnikiem do poddrzewa.Pri jest wskaźnikiem do bloku danych zawierających rekord o wartości klucza Ki.lDla każdego wierzchołka K1 < K2 < … < Kq-1llDla każdej wartości klucza x w poddrzewie wskazywanym przez wskaźnik Pi spełnione są następujące warunki:lKi-1 < x < Ki dla 1 < i < qx < Ki dla i = 1Ki-1 < x dla i = qlKażdy wierzchołek ma co najwyżej p wskaźników do poddrzew.llKażdy wierzchołek, za wyjątkiem korzenia i liści, posiada co najmniej (p/2) wskaźników do poddrzew.Korzeń posiada co najmniej 2 wskaźniki do poddrzew, za wyjątkiem sytuacji, gdy jest on jedynym wierzchołkiem w grafie.llWierzchołek o q wskaźnikach do poddrzew (q p) posiada q - 1 wartości kluczy.llWszystkie liście znajdują się na tym samym poziomie.Liście posiadają strukturę zbliżoną do struktury wierzchołków wewnętrznych - liście nie posiadają wskaźników do poddrzew.lKażdy wierzchołek to jeden rekord.Pi - wskaźnik do poddrzewa, w którym przechowywane są wartości kluczyKi - wartość kluczaPri - wskaźnik do bloku danych o kluczu PiStruktura węzła B-drzewa:B-drzewo rzędu p=3.Sekwencja wprowadzanych wartości: 8, 5, 1, 7, 3, 12, 9, 6: Przykład:Jak obliczyć p?Wartość klucza V = 9B; wskaźnik do bloku P = 6B.Rozmiar bloku B = 512B.Każdy wierzchołek ma co najwyżej p wskaźników do poddrzew, p - 1 wskaźników do danych i p - 1 kluczy:(p*6)+(( p-1)*(6+9)) 51221 * p 512p = 25B+-drzewoZdecydowana większość implementacji indeksów wielopoziomowych stosuje wariant struktury B-drzewa o nazwie B+-drzewo.Wynika z tego, że czas dostępu do dowolnego rekordu jest stały i zależy tylko od wysokości drzewa.W B+-drzewie wskaźniki do bloków danych znajdują się wyłącznie w wierzchołkach liści drzewa.Oznacza to, że liście i wierzchołki wewnętrzne drzewa posiadają różną strukturę.Struktura wierzchołków wewnętrznych B+-drzewa jest następująca:lKażdy wierzchołek wewnętrzny posiada następującą strukturęl<P1, K1, P2, K2, …, Pq-1, Kq-1, Pq>gdzie q p.Pi jest wskaźnikiem do poddrzewa.lDla każdego wierzchołka wewnętrznego K1 < K2 < … < Kq-1llDla każdej wartości klucza x w poddrzewie wskazywanym przez wskaźnik Pi spełnione są następujące warunki:lKi-1 < x Ki dla 1 < i < qx Ki dla i = 1Ki-1 < x dla i = qlKażdy wierzchołek wewnętrzny ma co najwyżej p wskaźników do poddrzew.llKażdy wierzchołek wewnętrzny, za wyjątkiem korzenia i liści, posiada co najmniej (p/2) wskaźników do poddrzew.Korzeń , jeżeli jest wierzchołkiem wewnętrznym posiada co najmniej 2 wskaźniki do poddrzew.llWierzchołek o q wskaźnikach do poddrzew (q p) posiada q - 1 wartości kluczy.lStruktura liści B+-drzewa jest następująca:lKażdy liść posiada następującą strukturęl<<K1, Pr1>, <K2, Pr2>, …, <Pq-1, Krq-1>, Pnext>gdzie q p.Pri jest wskaźnikiem do bloku danych, natomiast Pnext jest wskaźnikiem do następnego liścia B+-drzewa [ Pobierz całość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl trzylatki.xlx.pl
.Nie gwarantują one jednakże, że tworzone i modyfikowane dynamicznie S-drzewo jest zrównoważone.Innym problemem jest problem niewykorzystanej pamięci.B-drzewoB-drzewo jest S-drzewem z dodatkowymi ograniczeniami.Ograniczenia te mają na celu zagwarantowanie, że drzewo jest zrównoważone i że wolna przestrzeń (na skutek usuwania rekordów) nie będzie zbyt duża.B-drzewo rzędu p definiujemy następująco:lKażdy wierzchołek wewnętrzny posiada następującą strukturęl<P1, <K1, Pr1>, P2, <K2, Pr2>, …, <Pq-1, Krq-1>, Pq>gdzie q p.Pi jest wskaźnikiem do poddrzewa.Pri jest wskaźnikiem do bloku danych zawierających rekord o wartości klucza Ki.lDla każdego wierzchołka K1 < K2 < … < Kq-1llDla każdej wartości klucza x w poddrzewie wskazywanym przez wskaźnik Pi spełnione są następujące warunki:lKi-1 < x < Ki dla 1 < i < qx < Ki dla i = 1Ki-1 < x dla i = qlKażdy wierzchołek ma co najwyżej p wskaźników do poddrzew.llKażdy wierzchołek, za wyjątkiem korzenia i liści, posiada co najmniej (p/2) wskaźników do poddrzew.Korzeń posiada co najmniej 2 wskaźniki do poddrzew, za wyjątkiem sytuacji, gdy jest on jedynym wierzchołkiem w grafie.llWierzchołek o q wskaźnikach do poddrzew (q p) posiada q - 1 wartości kluczy.llWszystkie liście znajdują się na tym samym poziomie.Liście posiadają strukturę zbliżoną do struktury wierzchołków wewnętrznych - liście nie posiadają wskaźników do poddrzew.lKażdy wierzchołek to jeden rekord.Pi - wskaźnik do poddrzewa, w którym przechowywane są wartości kluczyKi - wartość kluczaPri - wskaźnik do bloku danych o kluczu PiStruktura węzła B-drzewa:B-drzewo rzędu p=3.Sekwencja wprowadzanych wartości: 8, 5, 1, 7, 3, 12, 9, 6: Przykład:Jak obliczyć p?Wartość klucza V = 9B; wskaźnik do bloku P = 6B.Rozmiar bloku B = 512B.Każdy wierzchołek ma co najwyżej p wskaźników do poddrzew, p - 1 wskaźników do danych i p - 1 kluczy:(p*6)+(( p-1)*(6+9)) 51221 * p 512p = 25B+-drzewoZdecydowana większość implementacji indeksów wielopoziomowych stosuje wariant struktury B-drzewa o nazwie B+-drzewo.Wynika z tego, że czas dostępu do dowolnego rekordu jest stały i zależy tylko od wysokości drzewa.W B+-drzewie wskaźniki do bloków danych znajdują się wyłącznie w wierzchołkach liści drzewa.Oznacza to, że liście i wierzchołki wewnętrzne drzewa posiadają różną strukturę.Struktura wierzchołków wewnętrznych B+-drzewa jest następująca:lKażdy wierzchołek wewnętrzny posiada następującą strukturęl<P1, K1, P2, K2, …, Pq-1, Kq-1, Pq>gdzie q p.Pi jest wskaźnikiem do poddrzewa.lDla każdego wierzchołka wewnętrznego K1 < K2 < … < Kq-1llDla każdej wartości klucza x w poddrzewie wskazywanym przez wskaźnik Pi spełnione są następujące warunki:lKi-1 < x Ki dla 1 < i < qx Ki dla i = 1Ki-1 < x dla i = qlKażdy wierzchołek wewnętrzny ma co najwyżej p wskaźników do poddrzew.llKażdy wierzchołek wewnętrzny, za wyjątkiem korzenia i liści, posiada co najmniej (p/2) wskaźników do poddrzew.Korzeń , jeżeli jest wierzchołkiem wewnętrznym posiada co najmniej 2 wskaźniki do poddrzew.llWierzchołek o q wskaźnikach do poddrzew (q p) posiada q - 1 wartości kluczy.lStruktura liści B+-drzewa jest następująca:lKażdy liść posiada następującą strukturęl<<K1, Pr1>, <K2, Pr2>, …, <Pq-1, Krq-1>, Pnext>gdzie q p.Pri jest wskaźnikiem do bloku danych, natomiast Pnext jest wskaźnikiem do następnego liścia B+-drzewa [ Pobierz całość w formacie PDF ]